Partitioning social networks

• US 7,668,957 B2
• Filed: 06/30/2004
• Issued: 02/23/2010
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Achlioptas, Dimitris, McSherry, Frank D
• Primary Examiner(s): Nguyen; Quang N.
• Application Number:
  US10/882,020
• Publication Number:
  US 20060015588A1
• Time in Patent Office: 2,064 Days
• Field of Search: 709/203, 709/223, 709/224, 709/226, 709/227, 709/228, 709/231
• US Class Current: 709/226
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

The present invention provides a unique system and method that facilitates reducing network traffic between a plurality of servers located on a social-based network. The system and method involve identifying a plurality of vertices or service users on the network with respect to their server or network locations. The vertices'"'"' contacts or connections can be located or determined as well. In order to minimize communication traffic, the vertices and their connections with respect to their respective server locations can be analyzed to determine whether at least a subset of nodes should be moved or relocated to another server to facilitate mitigating network traffic while balancing user load among the various servers or parts of the network. Thus, an underlying social network can be effectively partitioned. In addition, the network can be parsed into a collection of nested layers, whereby each successively less dense layer can be partitioned with respect to the previous (partitioned) more dense layer.

Claims

1. A system that facilitates social network management, comprising:

a memory;

a processing unit coupled to the memory;

a node identification component residing within the processing unit, that identifies one or more nodes associated with at least one social network that is managed by a plurality of servers;

a clustering component residing within the processing unit, that aggregates at least a subset of nodes associated with the social network and dedicates a subset of servers to respective subsets of nodes;

the clustering component that determines whether to move at least one node from a current server to a proposed server based at least in part upon comparing a number of connections between vertices with server size;

“

edge gain” and

“

size gain”

are arbitrary functions of quantities e1, e2 and s1, s2, wherein e1 is a number of contacts a node has on a first cluster, e2 is a number of contacts the node has on a second cluster, s1 is the size of the first cluster—

not including the node under consideration, and s2 is the size of the second cluster; and

the clustering component determines to move the node if and only if A*(e2−

e1)>

s2−

s1, wherein A is an amplification factor.

2. The system of claim 1, the node identification component further identifies one or more connections between any two nodes comprising a first node and at least a second node on the social network.

3. The system of claim 2, the clustering component further identifies one or more servers designated to the first node and the second node to determine whether to aggregate the first node and the second node on a similar server.

4. The system of claim 1, the first and second clusters map to first and second servers, respectively.

5. The system of claim 1, the clustering component that identifies a decreasing sequence of subsets of vertices, where subset q corresponds to the vertices in a q-core of the graph to facilitate determining a sequence of strata.

6. The system of claim 5, wherein the strata comprise at least one of a 1-core, 2-core, 3-core, and/or up to a k-core, wherein k is an integer greater than or equal to one.

7. The system of claim 1, further comprising a computer readable medium having stored thereon the computer executable components of claim 1 on a disk storage of a computer.