Method for detecting cliques in graphs

Patent metadata

Field	Value
Publication number	US-10055510-B2
Application number	US-201514932076-A
Country	US
Kind code	B2
Filing date	Nov 4, 2015
Priority date	Nov 4, 2015
Publication date	Aug 21, 2018
Grant date	Aug 21, 2018

Abstract

A method is provided for searching a graph to identify cliques using a set of processing elements (PEs), a first PE of the set of PEs having access to an adjacency list of a seed vertex of the graph, the adjacency list of the seed vertex including a set of vertices. The method includes: generating a data structure for each intermediate vertex of the set of vertices, the data structure indicating the respective intermediate vertex and an additional list of intermediate vertices of the set of vertices; storing the generated data structures; for each buffered data structure, receiving the buffered data structure and configuring the available PE to receive an adjacency list of the intermediate vertex indicated in the respective data structure and to select from the adjacency list a set of further vertices that are adjacent to the seed vertex and are part of the additional list.

First claim

What is claimed is:

1. A method for searching a graph to identify cliques using a set of processing elements (PEs), wherein a first PE of the set of PEs has access to a set of vertices adjacent to a seed vertex of the graph, the method comprising:
a) generating, by the first PE, a data structure for each intermediate vertex of the set of vertices, the data structure indicating the respective intermediate vertex and an additional list of zero or more intermediate vertices of the set of vertices;
b) storing, by the first PE, the generated data structures on a data buffer;
c) for each buffered data structure of the buffered data structures:
receiving, by an available PE of the set of PEs, the buffered data structure from the data buffer;
configuring the available PE to receive an adjacency list of the intermediate vertex indicated in the respective data structure and to select from the adjacency list of the intermediate vertex a set of further vertices that are adjacent to the seed vertex and are part of the additional list;
when at least one further vertex is selected, repeating steps a) through c) with the available PE being the first PE and the set of further vertices being the set of vertices; and
when no further vertex is selected, generating a clique candidate using the seed vertex and the intermediate vertices that have been processed in step c); and

d) selecting, among the clique candidates having overlapping pairs of vertices, cliques comprising a maximum number of vertices and selecting other cliques as clique candidates having non-overlapping pairs of vertices with other clique candidates;
wherein receipt of the adjacency list of the intermediate vertex indicated in the respective data structure comprises receiving a stream of adjacency lists of vertices of the graph and identifying the adjacency list of the intermediate vertex using the data structure.

2. The method of claim 1 , wherein receipt of the adjacency list of the intermediate vertex indicated in the respective data structure comprises:
providing a ring buffer; and
receiving from the ring buffer the stream of adjacency lists of vertices of the graph.

3. The method of claim 1 , further comprising storing, by the first PE, the set of vertices in association with the generated data structures, wherein the available PE is further configured to receive the set of vertices from the data buffer, and wherein the adjacency list of the intermediate vertex indicated in the respective data structure comprises at least part of the set of vertices.

4. The method of claim 3 , wherein the available PE is configured to receive the set of vertices together with the buffered data structure from the data buffer.

5. The method of claim 1 , wherein the data buffer comprises a first-in first-out (FIFO) buffer, and wherein data structures are stored and received from the FIFO buffer according to a FIFO mode of operation.

6. The method of claim 1 , wherein step c) is sequentially performed for each buffered data structure.

7. The method of claim 1 , wherein the available PE is an idle PE.

8. The method of claim 1 , wherein steps a) through c) are performed in accordance with a Bron-Kerbosch algorithm.

9. The method of claim 1 , further comprising repeating steps a) through c) for each vertex of the graph using a respective first PE, with the each vertex being the seed vertex.

10. The method of claim 9 , wherein the graph comprises N vertices, where N is an integer, the method further comprising assigning to the each vertex a different value i that is between 1 and N, wherein the set of vertices to which the first PE has access comprises N−i vertices of the N vertices that are adjacent to the seed vertex.

11. The method of claim 1 , wherein generating, by the first PE, the data structure for each intermediate vertex of the set of vertices comprises generating the data structure having a number of elements associated with each intermediate vertex of the set of vertices, and tagging the element associated with the given intermediate vertex differently from the other elements, wherein the available PE is further configured to use the tagging to identify the given intermediate vertex.

12. The method of claim 11 , wherein tagging comprises assigning the first element of the data structure to the given intermediate vertex.

13. The method of claim 11 , wherein tagging comprises assigning the first non-null element of the data structure to the given intermediate vertex.

14. The method of claim 1 , wherein the graph comprises an undirected graph.

15. The method of claim 1 , wherein the graph comprises at least one of an undirected graph with web pages as vertices and links as edges, and a graph representing a social network connecting multiple users, wherein users are represented by nodes and user dependencies are represented by edges.

16. The method of claim 1 , wherein the set of vertices comprises a number N of vertices, where N is an integer, the zero or more intermediate vertices comprise N−i intermediate vertices of the set of vertices, wherein i is between 1 and N, wherein each intermediate vertex of the set of vertices is assigned a different value of i.

17. A set of processing elements (PEs) for searching a graph to identify cliques, the set of PEs comprising a first PE having access to a set of vertices adjacent to a seed vertex of the graph, the first PE being configured:
a) to generate a data structure for each intermediate vertex of the set of vertices, the data structure indicating the respective intermediate vertex and an additional list of zero or more intermediate vertices of the set of vertices;
b) to store the generated data structures in a data buffer;
c) for each buffered data structure of the buffered data structures, the set of PEs comprising an available PE being configured:
to receive, by an available PE of the set of PEs, the buffered data structure from the data buffer; and
to configure the available PE to receive an adjacency list of the intermediate vertex indicated in the respective data structure and to select from the adjacency list of the intermediate vertex a set of further vertices that are adjacent to the seed vertex and are part of the additional list, wherein receipt of the adjacency list of the intermediate vertex indicated in the respective data structure comprises receiving a stream of adjacency lists of vertices of the graph and identifying the adjacency list of the intermediate vertex using the data structure;
wherein in case at least one further vertex is selected, repeating steps a) through c) with the available PE being the first PE and the set of further vertices being the set of vertices.

18. A hardware accelerator comprising a set of processing elements (PEs) according to claim 17 , the hardware accelerator being configured for selecting among clique candidates having overlapping pairs of vertices cliques comprising a maximum number of vertices and for selecting other cliques as clique candidates having non-overlapping pairs of vertices with other clique candidates.

Assignees

• IBM

Inventors

• Atasu Kubilay
• Dragone Silvio

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/24532

  of parallel queries · CPC title

• G06T1/20

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• G06F17/30958 Primary

  Physics · mapped topic

• G06F17/30445

  Physics · mapped topic