Method for identifying network similarity by matching neighborhood topology

摘要

A similarity measure is computed between nodes of first and second networks. Sets of pairwise scores are computed to find nodes in the individual networks that are good matches to one another. A pairwise score 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 process identifies node pairs that exhibit high pairwise values. Preferably, 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 is available, 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). Using the similarity scores, a common subgraph between the first and second networks is computed.

主权项

1. A computer program product comprising a non-transitory tangible machine-readable medium that stores a program, the program being executable by a machine to perform a method of identifying 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 method 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; selecting from the similarity scores a set of scores that capture mutually-consistent pairwise matches; and extracting node mappings from the set of scores to identify one or more conserved edges between the first and second network.