NODE CLUSTERING

• US 20120072554A1
• Filed: 09/20/2010
• Published: 03/22/2012
• Est. Priority Date: 09/20/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cao, Fei, Zhou, Shaoyu, Zhang, Sijian, Wu, Zhuoqing, Roy, Siddhartha, Elizarov, Michael A.
• Granted Patent: US 8,572,239 B2
• Time in Patent Office: Days
• US Class Current: 709/220
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data

Abstract

Large sets of unorganized data may provide little value in identifying useful observations from such data. For example, an online merchant may maintain a database of millions of user IDs (e.g., a cookie ID, a login ID, a device ID, a network ID, etc.) along with content viewed and/or actions taken with the user IDs, where minimal associations are known between user IDs. It may be advantageous to link together user IDs of respective users to capture a comprehensive view of respective users'"'"' activities. Accordingly, one or more systems and/or techniques for identifying a cluster of nodes based upon transforming a set of node pairings (e.g., pairings of related nodes) one or more times are disclosed herein. Iterative transformations may be performed until respective nodes are paired with merely their smallest neighboring node and are paired with no other node. In this way, node clusters may be identifiable.

Claims

1. A method for identifying one or more node clusters, comprising:

receiving a set of node pairings corresponding to a plurality of nodes, a node pairing comprising a first node connected to a second node; and

transforming the set of node pairings one or more times until one or more node clusters are identified from the plurality of nodes, where nodes within a node cluster are paired with a base node within the plurality of nodes by a single connection and are connected to no other nodes, the transforming comprising;

for respective current nodes paired with more than one neighboring node;

determining a reference node with which a current node is paired; and

for respective neighboring nodes paired with the current node;

disconnecting neighboring nodes, other than the reference node, from the current node and connecting the neighboring nodes to the reference node.

2. The method of claim 1, comprising:

assigning hash values to respective nodes within the plurality of nodes.

3. The method of claim 2, the reference node comprising a hash value smaller than a hash value of the current node.

4. The method of claim 3, the disconnecting comprising:

if the hash value of the reference node is larger than or equal to the hash value of the current node, then refraining from disconnecting neighboring nodes from the current node and connecting the neighboring nodes to the reference node.

5. The method of claim 2, the base node of the node cluster comprising a smaller hash value than respective hash values of nodes within the node cluster.

6. The method of claim 2, a node pairing comprising:

a first node corresponding to a user ID and a second node corresponding to an IP address, or

a first node corresponding to an IP address and a second node corresponding to a user ID.

7. The method of claim 1, the transforming of current nodes performed in parallel.

8. The method of claim 1, nodes within the plurality of nodes representing individuals, and connections between nodes representing relationships.

9. The method of claim 1, comprising:

identifying a second node cluster from the plurality of nodes, where nodes within the second node cluster are paired with a second base node within the plurality of nodes by a single connection and are connected to no other nodes.

10. The method of claim 1, a node within the node cluster comprising a symmetric and transitive relationship with respective nodes within the node cluster.

11. The method of claim 1, comprising:

referencing the cluster based upon the base node.

12. The method of claim 1, the cluster corresponding to an individual and nodes within the cluster representing descriptive data corresponding to the individual.

13. A system for identifying one or more node clusters, comprising:

a transformation module configured to;

receive a set of node pairings corresponding to a plurality of nodes, a node pairing comprising a first node connected to a second node;

transform the set of node pairings one or more times until one or more node clusters are identified from the plurality of nodes, where nodes within a node cluster are paired with a base node within the plurality of nodes by a single connection and are connected to no other nodes, a transformation comprising;

for respective current nodes paired with more than one neighboring node;

determine a reference node with which a current node is paired; and

for respective neighboring nodes paired with the current node;

 

disconnect neighboring nodes, other than the reference node, from the current node and connect the neighboring nodes to the reference node.

14. The system of claim 13, comprising:

a hashing module configured to;

assign hash values to respective nodes within the plurality of nodes.

15. The system of claim 14, the reference node comprising a hash value smaller than a hash value of the current node.

16. The system of claim 15, the transformation module configured to:

refrain from disconnecting neighboring nodes from the current node and connecting the neighboring nodes to the reference node if the hash value of the reference node is larger than or equal to the hash value of the current node.

17. The system of claim 14, the base node comprising a hash value smaller than respective hash values of nodes within the cluster.

18. The system of claim 13, the transformation module configured to:

transform current nodes in parallel.

19. The system of claim 13, the transformation module configured to:

identify a second node cluster from the plurality of nodes, where nodes within the second node cluster are paired with a second base node within the plurality of nodes by a single connection and are connected to no other nodes.

20. A method for identifying a cluster of nodes, comprising:

receiving a set of node pairings corresponding to a plurality of nodes, a node pairing comprising a first node connected to a second node, nodes within the plurality of nodes comprising hash values; and

transforming the set of node pairings one or more times until one or more node clusters are identified from the plurality of nodes, where nodes within a node cluster are paired with a base node within the plurality of nodes by a single connection and are connected to no other nodes, the base node comprising a hash value smaller than respective hash values of nodes within the node cluster, the transforming comprising;

for respective current nodes paired with more than one neighboring node;

determining a reference node with which a current node is paired, the reference node comprising a hash value smaller than respective hash values of neighboring nodes paired with the current node; and

if the hash value of the reference node is smaller than a hash value of the current node, then for respective neighboring nodes paired with the current node;

disconnecting neighboring nodes, other than the reference node, from the current node and connecting the neighboring nodes to the reference node.