×

Method for identifying network similarity by matching neighborhood topology

  • US 8,000,262 B2
  • Filed: 04/18/2008
  • Issued: 08/16/2011
  • Est. Priority Date: 04/18/2008
  • Status: Active Grant
First Claim
Patent Images

1. A non-transitory computer-readable storage medium storing a computer readable program of computer instructions, wherein the computer 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 G1 having a set of nodes V1 and a set of edges E1, the second network G2 having a set of nodes V2 and a set of edges E2, 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:

  • for each 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 Ri,j equal to a support value provided to the node pair (i, j) by |N(i)∥

    N(j)| possible matches between neighbors of i and j, where each neighboring node pair (u,v) distributes back its score Ruv among |N(u)∥

    N(v)| possible matches between neighbors of u and v;

    using the similarity scores to construct the common subgraph.

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×