United States Patent
US Patent 8000262: Method for identifying network similarity by…
US 8000262 · granted 2011-08-16
Abstract
A method of computing a measure of similarity between nodes of first and second networks is described. In particular, sets of pairwise scores are computed to find nodes in the individual networks that are good matches to one another. Thus, a pairwise score, referred to as R.sub.ij, is computed for a node i in the first network and a node j in the second network. Similar pairwise scores are computed for each of the nodes in each network. The goal of this process is to identify node pairs that exhibit high R.sub.ij values. According to the technique described herein, the intuition is that nodes i and j are a good match if their neighbors are a good match. This technique produces a measure of "network similarity." If node feature data also is available, the intuition may be expanded such that nodes i and j are considered a good match if their neighbors are a good match (network similarity) and their node features are a good match (node similarity). Node feature data typically is domain-specific. Using the similarity scores, a common subgraph between the first and second networks then can be computed.
| Patent Number | 8000262 |
|---|---|
| Title | Method for identifying network similarity by matching neighborhood topology |
| Filed | 2008-04-18 |
| Granted | 2011-08-16 |
| Inventor(s) | Leighton; Bonnie Berger, Singh; Rohit |
| CPC Classification | H04L 12/28 |
| Number of Claims | 30 |
Abstract
A method of computing a measure of similarity between nodes of first and second networks is described. In particular, sets of pairwise scores are computed to find nodes in the individual networks that are good matches to one another. Thus, a pairwise score, referred to as R.sub.ij, is computed for a node i in the first network and a node j in the second network. Similar pairwise scores are computed for each of the nodes in each network. The goal of this process is to identify node pairs that exhibit high R.sub.ij values. According to the technique described herein, the intuition is that nodes i and j are a good match if their neighbors are a good match. This technique produces a measure of "network similarity." If node feature data also is available, the intuition may be expanded such that nodes i and j are considered a good match if their neighbors are a good match (network similarity) and their node features are a good match (node similarity). Node feature data typically is domain-specific. Using the similarity scores, a common subgraph between the first and second networks then can be computed.
Claim 1
A non-transitory computer-readable storage medium storing a computer readable program of computer instructions, wherein thecomputer readable program when executed on a computer causes the computer to carry out operations to identify a common subgraph between first and second networks, the first network G.sub.1 having a set of nodes V.sub.1 and a set of edges E.sub.1, thesecond network G.sub.2 having a set of nodes V.sub.2 and a set of edges E.sub.2, where N(a) is a set of neighbors of a given node a, the set being of size |N(a)|, with each edge e of a network having an edge weight w(e), the operations comprising: foreach of a set of node pairs (i, j), where i is a node from the first network and j is a node from the second network, and where u is a neighbor of i and v is a neighbor of j, computing a similarity score R.sub.i,j equal to a support value provided to thenode pair (i, j) by |N(i).parallel.N(j)| possible matches between neighbors of i and j, where each neighboring node pair (u,v) distributes back its score R.sub.uv among |N(u).parallel.N(v)| possible matches between neighbors of u and v; using thesimilarity scores to construct the common subgraph.
Claims
30 totalA non-transitory computer-readable storage medium storing a computer readable program of computer instructions, wherein thecomputer readable program when executed on a computer causes the computer to carry out operations to identify a common subgraph between first and second networks, the first network G.sub.1 having a set of nodes V.sub.1 and a set of edges E.sub.1, thesecond network G.sub.2 having a set of nodes V.sub.2 and a set of edges E.sub.2, where N(a) is a set of neighbors of a given node a, the set being of size |N(a)|, with each edge e of a network having an edge weight w(e), the operations comprising: foreach of a set of node pairs (i, j), where i is a node from the first network and j is a node from the second network, and where u is a neighbor of i and v is a neighbor of j, computing a similarity score R.sub.i,j equal to a support value provided to thenode pair (i, j) by |N(i).parallel.N(j)| possible matches between neighbors of i and j, where each neighboring node pair (u,v) distributes back its score R.sub.uv among |N(u).parallel.N(v)| possible matches between neighbors of u and v; using thesimilarity scores to construct the common subgraph.