Name
Abstract | ||
|---|---|---|
An important objective for analyzing real-world graphs is to achieve scalable performance on large, streaming graphs. A challenging and relevant example is the graph partition problem. As a combinatorial problem, graph partition is NP-hard, but existing relaxation methods provide reasonable approximate solutions that can be scaled for large graphs. Competitive benchmarks and challenges have proven to be an effective means to advance state-of-the-art performance and foster community collaboration. This paper describes a graph partition challenge with a baseline partition algorithm of sub-quadratic complexity. The algorithm employs rigorous Bayesian inferential methods based on a statistical model that captures characteristics of the real-world graphs. This strong foundation enables the algorithm to address limitations of well-known graph partition approaches such as modularity maximization. This paper describes various aspects of the challenge including: (1) the data sets and streaming graph generator, (2) the baseline partition algorithm with pseudocode, (3) an argument for the correctness of parallelizing the Bayesian inference, (4) different parallel computation strategies such as node-based parallelism and matrix-based parallelism, (5) evaluation metrics for partition correctness and computational requirements, (6) preliminary timing of a Python-based demonstration code and the open source C++ code, and (7) considerations for partitioning the graph in streaming fashion. Data sets and source code for the algorithm as well as metrics, with detailed documentation are available at GraphChallenge.org. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/HPEC.2017.8091040 | 2017 IEEE High Performance Extreme Computing Conference (HPEC) |
Keywords | DocType | Volume |
graph partition problem,combinatorial problem,graph partition challenge,baseline partition algorithm,real-world graphs,data sets,streaming graph generator,parallelism,streaming fashion,stochastic block partition,relaxation methods,approximate solutions,community collaboration,parallel computation strategies,Bayesian inferential methods | Journal | abs/1708.07883 |
ISSN | ISBN | Citations |
2377-6943 | 978-1-5386-3473-8 | 25 |
PageRank | References | Authors |
1.29 | 14 | 12 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Edward K. Kao | 1 | 123 | 10.06 |
| Vijay Gadepally | 2 | 449 | 50.53 |
| Michael B. Hurley | 3 | 93 | 6.44 |
| Michael J. Jones | 4 | 11341 | 927.21 |
| Jeremy Kepner | 5 | 606 | 61.58 |
| Sanjeev Mohindra | 6 | 76 | 5.38 |
| Paul Monticciolo | 7 | 73 | 4.19 |
| Albert Reuther | 8 | 335 | 37.32 |
| Siddharth Samsi | 9 | 201 | 24.09 |
| William Song | 10 | 79 | 4.61 |
| Diane Staheli | 11 | 104 | 8.96 |
| Steven Smith | 12 | 75 | 4.23 |