Method for enumerating cliques

• US 8,395,622 B2
• Filed: 06/18/2008
• Issued: 03/12/2013
• Est. Priority Date: 06/18/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Modani, Natwar
• Primary Examiner(s): Johnson, M Good
• Application Number:
  US12/141,219
• Publication Number:
  US 20090315890A1
• Time in Patent Office: 1,728 Days
• Field of Search: 345/440, 370/254, 709/200
• US Class Current: 345/440
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 50/60 Business processes related to postal services shipping G06Q10/083; franking apparatus G07B17/00

Abstract

Techniques for enumerating at least one maximal clique are provided. The techniques include obtaining data, wherein the data comprises a graph, obtaining a user-specified minimum size restriction on at least one maximal clique of interest, filtering the data using the user-specified minimum size restriction to reduce graph size, and enumerating at least one maximal clique from the graph provided that at least one maximal clique exists above the user-specified minimum size restriction.

Claims

1. A method for enumerating at least one maximal clique, comprising the steps of:

obtaining data, wherein the data comprises a graph;

obtaining a user-specified minimum size restriction on at least one maximal clique of interest in the graph;

filtering the data based on the user-specified minimum size restriction and an extent of overlap in one or more neighborhoods of two vertices joined by an edge to reduce graph size, wherein said filtering comprises counting a number of one or more nodes that are common in the one or more neighborhoods, and wherein if the number of such common neighbor nodes exceeds a specified number, retaining the edge, else discarding the edge; and

enumerating at least one maximal clique from the graph provided that at least one maximal clique exists above the user-specified minimum size restriction.

2. The method of claim 1, wherein filtering the data comprises using degree-based filtering while loading less than an entire graph in memory to reduce the graph in size.

3. The method of claim 2, wherein degree-based filtering comprises the steps of:

keeping track of one or more nodes dropped in a current and a previous iteration;

reading one vertex and all of its one or more neighbors at a time from a sequential access memory;

determining whether each neighbor node was dropped in the current or previous iteration, wherein if a neighbor node was dropped, dropping it from a list of one or more neighbors; and

determining a number of one or more surviving neighbors, wherein if there are fewer than L−

1 surviving neighbors, removing the node from consideration and adding it to a list of nodes dropped in the current iteration, and wherein if the number of one or more surviving neighbors is at least L−

1, outputting the node and its neighbors to a sequential access memory, and wherein L is the user-specified minimum desired clique size.

4. The method of claim 3, wherein the determining steps are repeated until no nodes are dropped in an iteration.

5. The method of claim 1, wherein using an extent of overlap in one or more neighborhoods of two vertices as a basis for filtering the data comprises steps of:

determining a number of one or more surviving edges for a given node, wherein if the number of the one or more edges is less than L−

1, discarding the node and each of one or more associated edges, else retaining the node and the one or more surviving edges.

6. The method of claim 5, wherein the steps are repeated until at least one of no vertex and no edge is dropped in one full iteration over all of the one or more nodes.

7. The method of claim 1, further comprising attaching a taboo list to a candidate for each vertex that is chosen to not be retained in the candidate, wherein attaching a taboo list facilitates determining if a candidate cannot give rise to a maximal clique.

8. The method of claim 7, wherein the taboo list comprises a set of one or more vertices such that if none of the one or more vertices is retained in the candidate, the candidate cannot evolve into a maximal clique.

9. The method of claim 8, wherein the one or more vertices are neighbors of each the one or more nodes that are guaranteed to participate in a maximal clique arising from the candidate.

10. The method of claim 7, where the taboo list is considered to be fulfilled when one of the one or more nodes in it is guaranteed to be included in a maximal clique arising from the candidate, and is discarded from further consideration to decide maximality of the candidate.

11. The method of claim 7, where the taboo list is updated upon deciding to drop a node from the candidate to which the taboo list is attached, wherein updating comprises removing the node from the taboo list.

12. The method of claim 7, where the candidate is declared to be incapable of producing a maximal clique when a taboo list attached thereto becomes empty.

13. A computer program product comprising a tangible computer readable recordable storage medium having computer readable program code for enumerating at least one maximal clique, said computer program product including:

computer readable program code for obtaining data, wherein the data comprises a graph;

computer readable program code for obtaining a user-specified minimum size restriction on at least one maximal clique of interest in the graph;

computer readable program code for filtering the data based on the user-specified minimum size restriction and an extent of overlap in one or more neighborhoods of two vertices joined by an edge to reduce graph size, wherein said filtering comprises counting a number of one or more nodes that are common in the one or more neighborhoods, and wherein if the number of such common neighbor nodes exceeds a specified number, retaining the edge, else discarding the edge; and

computer readable program code for enumerating at least one maximal clique from the graph provided that at least one maximal clique exists above the user-specified minimum size restriction.

14. The computer program product of claim 13, wherein the computer readable program code for filtering the data comprises computer readable program code for using degree-based filtering while loading less than an entire graph in memory to reduce the graph in size.

15. The computer program product of claim 13, further comprising computer readable program code for attaching a taboo list to a candidate for each vertex that is chosen to not be retained in the candidate, wherein attaching a taboo list facilitates determining if a candidate cannot give rise to a maximal clique.

16. An apparatus for enumerating at least one maximal clique, comprising:

a memory; and

at least one processor coupled to said memory and operative to;

obtain data, wherein the data comprises a graph;

obtain a user-specified minimum size restriction on at least one maximal clique of interest in the graph;

filter the data based on the user-specified minimum size restriction and an extent of overlap in one or more neighborhoods of two vertices joined by an edge to reduce graph size, wherein said filtering comprises counting a number of one or more nodes that are common in the one or more neighborhoods, and wherein if the number of such common neighbor nodes exceeds a specified number, retaining the edge, else discarding the edge; and

enumerate at least one maximal clique from the graph provided that at least one maximal clique exists above the user-specified minimum size restriction.

17. The apparatus of claim 16, wherein in filtering the data, the at least one processor coupled to said memory is further operative to use degree-based filtering while loading less than an entire graph in memory to reduce the graph in size.