Graph data representation and pre-processing for efficient parallel search tree traversal
AssigneeInternational Business Machines Corporation
InventorsKubilay Atasu, Silvio Dragone, Christoph Hagleitner, Robert R. McCune
Life of this patent
Estimating the term…
Abstract
One or more embodiments may provide the capability to enumerate maximal cliques of graph data by constructing and traversing a search tree through a single sequential pass on an adjacency list. The adjacency list may be generated so as to enable the at least one maximal clique to be generated in one single sequential pass.
Claims20
A computer-implemented method for clique enumeration of graph data, the method comprising:
- receiving, using a processor system, data representing a graph comprising a plurality of nodes and a plurality of edges connecting at least some of the nodes;
- generating, using the processor system at least one adjacency list specifying nodes that are neighbors of a node based on the received data representing the graph;
- and
- generating, based on the at least one adjacency list, at least one maximal clique, wherein the at least one maximal clique specifies at least one set of nodes in which every node is connected to every other node and to which no additional node can be added with every node still being connected to every other node.
A computer system for clique enumeration of graph data comprising:
- a plurality of processing kernels, each processing kernel comprising processing circuitry, input memory configured to store input to the processing kernel, output memory configured to store output from the processing kernel, and a plurality of intermediate memories configured to store intermediate processing data, wherein the processing circuitry is configured to:
- receive data representing a graph comprising a plurality of nodes and a plurality of edges connecting at least some of the nodes;
- generate at least one adjacency list specifying nodes that are neighbors of a node based on the received data representing the graph;
- and
- generate, based on the at least one adjacency list, at least one maximal clique, wherein the at least one maximal clique specifies at least one set of nodes in which every node is connected to every other node and to which no additional node can be added with every node still being connected to every other node.
A computer program product for clique enumeration of graph data, the computer program product comprising a non-transitory computer readable storage having program instructions embodied therewith, the program instructions executable by a computer, to cause the computer to perform a method comprising:
- generating at least one adjacency list specifying nodes that are neighbors of a node based on the received data representing the graph;
- and
- generating, based on the at least one adjacency list, at least one maximal clique, wherein the at least one maximal clique specifies at least one set of nodes in which every node is connected to every other node and to which no additional node can be added with every node still being connected to every other node.
Dependencies are inferred from the claim text.