# US 9,519,864 B1 · Method and system for identifying dependent components

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,519,864 B1
- Document ID: US9519864B1
- Status: Granted
- Kind: B1
- Application number: 14/967,678
- Filed: 2015-12-14
- Granted: 2016-12-13
- Earliest claimed: 2015-11-09
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Reinhard Wolfram Heckel; Vasileios Vasileiadis; Michail Vlachos
- Web page: https://patentgrep.com/patent/US9519864B1

## CPC

- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06N 5/022: Knowledge engineering; Knowledge acquisition
- G06N 5/04: Inference or reasoning models
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Embodiments include processing a data structure representing a dependency matrix having columns representing respective first components and rows representing respective second components. Aspects include assigning each cell of the matrix a value indicative of the level of dependency or indicative of an unknown dependency of a pair of first and second components forming the cell and assigning each component of the first and second components an affiliation vector indicative of the strength of affiliation of the component to N predefined initial clusters of cells of the matrix. Aspects also include determining a probability model using the affiliations vectors parameters and estimating the parameters of the probability model for a plurality of different numbers of clusters starting from the initial number N of clusters. Aspects further include computing a score for the parameters of the probability model estimated and selecting the parameters of the probability model with the highest computed score.

## Claims

### Claim 1

A computer implemented method for processing a data structure representing a dependency matrix having a plurality of columns representing respective first components and a plurality of rows representing respective second components, the method comprising:
assigning each cell of the matrix a value indicative of the level of dependency or indicative of an unknown dependency of a pair of first and second components forming the cell;
assigning each component of the first and second components an affiliation vector fu and fi respectively indicative of the strength of affiliation of the component to N predefined initial clusters of cells of the matrix, and initializing the affiliation vectors with predefined values;
determining a probability model using the affiliations vectors fu and fi as parameters, wherein the probability model presents the probabilities for a first component of the first components to depend on a second component of the second components;
estimating the parameters of the probability model for a plurality of different numbers of clusters starting from the initial number N of clusters using the matrix;
computing a score for the parameters of the probability model estimated for each of the plurality of different numbers of clusters;
selecting the parameters of the probability model with the highest computed score;
using the selected parameters of the probability model to identify cells of unknown dependencies pairs of first and second components that depend on each other.

### Claim 2 (depends on 1)

The method of claim 1, wherein the probability model is a function of the inner product <fu, fi> between two affiliation vectors fu and fi in RN y corresponding to the first and second components, where c runs over each cluster of the N clusters.

### Claim 3 (depends on 1)

The method of claim 1, wherein the probability model is given by the following equation: 1−e−(fu,fi).

### Claim 4 (depends on 3)

The method of claim 3, wherein the parameters of the probability model are estimated by computing a maximum of a likelihood given by the following equation:
=
∏
(
u
,
i
)
:
r
u
⁢
⁢
i
=
1
⁢
(
1
-
ⅇ
-
〈
f
u
,
f
i
〉
)
⁢
∏
(
u
,
i
)
:
r
u
⁢
⁢
i
=
0
⁢
ⅇ
-
〈
f
u
,
f
i
〉

### Claim 5 (depends on 2)

The method of claim 2, wherein parameters of the probability model are estimated by computing a minimum of the following equation Q subject to [fu]c, [fi]c≧0, ∀c:
Q
=
-
log
⁢
⁢
+
λ
⁢
∑
i
⁢

f
i

2
2
+
λ
⁢
∑
u
⁢

f
u

2
2
,
where
-
log
⁢
⁢
=
-
∑
(
u
,
i
)
:
r
u
⁢
⁢
i
=
1
⁢
log
⁡
(
1
-
ⅇ
-
〈
f
u
,
f
i
〉
)
+
∑
(
u
,
i
)
:
r
u
⁢
⁢
i
=
0
⁢
〈
f
u
,
f
i
〉
and λ≧0 is a regularization parameter, where c runs over each cluster of the N clusters.

### Claim 6 (depends on 5)

The method of claim 5, wherein the minimizing comprises:
determining the value of Q by adjusting values of the parameter fi while fu is fixed;
determining the value of Q by adjusting values of the parameter fi while fu is fixed;
repeating the determining steps until Q changes by a value that is smaller or equal to a predetermined maximum improvement value.

### Claim 7 (depends on 5)

The method of claim 5, wherein the minimizing of Q comprises using a predefined solver for a convex problem, preferably, a gradient descent method for iteratively adjusting the parameters fu and fi.

### Claim 8 (depends on 1)

The method of claim 1, wherein identifying a given cell of the identified cells comprises evaluating or calculating the probability model using the selected parameters for the pairs of first and second components of the given cell and determining that the calculated probability model is higher than a predefined threshold.

### Claim 9 (depends on 1)

The method of claim 1, wherein the data structure is a two-dimensional array of scalar elements, which captures dependencies between at least 104 components, preferably 105 components.

### Claim 10 (depends on 1)

The method of claim 1, wherein the data structure is representable as an adjacency matrix of a bipartite graph, preferably a bipartite graph of components versus component attributes.

### Claim 11 (depends on 1)

The method of claim 1, wherein the first and second components comprise nodes of a data communication network.

### Claim 12 (depends on 10)

The method of claim 10, wherein the probabilities for a first component of the first components to depend on a second component of the second components comprises the probability that at least one of:
the first component accesses data in the second component;
the first component requests a service of the second component.

### Claim 13 (depends on 1)

The method of claim 1, further comprising notifying an operation state of the first and second components.

### Claim 14 (depends on 1)

The method of claim 1, the identified cells being part of overlapping clusters.