Roland Glantz
Abstract
A hierarchy of increasingly coarse versions of a network allows one to represent the network on multiple scales at the same time. Often, the elementary operation for generating a hierarchy on a network is merging adjacent vertices, an operation that can be realized through contracting the edge between the two vertices. Such a hierarchy is defined by the selection of the edges to be contracted between a level and the next coarser level. The selection may involve (i) rating the edges, (ii) constraining the selection (e.g., that the selected edges form a matching), as well as (iii) maximizing the total rate of the selected edges under the constraints. Hierarchies of this kind are, among others, involved in multilevel methods for partitioning networks—a prerequisite for processing in parallel with distributed memory.
In this article, we propose a new edge rating by (i) defining weights for the edges of a network that express the edges’ importance for connectivity via shortest paths, (ii) computing a minimum weight spanning tree with respect to these weights, and (iii) rating the network edges based on the conductance values of the tree’s fundamental cuts.
To make the computation of our new edge rating efficient, we develop the first optimal linear-time algorithm to compute the conductance values of all fundamental cuts of a given spanning tree. We integrate the new edge rating into a leading multilevel graph partitioner and equip the latter also with a new greedy postprocessing for optimizing the Maximum Communication Volume (MCV) of a partition.
Our experiments, in which we bipartition frequently used benchmark networks, show that the postprocessing reduces MCV by 11.3%. Our new edge rating, here used for matching-based coarsening, further reduces MCV by 10.3% compared to the previously best rating with MCV postprocessing in place for both ratings. In total, with a modest increase in running time, our new approach reduces the MCV of complex network partitions by 20.4%.
Supplemental Material
Available for Download
Supplemental movie, appendix, image and software files for, Tree-Based Coarsening and Partitioning of Complex Networks
- D. Bader, H. Meyerhenke, P. Sanders, and D. Wagner (Eds.). 2013. Graph Partitioning and Graph Clustering—10th DIMACS Impl. Challenge. Contemporary Mathematics, Vol. 588. AMS. 19--36.Google Scholar
- M. Bender and M. Farach-Colton. 2000. The LCA problem revisited. In Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN’00). Springer-Verlag, 88--94. Google ScholarDigital Library
- C. Bichot and P. Siarry (Eds.). 2011. Graph Partitioning. Wiley.Google Scholar
- T. N. Bui and C. Jones. 1993. A heuristic for reducing fill in sparse matrix factorization. In 6th SIAM Conference on Parallel Processing for Scientific Computing (PPSC). 445--452.Google Scholar
- A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz. 2014. Recent Advances in Graph Partitioning. Technical Report arXiv:1311.3144.Google Scholar
- J. Chen and I. Safro. 2011. Algebraic distance on graphs. SIAM J. Comput. 6 (2011), 3468--3490. Google ScholarDigital Library
- C. Chevalier and I. Safro. 2009. Comparison of coarsening schemes for multi-level graph partitioning. In Proceedings of Learning and Intelligent Optimization. Google ScholarDigital Library
- L. Costa, O. Oliveira, Jr., G. Travieso, F. Rodrigues, P. Villas Boas, L. Antiqueira, Matheus P. Viana, and L. Correa Rocha. 2011. Analyzing and modeling real-world phenomena with complex networks: A survey of applications. Adv. Phys. 60, 3 (2011), 329--412.Google ScholarCross Ref
- R. Diestel. 2012. Graph Theory (4th ed.). Graduate Texts in Mathematics, Vol. 173. Springer.Google Scholar
- B. Fagginger Auer and R. Bisseling. 2013. Graph coarsening and clustering on the GPU. In Graph Partitioning and Graph Clustering. AMS and DIMACS.Google Scholar
- P. Felzenszwalb and D. Huttenlocher. 2004. Efficient graph-based image segmentation. Int. J. Comput. Vision 59, 2 (2004), 167--181. Google ScholarDigital Library
- J. Fischer and V. Heun. 2006. Theoretical and practical improvements on the RMQ-problem with applications to LCA and LCE. In Proceedings of the 16th Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 4009. Springer, 36--48. Google ScholarDigital Library
- W. Fung, R. Hariharan, N. Harvey, and D. Panigrahi. 2011. A general framework for graph sparsification. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC’11). ACM, 71--80. Google ScholarDigital Library
- M. Garey, D. Johnson, and L. Stockmeyer. 1974. Some simplified NP-Complete problems. In Proceedings of the 6th ACM Symposium on Theory of Computing (STOC’74). ACM, 47--63. Google ScholarDigital Library
- R. Glantz, H. Meyerhenke, and C. Schulz. 2014. Tree-based coarsening and partitioning of complex networks. In 13th International Symposium on Experimental Algorithms, (SEA 2014), J. Gudmundson and J. Katajainen (Eds.). Springer, 364--375. Google ScholarDigital Library
- L. Grady and E. Schwartz. 2006. Isoperimetric graph partitioning for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 28, 3 (2006), 469--475. Google ScholarDigital Library
- Y. Haxhimusa, R. Glantz, M. Saib, G. Langs, and W. Kropatsch. 2002. Logarithmic tapering graph pyramid. In Proceedings of the DAGM Symposium 2002, Lecture Notes in Computer Science, Vol. 2449, Luc Van Gool (Ed.). Springer, 117--124. Google ScholarDigital Library
- Bruce Hendrickson and Tamara G. Kolda. 2000. Graph partitioning models for parallel computing. Parallel Comput. 26, 12 (2000), 1519--1534. Google ScholarDigital Library
- B. Hendrickson and R. Leland. 1995. A multi-level algorithm for partitioning graphs. In Proceedings of Supercomputing’95. ACM, 28 (CD). Google ScholarDigital Library
- M. Holtgrewe, P. Sanders, and C. Schulz. 2010. Engineering a scalable high quality graph partitioner. In 24th International Parallel and Distributed Processing Symposium (IPDPS).Google Scholar
- J. Hopcroft and R. Tarjan. 1973. Efficient algorithms for graph manipulation. Comm. ACM 16 (1973), 372--378. Google ScholarDigital Library
- D. Jungnickel. 2005. Graphs, Networks and Algorithms (2nd. ed.). Algorithms and Computation in Mathematics, Vol. 5. Springer, Berlin. Google ScholarDigital Library
- R. Kannan, S. Vempala, and A. Vetta. 2004. On clusterings: Good, bad and spectral. J. ACM 51, 3 (2004), 497--515. Google ScholarDigital Library
- G. Karypis and V. Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 1 (1998), 359--392. Google ScholarDigital Library
- W. Kropatsch. 1997. Equivalent contraction kernels to build dual irregular pyramids. Advances in Computer Science, Advances in Computer Vision (1997), pp. 99--107.Google ScholarCross Ref
- J. Leskovec. 2014. Stanford Network Analysis Package (SNAP). (2014). http://snap.stanford.edu/index.html.Google Scholar
- J. Maue and P. Sanders. 2007. Engineering algorithms for approximate weighted matching. In Proceedings of the 6th International Workshop on Experimental Algorithms (WEA’07), Lecture Notes in Computer Science, Vol. 4525. Springer-Verlag, 242--255. Google ScholarDigital Library
- C. Mavroforakis, R. Garcia-Lebron, I. Koutis, and E. Terzi. 2015. Spanning edge centrality: Large-scale computation and applications. In Proceedings of the 24th International World Wide Web Conference (WWW 2015). International World Wide Web Conferences Steering Committee (IW3C2), ACM. Google ScholarDigital Library
- H. Meyerhenke, B. Monien, and S. Schamberger. 2006. Accelerating shape optimizing load balancing for parallel FEM simulations by algebraic multigrid. In Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS). 57. Google ScholarDigital Library
- H. Meyerhenke, B. Monien, and S. Schamberger. 2009. Graph partitioning and disturbed diffusion. Parallel Comput. 35, 10--11 (2009), 544--569. Google ScholarDigital Library
- H. Meyerhenke, P. Sanders, and C. Schulz. 2014. Partitioning complex networks via size-constrained clustering. In 13th International Symposium on Experimental Algorithms (SEA’14), J. Gudmundson and J. Katajainen (Eds.). Springer, 351--363. Google ScholarDigital Library
- M. Newman. 2010. Networks: An Introduction. Oxford University Press, Inc., New York. Google ScholarCross Ref
- V. Osipov and P. Sanders. 2010. N-Level graph partitioning. In Proceedings of the 18th European Symposium on Algorithms (ESA’10). 278--289. Google ScholarDigital Library
- D. Pritchard and R. Thurimella. 2011. Fast computation of small cuts via cycle space sampling. ACM Trans. Algorithms 7, 4 (2011), 46:1--46:30. Google ScholarDigital Library
- U. Raghavan, R. Albert, and S. Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76, 3 (2007), 036106.Google ScholarCross Ref
- I. Safro, P. Sanders, and C. Schulz. 2012. Advanced coarsening schemes for graph partitioning. In Proceedings of the 11th International Symposium on Experimental Algorithms. Springer, 369--380. Google ScholarDigital Library
- P. Sanders and C. Schulz. 2013. Think locally, act globally: Highly balanced graph partitioning. In Proceedings of the 12th International Symposium on Experimental Algorithms. Springer, 164--175.Google Scholar
- P. Sanders and C. Schulz. 2014. KaHIP—Karlsruhe High Qualtity Partitioning Homepage. (2014). http://algo2.iti.kit.edu/documents/kahip/index.html.Google Scholar
- C. Schulz. 2013. Hiqh Quality Graph Partititioning. Ph.D. dissertation. Karlsruhe Institute of Technology.Google Scholar
- A. Soper, C. Walshaw, and M. Cross. 2004. A combined evolutionary search and multilevel optimisation approach to graph partitioning. J. Global Opt. 29, 2 (2004), 225--241. Google ScholarDigital Library
- D. Spielman and N. Srivastava. 2008. Graph sparsification by effective resistances. CoRR abs/0803.0929 (2008). http://arxiv.org/abs/0803.0929Google Scholar
- R. Tarjan. 1972. Depth-first search and linear graph algorithms. J. Comput. 1 (1972), 146--160.Google Scholar
- J. Wassenberg, W. Middelmann, and P. Sanders. 2009. An efficient parallel algorithm for graph-based image segmentation. In Proceedings of the 13th International Conference on Computer Analysis of Images and Patterns. 1003--1010. Google ScholarDigital Library
Recommendations
Tree-Based Coarsening and Partitioning of Complex Networks
Proceedings of the 13th International Symposium on Experimental Algorithms - Volume 8504Many applications produce massive complex networks whose analysis would benefit from parallel processing. Parallel algorithms, in turn, often require a suitable network partition. For solving optimization tasks such as graph partitioning on large ...
Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering
The most commonly used method to tackle the graph partitioning problem in practice is the multilevel metaheuristic. In this paper we introduce size-constrained label propagation (SCLaP) and show how it can be used to instantiate both the coarsening ...
Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning
Multilevel partitioning methods that are inspired by principles of multiscaling are the most powerful practical hypergraph partitioning solvers. Hypergraph partitioning has many applications in disciplines ranging from scientific computing to data science. ...
Comments