Method for discovery of clusters of objects in an arbitrary undirected graph using a difference between a fraction of internal connections and maximum fraction of connections by an outside object

• US 7,818,272 B1
• Filed: 07/31/2006
• Issued: 10/19/2010
• Est. Priority Date: 07/31/2006
• Status: Expired due to Fees

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Tarjan, Robert E., Mishra, Nina, Schreiber, Robert Samuel
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US11/496,807
• Time in Patent Office: 1,541 Days
• Field of Search: 706/14, 463/29, 380/251, 707/713, 707/721, 707/776, 707706-709
• US Class Current: 706/14
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A method for discovery of a cluster of objects in an arbitrary undirected graph. A subset of the objects is determined by performing a random walk starting from a first object of the objects and following a plurality of random edges of subsequent objects, the subset comprising the first object and the subsequent objects. An enlarged subset is determined by enlarging the subset to include other objects well-connected to the subset. It is determined whether the enlarged subset is a cluster.

Claims

1. A computer-implemented method for discovery of a cluster of objects in an arbitrary undirected graph, the method comprising:

determining a subset of the objects by performing a random walk starting from a first object of the objects and following a plurality of random edges of subsequent objects, the subset comprising the first object and the subsequent objects;

determining an enlarged subset by enlarging the subset to include other objects well-connected to the subset; and

determining whether the enlarged subset is a cluster wherein fraction of internal connections which defines a cluster (β

) is determined, a maximum fraction of connections by an outside object to said cluster (α

) is determined, and said cluster is defined as acceptable when the difference between said fraction of internal connections and said maximum fraction of connections by an outside object (β

−

α

) exceeds a threshold value.

2. The computer-implemented method of claim 1 further comprising removing objects from the subset based on connectivity of objects within the subset.

3. The computer-implemented method of claim 1 further comprising modifying the enlarged subset by comparing connectedness of objects within the enlarged subset to connectedness of objects outside of the enlarged subset to objects within the enlarged subset.

4. The computer-implemented method of claim 3 further comprising adding objects outside of the enlarged subset to the enlarged subset that have higher connectivity to objects within the enlarged subset than a connectivity within the enlarged subset of at least one object within the enlarged subset.

5. The computer-implemented method of claim 3 further comprising removing objects within the enlarged subset that have a lower connectivity to other objects within the enlarged subset than a connectivity of at least one object outside the enlarged subset to objects within the enlarged subset.

6. The computer-implemented method of claim 1 wherein the random edges of the random walk are skewed with probability proportional to a number of edges between previous objects of the random walk and a current object of the random walk.

7. The computer-implemented method of claim 1 wherein the determining whether the enlarged subset is a cluster is based at least in part on a minimum fraction of internal connections and a maximum fraction of external connections defining a cluster.

8. The computer-implemented method of claim 1 wherein the arbitrary undirected graph is a bipartite graph.

9. The computer-implemented method of claim 1 wherein the random walk comprises a predetermined number of steps.

10. The computer-implemented method of claim 1 further comprising repeating the determining a subset of the objects, the determining an enlarged subset, and determining whether the enlarged subset is a cluster for a plurality of objects of the arbitrary undirected graph.

11. A computer-usable storage medium having computer-readable program code embodied therein for causing a computer system to perform a method for discovery of clusters of vertices in an arbitrary undirected graph, the method comprising:

for a plurality of vertices of the arbitrary undirected graph

performing a random walk starting from a selected vertex and traversing a predetermined number of random edges of subsequent vertices yielding a subset of the vertices, the subset comprising the selected vertex and the subsequent vertices;

selectively adding vertices to the subset and removing vertices from the subset based at least in part on connectivity of the vertices to the subset yielding a proposed cluster; and

evaluating whether the proposed cluster is acceptable as a cluster wherein fraction of internal connections which defines said cluster (β

) is determined, a maximum fraction of connections by an outside object to said cluster (α

) is determined, and said cluster is defined as acceptable when the difference between said fraction of internal connections and said maximum fraction of connections by an outside object (β

−

α

) exceeds a threshold value.

12. The computer-usable storage medium of claim 11 further comprising modifying the proposed cluster by comparing connectedness of objects within the enlarged subset to connectedness of objects outside of the enlarged subset to objects within the enlarged subset.

13. The computer-usable storage medium of claim 11 wherein the performing a random walk comprises skewing selection of a subsequent vertex with probability proportional to a number of edges between previous vertices of the random walk and the subsequent vertex.

14. The computer-usable storage medium of claim 11 wherein the evaluating whether the proposed cluster is acceptable as a cluster is based at least in part on a minimum fraction of internal connections and a maximum fraction of external connections defining a cluster.

15. The computer-usable storage medium of claim 11 wherein the arbitrary undirected graph is a bipartite graph.

16. A system for identifying clusters of objects in an arbitrary undirected graph, the system comprising:

means for determining a subset of the objects by performing a random walk starting from a first object of the objects and following a plurality of random edges of subsequent objects, the subset comprising the first object and the subsequent objects;

means for determining an enlarged subset by enlarging the subset to include other objects well-connected to the subset; and

means for determining whether the enlarged subset is a cluster wherein fraction of internal connections which defines a cluster (β

) is determined, a maximum fraction of connections by an outside object to said cluster (α

) is determined, and said cluster is defined as acceptable when the difference between said fraction of internal connections and said maximum fraction of connections by an outside object (β

−

α

) exceeds a threshold value.

17. The system of claim 16 further comprising means for removing objects from the subset based on connectivity of objects within the subset.

18. The system of claim 16 further comprising means for modifying the enlarged subset by comparing connectedness of objects within the enlarged subset to connectedness of objects outside of the enlarged subset to objects within the enlarged subset.

19. The system of claim 16 further comprising skewing selection of the random edges of the random walk with probability proportional to a number of edges between previous objects of the random walk and a current object of the random walk.

20. The system of claim 16 wherein the means for determining whether the enlarged subset is a cluster is operable to determine whether the enlarged subset is a cluster based at least in part on a minimum fraction of internal connections and a maximum fraction of external connections defining a cluster.