COUNTING TRIANGLES 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 counting a number of triangles in a graph that comprises a plurality of nodes, the method comprising:
for each node in the plurality of nodes, determining a degree of said each node; based on the degree of each node of the plurality of nodes, ordering a set of neighbor lists, wherein each neighbor list in the set of neighbor lists corresponds to a different node of the plurality of nodes and comprises a set of neighbors of said different node in the graph; after ordering the set of neighbor lists, for each neighbor list in the set of neighbor lists, removing, from said each neighbor lists, one or more neighbors; after removing the one or more neighbors, determining the number of triangles in the graph; wherein the method is performed by one or more computing devices.