FINDING COMMON NEIGHBORS BETWEEN TWO NODES IN A GRAPH

摘要

Techniques for identifying common neighbors of two nodes in a graph are provided. One technique involves performing a binary split search and/or a linear search. Another technique involves creating a segmenting index for a first neighbor list. A second neighbor list is scanned and, for each node indicated in the second neighbor list, the segmenting index is used to determine whether the node is also indicated in the first neighbor list. Techniques are also provided for counting the number of triangles. One technique involves pruning nodes from neighbor lists based on the node values of the nodes whose neighbor lists are being pruned. Another technique involves sorting the nodes in a node array (and, thus, their respective neighbor lists) based on the nodes' respective degrees prior to identifying common neighbors. In this way, when pruning the neighbor lists, the neighbor lists of the highly connected nodes are significantly reduced.

主权项

1. A method for finding common neighbors of a first node and a second node in a graph that comprises a plurality of nodes that includes the first node and the second node, the method comprising:
identifying a first set of neighbors for the first node; identifying a second set of neighbors for the second node; identifying a first neighbor in the first set of neighbors; based on the first neighbor, identifying, in the second set of neighbors, a second neighbor that matches or nearly matches the first neighbor; if the first neighbor matches the second neighbor, then storing data that identifies the first neighbor as a common neighbor of the first node and the second node; based on the first neighbor, dividing the first set of neighbors into a first subset and a second subset, wherein the first subset indicates one or more first neighbors whose values are less than a value of the first neighbor, wherein the second subset indicates one or more second neighbors whose values are greater than the value of the first neighbor; based on the second neighbor, dividing the second set of neighbors into a third subset and a fourth subset, wherein the third subset indicates one or more third neighbors whose values are less than a value of the second neighbor, wherein the fourth subset indicates one or more fourth neighbors whose values are greater than the value of the second neighbor; wherein the method is performed by one or more computing devices.