HIERARCHICAL CLUSTERING OF LARGE-SCALE NETWORKS

• US 20080126523A1
• Filed: 09/22/2006
• Published: 05/29/2008
• Est. Priority Date: 09/22/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Benyu, Zhang, Heng, Tantrum, Jeremy, Srivastava, Abhinai, Mah, Teresa B.
• Granted Patent: US 7,627,542 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/125 involving control of end-device applications over a network

Abstract

A method and system are provided for identifying groups in large-scale networks. The large-scale networks include a collection of nodes and edges that may represent relationships between entities or individuals. The large-scale network is split into a number of fractions satisfying an edge threshold. In turn, the nodes in each fraction are merged to generate one or more clusters based on a specified similarity metric. The large-scale network is recursively split and clustered until distinct groups are identified.

Claims

1. A computer-implemented method to identify groups in large networks, the method comprising:

receiving a plurality of edges associated with the large networks;

splitting the plurality of edges into a collection of fractions;

generating one or more clusters from each fraction in the collection of fractions based on a similarity metric; and

identifying a set of groups across the one or more clusters.

2. The computer-implemented method of claim 1, wherein the large network is based on web pages associated with a social network service.

3. The computer-implemented method of claim 1, wherein the large network is based on contact lists utilized by a messaging service.

4. The computer-implemented method of claim 1, further comprising for each fraction, merging un-clustered nodes that share a specified number of neighbors.

5. The computer-implemented method of claim 1, further comprising for each fraction, merging un-clustered nodes that satisfy the similarity metric.

6. The computer-implemented method of claim 1, wherein a number of edges associated with each fraction of the collection of fractions is based on a memory threshold.

7. The computer-implemented method of claim 6, further comprising storing the number of edges associated with each fraction.

8. The computer-implemented method of claim 1, further comprising merging said one or more clusters that share one or more nodes.

9. The computer-implemented method of claim 8, wherein said merging includes merging two clusters having one or more edges between them and satisfying the similarity metric.

10. The computer-implemented method of claim 1, wherein the similarity metric, ω

(n1, n2), between nodes or clusters n1 and n2 is

$\mathrm{\omega <br><br>}<br><br>\left(n<br><br><br><br>1,n<br><br><br><br>2\right)=w_{n<br><br><br><br>1}<br><br>w_{n<br><br><br><br>2}+\frac{P_2}{2},$

wherein P₂ is the number of paths of length two between the two nodes or cluster n1 and n2, w_n1 is the weight of a first node or cluster, and w_n2 is the weight of a second node or cluster.

11. A computer-implemented method to identify groups in large networks, the method comprising:

receiving a plurality of nodes associated with the large networks, wherein the plurality of nodes are constrained to an edge threshold;

splitting the plurality of nodes into a collection of fractions;

storing edges associated with each fraction of the collection of fractions;

generating one or more clusters from each fraction in the collection of fractions based on a similarity metric; and

identifying a set of groups across the one or more clusters.

12. The computer-implemented method of claim 11, wherein the edge threshold is based on a memory threshold.

13. The computer-implemented method of claim 11, further comprising ignoring edges that are not within each fraction of the collection of fraction.

14. The computer-implemented method of claim 11, further comprising merging nodes that satisfy the similarity metric.

15. The computer-implemented method of claim 11, further comprising for each fraction storing edges between clusters and a count of edges within each cluster.

16. The computer-implemented method of claim 11, wherein identifying said set of groups across the one or more clusters stops when a ratio of the similarity between two or more clusters and a minimum number of edges within two or more clusters satisfies a specified threshold.

17. The computer-implemented method of claim 11, wherein the similarity metric, ω

(n1, n2), between nodes or clusters n1 and n2 is

$\mathrm{\omega <br><br>}<br><br>\left(n<br><br><br><br>1,n<br><br><br><br>2\right)=w_{n<br><br><br><br>1}<br><br>w_{n<br><br><br><br>2}+\frac{P_2}{2},$

wherein P₂ is the number of paths of length two between the two nodes or cluster n1 and n2, w_n1 is the weight of a first node or cluster, and w_n2 is the weight of a second node or cluster.

18. A computer system to generate hierarchical clusters, the system comprising:

a large network having edges and nodes;

a fractionation component to split the large network into a collection of fractions;

a clustering component to generate one or more clusters for each fraction of the collection of fractions based on a similarity metric; and

a presentation component to provide clusters associated with the large network.

19. The computer system of claim 18, wherein the clustering component is configured to form said one or more clusters by merging nodes that share a selected number of neighbors.

20. The computer system of claim 18, wherein the presentation component is configured to traverse said one or more clusters to respond to queries about relationships between at least a portion of said nodes in the large network.