Approximate maximal clique enumeration for dynamic graphs

A computer-implemented method for determining an approximation of a set of largest maximal cliques connected to each node, entities represented by nodes and pairwise relation represented by edges, the method comprising:

• initializing an adjacency variable indexed by node and includes entries, for each node, indicating which other nodes of the nodes are directly connected to the node by an edge;
• initializing a clique variable indexed by node and sub-indexed by clique size, storing, for each node, cliques of which the node is a member;
• receiving dynamic graph data indicating the nodes and the edges of a dynamic graph;
• estimating, for one or more nodes of the nodes, cliques of size less than or equal to a user specified or default clique size parameter;
• storing the estimated cliques in the clique variable;
• identifying, for cliques of size greater than or equal to the user specified or default clique size parameter, at most a single clique of a corresponding size;
• storing the identified single clique in the clique variable;
• updating and overwriting, in real time, the adjacency and clique variables in response to an addition or deletion of a node or edge in the dynamic graph;
• and
• returning, for each node, the largest maximal cliques in the clique variable.

A non-transitory machine-readable medium including instructions that, when executed by a machine, cause the machine to perform operations for determining an approximation of a set of largest maximal cliques connected to each node, entities represented by nodes and pairwise relation represented by edges, the operations comprising:

• initializing an adjacency variable indexed by node and includes entries, for each node, indicating which other nodes of the nodes are directly connected to the node by an edge;
• initializing a clique variable indexed by node and sub-indexed by clique size, storing, for each node, cliques of which the node is a member;
• receiving dynamic graph data indicating the nodes and the edges of a dynamic graph;
• estimating, for one or more nodes of the nodes, cliques of size less than or equal to a user specified or default clique size parameter;
• storing the estimated cliques in the clique variable;
• identifying, for cliques of size greater than or equal to the user specified or default clique size parameter, at most a single clique of a corresponding size;
• storing the identified single clique in the clique variable;
• updating and overwriting, in real time, the adjacency and clique variables in response to an addition or deletion of a node or edge in the dynamic graph;
• and
• returning, for each node, the largest maximal cliques in the clique variable.