Document Zbl 1365.68355

Glantz, Roland; Meyerhenke, Henning; Schulz, Christian

Tree-based coarsening and partitioning of complex networks. (English) Zbl 1365.68355

ACM J. Exp. Algorithm. 21, Article No. 1.6, 20 p. (2016).

MSC:

68R10	Graph theory (including graph drawing) in computer science
05C82	Small world graphs, complex networks (graph-theoretic aspects)
05C85	Graph algorithms (graph-theoretic aspects)

Keywords:

graph coarsening; complex networks; conductance; fundamental cuts; multilevel graph partitioning; spanning trees

Software:

SNAP

Cite Review PDF

Full Text: DOI arXiv

References:

[1]	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.
[2]	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. · Zbl 0959.68133
[3]	C. Bichot and P. Siarry (Eds.). 2011. Graph Partitioning. Wiley. · Zbl 1242.05002
[4]	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.
[5]	A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz. 2014. Recent Advances in Graph Partitioning. Technical Report arXiv:1311.3144.
[6]	J. Chen and I. Safro. 2011. Algebraic distance on graphs. SIAM J. Comput. 6 (2011), 3468-3490. · Zbl 1235.05042
[7]	C. Chevalier and I. Safro. 2009. Comparison of coarsening schemes for multi-level graph partitioning. In Proceedings of Learning and Intelligent Optimization.
[8]	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.
[9]	R. Diestel. 2012. Graph Theory (4th ed.). Graduate Texts in Mathematics, Vol. 173. Springer.
[10]	B. Fagginger Auer and R. Bisseling. 2013. Graph coarsening and clustering on the GPU. In Graph Partitioning and Graph Clustering. AMS and DIMACS. · Zbl 1271.68198
[11]	P. Felzenszwalb and D. Huttenlocher. 2004. Efficient graph-based image segmentation. Int. J. Comput. Vision 59, 2 (2004), 167-181. · Zbl 1477.68505
[12]	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. · Zbl 1196.68068
[13]	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. · Zbl 1288.68118
[14]	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.
[15]	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. · Zbl 1365.68355
[16]	L. Grady and E. Schwartz. 2006. Isoperimetric graph partitioning for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 28, 3 (2006), 469-475.
[17]	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. · Zbl 1017.68716
[18]	Bruce Hendrickson and Tamara G. Kolda. 2000. Graph partitioning models for parallel computing. Parallel Comput. 26, 12 (2000), 1519-1534. · Zbl 0948.68130
[19]	B. Hendrickson and R. Leland. 1995. A multi-level algorithm for partitioning graphs. In Proceedings of Supercomputing’95. ACM, 28 (CD). · Zbl 0816.68093
[20]	M. Holtgrewe, P. Sanders, and C. Schulz. 2010. Engineering a scalable high quality graph partitioner. In 24th International Parallel and Distributed Processing Symposium (IPDPS).
[21]	J. Hopcroft and R. Tarjan. 1973. Efficient algorithms for graph manipulation. Comm. ACM 16 (1973), 372-378.
[22]	D. Jungnickel. 2005. Graphs, Networks and Algorithms (2nd. ed.). Algorithms and Computation in Mathematics, Vol. 5. Springer, Berlin. · Zbl 1061.05001
[23]	R. Kannan, S. Vempala, and A. Vetta. 2004. On clusterings: Good, bad and spectral. J. ACM 51, 3 (2004), 497-515. · Zbl 1192.05160
[24]	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. · Zbl 0915.68129
[25]	W. Kropatsch. 1997. Equivalent contraction kernels to build dual irregular pyramids. Advances in Computer Science, Advances in Computer Vision (1997), pp. 99-107. · Zbl 0899.68105
[26]	J. Leskovec. 2014. Stanford Network Analysis Package (SNAP). (2014). http://snap.stanford.edu/index.html.
[27]	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. · Zbl 1203.68317
[28]	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.
[29]	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.
[30]	H. Meyerhenke, B. Monien, and S. Schamberger. 2009. Graph partitioning and disturbed diffusion. Parallel Comput. 35, 10-11 (2009), 544-569.
[31]	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. · Zbl 1360.90305
[32]	M. Newman. 2010. Networks: An Introduction. Oxford University Press, Inc., New York. · Zbl 1195.94003
[33]	V. Osipov and P. Sanders. 2010. N-Level graph partitioning. In Proceedings of the 18th European Symposium on Algorithms (ESA’10). 278-289. · Zbl 1287.05152
[34]	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. · Zbl 1295.68205
[35]	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.
[36]	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. · Zbl 1347.68355
[37]	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.
[38]	P. Sanders and C. Schulz. 2014. KaHIP—Karlsruhe High Qualtity Partitioning Homepage. (2014). http://algo2.iti.kit.edu/documents/kahip/index.html.
[39]	C. Schulz. 2013. Hiqh Quality Graph Partititioning. Ph.D. dissertation. Karlsruhe Institute of Technology.
[40]	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. · Zbl 1084.90049
[41]	D. Spielman and N. Srivastava. 2008. Graph sparsification by effective resistances. CoRR abs/0803.0929 (2008). http://arxiv.org/abs/0803.0929 · Zbl 1231.68184
[42]	R. Tarjan. 1972. Depth-first search and linear graph algorithms. J. Comput. 1 (1972), 146-160. · Zbl 0251.05107
[43]	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.

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.