Group identification in large-scaled networks via hierarchical clustering through refraction over edges of networks
AssigneeMicrosoft Corporation
InventorsJeremy Tantrum, Heng Zhang, Teresa B. Mah, Benyu Zhang, Abhinai Srivastava
Life of this patent
Estimating the term…
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.
Claims20
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, while refractioning and reclustering, one or more clusters from each fraction in the collection of fractions based on a similarity metric, wherein the similarity metric, ω(n1, n2), between nodes or clusters n1 and n2 is
- ω
-
- (
- n
-
-
- 1
- ,
- n
-
-
- 2
- )
- =
- w
- n
-
-
- 1
-
- w
- n
-
-
- 2
- +
- P
- 2
- 2
- ,
- wherein P2 is the number of paths of length two between the two nodes or cluster n1 and n2, wn1 is the weight of a first node or cluster, wn2 is the weight of a second node or cluster, and the weight is a count of the nodes in n1 or n2;
- and
- identifying a set of groups across the one or more clusters having nodes corresponding to a subset of the plurality of edges associated with the large networks.
A computer system to identify groups in large networks, the system comprising:
- a fractionation component that is configured to receive a plurality of edges associated with the large networks and to split the plurality of edges into a collection of fractions;
- a clustering component is configured to receive the collection of fractions and to generate, while refractioning and reclustering, one or more nodes or clusters from each fraction in the collection of fractions based on a similarity metric, wherein the similarity metric, ω(n1, n2), between nodes or clusters n1 and n2 is
- ω
-
- (
- n
-
-
- 1
- ,
- n
-
-
- 2
- )
- =
- w
- n
-
-
- 1
-
- w
- n
-
-
- 2
- +
- P
- 2
- 2
- ,
- wherein P2 is the number of paths of length two between the two nodes or cluster n1 and n2, wn1 is the weight of a first node or cluster, wn2 is the weight of a second node or cluster, and the weight is the number of nodes in n1 or n2;
- and
- the cluster component is configured to identify a set of groups across the one or more clusters having nodes corresponding to a subset of the plurality of edges associated with the large networks.
A computer system having multiple processors and memories configured to identify groups in large networks, a number of available processors among multiple processors determines a number of fractions supported by the computer system and the available memory associated with each available processor determines a number of edges or nodes stored in each of the fractions, the system further comprising:
- a fractionation component that is configured to receive a plurality of edges associated with the large networks and to split the plurality of edges into a collection of fractions;
- a clustering component is configured to receive the collection of fractions and to generate, while refractioning and reclustering, one or more nodes or clusters from each fraction in the collection of fractions based on a similarity metric, wherein the similarity metric, ω(n1, n2), between nodes or clusters n1 and n2 is
- ω
-
- (
- n
-
-
- 1
- ,
- n
-
-
- 2
- )
- =
- w
- n
-
-
- 1
-
- w
- n
-
-
- 2
- +
- P
- 2
- 2
- ,
- wherein P2 is the number of paths of length two between the two nodes or cluster n1 and n2, wn1 is the weight of a first node or cluster, wn2 is the weight of a second node or cluster, and the weight is the number of nodes in n1 or n2;
- and
- the cluster component is configured to identify a set of groups across the one or more clusters having nodes corresponding to a subset of the plurality of edges associated with the large networks.
Dependencies are inferred from the claim text.