Partitioning social networks

Details Partitioning social networks Partitioning social networks

2004-06-30

2010-02-23

Nguyen, Quang N. (Department: 2441)

Electrical computers and digital processing systems: multicomput

Computer network managing

Network resource allocating

C709S203000, C709S207000, C709S223000, C709S224000

Reexamination Certificate

active

07668957

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.

REFERENCES:
patent: 5627766 (1997-05-01), Beaven et al.
patent: 6411966 (2002-06-01), Kwan et al.
patent: 6507844 (2003-01-01), Leymann et al.
patent: 6766374 (2004-07-01), Trovato et al.
patent: 7185076 (2007-02-01), Novaes et al.
patent: 7478078 (2009-01-01), Lunt et al.
patent: 2002/0010783 (2002-01-01), Primak et al.
patent: 2002/0120744 (2002-08-01), Chellis et al.
patent: 2002/0133611 (2002-09-01), Gorsuch et al.
patent: 2002/0161896 (2002-10-01), Wen et al.
patent: 2002/0174234 (2002-11-01), Trovato et al.
patent: 2004/0041836 (2004-03-01), Zaner et al.
Tapas K. Das, et al., NetEffect: A Network Architecture for Large-scale Multi-user Virtual Worlds, ACM VRST '97, 1997, pp. 157-163, ACM, Lausanne, Switzerland.
Sean Rooney, et al., Automatic VLAN Creation Based on On-line Measurement, ACM SIGCOMM Computer Communication Review, 1999, pp. 50-57, ACM.
Harold E. Livings, et al., A Heuristic Teleprocessing Network Design Technique, Symposium on the Simulation of Computer Systems IV, 1976, pp. 71-82, IEEE.
Lili Qiu, et al., On Selfish Routing in Internet-Like Environments, SIGCOMM '03, 2003, pp. 151-162, ACM, Karlsruhe, Germany.
Anukool Lakhina, et al., Structural Analysis of Network Traffic Flows, SIGMETRICS/Performance '04, Jun. 12-16 2004, pp. 61-72, ACM, New York, NY.
ParMETIS: Parallel Graph Partitioning & Sparse Matrix Ordering, http://www-users.cs.umn.edu/˜karypis/metis/parmetis/index.html, Aug. 2003, 1 page.
George Karypis, et al., A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, 1998, pp. 1-28.
George Karypis, et al., Analysis of Multilevel Graph Partitioning, 1998, pp. 1-18.
George Karypis, et al., A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering, 1998, pp. 1-21.
George Karypis, et al., Multilevel k-way Partitioning Scheme for Irregular Graphs, 1998, pp. 1-25.
George Karypis, et al., Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs, 1998, pp. 1-23.
George Karypis, et al., A Coarse-Grain Parallel Formulation of Multilevel k-way Graph Partitioning Algorithm, 1997, pp. 1-12.
George Karypis, et al., Multilevel Hypergraph Partitioning: Applications in VLSI Domain, 1998, pp. 1-25.
Kirk Schloegel, et al., Multilevel Diffusion Schemes for Repartitioning of Adaptive Meshes, 1997, pp. 1-20.
Kirk Schloegel, et al.,A Performance Study of Diffusivevs,Remapped Load-Balancing Schemes, 1998, pp. 1-12.
George Karypis, et al., Multilevel Algorithms for Multi-Constraint Graph Partitioning, 1998, pp. 1-25.
Kirk Schloegel, et al., Wavefront Diffusion and LMSR: Algorithms for Dynamic Repartitioning of Adaptive Meshes, 1998, pp. 1-26.
George Karypis, et al., Multilevel k-way Hypergraph Partitioning, 1998, pp. 1-15.
Kirk Schloegel, et al., A New Algorithm for Multi-objective Graph Partitioning, 1999, pp. 1-10.
Kirk Schloegel, et al., Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning, 1999, pp. 1-21.
George Karypis, Multilevel Algorithms for Multi-Constraint Hypergraph Partitioning, 1999, pp. 1-10.
Kirk Schloegel, et al., Graph Partitioning for High Performance Scientific Simulations, 1999, pp. 1-39.
Kirk Schloegel, et al., A Unified Algorithm for Load-balancing Adaptive Scientific Simulations, 2000, pp. 1-11.
Irene Moulitsas, et al., Multilevel Algorithms for Generating Coarse Grids for Multigrid Methods, SC2001, 2001, pp. 1-10.
George Karypis, Multilevel Hypergraph Partitioning, 2002, pp. 1-30.
Cristinel Ababei, et al., Multi-objective Circuit Partitioning for Cutsize and Path-Based Delay Minimization, ICCAD 2002, 2002, 5 pages.
Navaratnasothie Selvakkumaran, et al., Perimeter-Degree: A Priori Metric for Directly Measuring and Homogenizing Interconnection Complexity in Multilevel Placement, SLIP '03, 2003, 8 pages, ACM, Monterey CA.
Navaratnasothie Selvakkumaran, et al., Multi-Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization, ICCAD 2003, 2003, 8 pages.
George Karypis, Multi-Constraint Mesh Partitioning for Contact/Impact Computations, 2003, pp. 1-14.
Navaratnasothie Selvakkumaran, et al., THETO—A Fast and High-Quality Partitioning Driven Global Placer, 2003, 6 pages.
Navaratnasothie Selvakkumaran, et al., Multi-Resource Aware Partitioning Algorithms for FPGAs with Heterogeneous Resources, 2003, 6 pages.
Kirk Schloegel, et al., Parallel Multilevel Diffusion Algorithms for Repartitioning of Adaptive Meshes, 1997, pp. 1-9.

Affiliated with

Also associated with

Rating

Partitioning social networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Partitioning social networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitioning social networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4178939