METHOD FOR ENUMERATING CLIQUES

• US 20090315890A1
• Filed: 06/18/2008
• Published: 12/24/2009
• Est. Priority Date: 06/18/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Modani, Natwar
• Granted Patent: US 8,395,622 B2
• Time in Patent Office: Days
• 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/32 Post and telecommunications franking apparatus G07B17/00
• 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;

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.

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 filtering the data comprises using an extent of over lap in one or more neighborhoods of two vertices as a basis for filtering the data prior to enumerating at least one maximal clique.

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

for each node, examining each edge incident thereon;

counting a number of one or more nodes that are common in one or more neighborhoods of the two vertices joined by the edge, wherein if the number of such common neighbor nodes is at least L−

2, retaining the edge, else discarding the edge; and

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.

7. The method of claim 6 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.

8. 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.

9. The method of claim 8, 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.

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

11. The method of claim 8, 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.

12. The method of claim 8, 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.

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

14. A computer program product comprising a computer readable 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;

computer readable program code for filtering the data using the user-specified minimum size restriction to reduce graph size; 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.

15. The computer program product of claim 14, 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.

16. The computer program product of claim 14, wherein the computer readable program code for filtering the data comprises computer readable program code for using an extent of overlap in one or more neighborhoods of two vertices as a basis for filtering the data prior to enumerating at least one maximal clique.

17. The computer program product of claim 14, 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.

18. 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;

filter the data using the user-specified minimum size restriction to reduce graph size; 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.

19. The apparatus of claim 18, 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.

20. The apparatus of claim 18, wherein in filtering the data, the at least one processor coupled to said memory is further operative to use an extent of overlap in one or mole neighborhoods of two vertices as a basis for filtering the data prior to enumerating at least one maximal clique.