Optima Network Science Seminar
Faculty Advisor: My T. Thai
Coordinator: Thang N. Dinh
Time and place: 1:50pm Wed, E520A CSE Building
Note:
If you are
interested in participating in the activities of the seminar and/or wish to
receive emails about
upcoming events please send an email to tdinh@cise.ufl.edu.
by Huiyuan on Feb 20
Partitioning graphs at scale is a key challenge for any application that involves distributing a graph across disks, machines, or data centers. Graph partitioning is a very well studied problem with a rich literature, but existing algorithms typically can not scale to billions of edges, or can not provide guarantees about partition sizes. In this work we introduce an efficient algorithm, balanced label propagation, for precisely partitioning massive graphs while greedily maximizing edge locality, the number of edges that are assigned to the same shard of a partition. By combining the computational e ffciency of label propagation--where nodes are interactively relabeled to the same `label' as the plurality of their graph neighbors--with the guarantees of constrained optimization | guiding the propagation by a linear program constraining the partition sizes--our algorithm makes it practically possible to partition graphs with billions of edges. Our algorithm is motivated by the challenge of performing graph predictions in a distributed system. Because this requires assigning each node in a graph to a physical machine with memory limitations, it is critically necessary to ensure the resulting partition shards do not overload any single machine. We evaluate our algorithm for its partitioning performance on the Facebook social graph, and also study its performance when partitioning Facebook's `People You May Know' service (PYMK), the distributed system responsible for the feature extraction and ranking of the friends-of-friends of all active Facebook users. In a live deployment, we observed average query times and average network tra c levels that were 50.5% and 37.1% (respectively) when compared to the previous naive random sharding.
Balanced Label Propagation for Partitioning Massive Graphs
Johan Ugander, Lars Backstrom, In WSDM 2013 (Best Student Paper) [PDF]
AbstractPartitioning graphs at scale is a key challenge for any application that involves distributing a graph across disks, machines, or data centers. Graph partitioning is a very well studied problem with a rich literature, but existing algorithms typically can not scale to billions of edges, or can not provide guarantees about partition sizes. In this work we introduce an efficient algorithm, balanced label propagation, for precisely partitioning massive graphs while greedily maximizing edge locality, the number of edges that are assigned to the same shard of a partition. By combining the computational e ffciency of label propagation--where nodes are interactively relabeled to the same `label' as the plurality of their graph neighbors--with the guarantees of constrained optimization | guiding the propagation by a linear program constraining the partition sizes--our algorithm makes it practically possible to partition graphs with billions of edges. Our algorithm is motivated by the challenge of performing graph predictions in a distributed system. Because this requires assigning each node in a graph to a physical machine with memory limitations, it is critically necessary to ensure the resulting partition shards do not overload any single machine. We evaluate our algorithm for its partitioning performance on the Facebook social graph, and also study its performance when partitioning Facebook's `People You May Know' service (PYMK), the distributed system responsible for the feature extraction and ranking of the friends-of-friends of all active Facebook users. In a live deployment, we observed average query times and average network tra c levels that were 50.5% and 37.1% (respectively) when compared to the previous naive random sharding.