Memetic graph clustering. (English) Zbl 07286676

D’Angelo, Gianlorenzo (ed.), 17th symposium on experimental algorithms, SEA 2018, June 27–29, 2018, L’Aquila, Italy. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 103, Article 3, 15 p. (2018).
Summary: It is common knowledge that there is no single best strategy for graph clustering, which justifies a plethora of existing approaches. In this paper, we present a general memetic algorithm, VieClus, to tackle the graph clustering problem. This algorithm can be adapted to optimize different objective functions. A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high-quality solutions in a short amount of time. We instantiate our scheme with local search for modularity and show that our algorithm successfully improves or reproduces all entries of the 10th DIMACS implementation challenge under consideration using a small amount of time.
For the entire collection see [Zbl 1390.68017].


68Wxx Algorithms in computer science


Full Text: DOI arXiv


[2] L. Akoglu, H. Tong, and D. Koutra.Graph Based Anomaly Detection and Description: A Survey.{\it Data Min. Knowl. Discov.}, 29(3):626-688, may 2015.doi:10.1007/ s10618-014-0365-y.
[3] D. Aloise, G. Caporossi, S. Perron, P. Hansen, L. Liberti, and M. Ruiz. Modularity Maximization in Networks by Variable Neighborhood Search. In {\it 10th DIMACS Impl. Challenge} {\it Workshop}. Georgia Inst. of Technology, Atlanta, GA, 2012.
[4] :15
[5] V. Arnau, S. Mars, and I. Marín. Iterative Cluster Analysis of Protein Interaction Data. {\it Bioinformatics}, 21(3):364-378, 2004.
[6] :14
[7] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. {\it Complexity and Approximation: Combinatorial Optimization Problems and their Approx-} {\it imability Properties}. Springer Science & Business Media, 2012.
[8] T. Bäck. {\it Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolu-} {\it tionary Programming, Genetic Algorithms}. PhD thesis, Informatik Centrum Dortmund, Germany, 1996.
[9] D. Bader, A. Kappes, H. Meyerhenke, P. Sanders, C. Schulz, and D. Wagner. Benchmarking for Graph Clustering and Partitioning. In {\it Encyclopedia of Social Network Analysis and} {\it Mining}. Springer, 2014.
[10] D. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, editors. {\it Proc. of the 10th DIMACS} {\it Impl. Challenge}, Cont. Mathematics. AMS, 2012.
[11] S. Biedermann. Evolutionary Graph Clustering. Bachelor’s Thesis, Universität Wien, 2017.
[12] S. Biedermann, M. Henzinger, C. Schulz, and B. Schuster. Memetic Graph Clustering (see ArXiv preprint arXiv:1802.07034). {\it Technical Report. arXiv:1802.07034}, 2018.
[13] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre.Fast Unfolding of Communities in Large Networks. {\it Journal of Statistical Mechanics: Theory and Experi-} {\it ment}, 2008(10):P10008, 2008. URL: http://stacks.iop.org/1742-5468/2008/i=10/a= P10008.
[14] U. Brandes. {\it Network Analysis: Methodological Foundations}, volume 3418. Springer Science & Business Media, 2005.
[15] U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner. On Modularity Clustering. {\it IEEE Transactions on Knowledge and Data Engineering}, 20(2):172- 188, 2008.
[16] U. Brandes, M. Gaertler, and D. Wagner. Engineering Graph Clustering: Models and Experimental Evaluation. {\it ACM Journal of Experimental Algorithmics}, 12(1.1):1-26, 2007.
[17] Ü. V. Çatalyürek, K. Kaya, J. Langguth, and B. Uçar. A Divisive Clustering Technique for Maximizing the Modularity. In {\it 10th DIMACS Impl. Challenge Workshop}. Georgia Inst. of Technology, Atlanta, GA, 2012.
[18] J. Demme and S. Sethumadhavan. Approximate Graph Clustering for Program Characterization. {\it ACM Trans. Archit. Code Optim.}, 8(4):21:1-21:21, 2012. doi:10.1145/2086696. 2086700.
[19] I. Derényi, G. Palla, and T. Vicsek. Clique Percolation in Random Networks. {\it Physical} {\it review letters}, 94(16):160202, 2005.
[20] A. A. Diwan, S. Rane, S. Seshadri, and S. Sudarshan. Clustering Techniques for Minimizing External Path Length. In {\it Proceedings of the 22th International Conference on Very Large} {\it Data Bases}, VLDB ’96, pages 342-353, San Francisco, CA, USA, 1996. Morgan Kaufmann Publishers Inc. URL: http://dl.acm.org/citation.cfm?id=645922.673636.
[21] D. Džamić, D. Aloise, and N. Mladenović. Ascent-descent Variable Neighborhood Decomposition Search for Community Detection by Modularity Maximization. {\it Annals of} {\it Operations Research}, Jun 2017. doi:10.1007/s10479-017-2553-9.
[22] G. W. Flake, R. E. Tarjan, and K. Tsioutsiouliklis. Graph Clustering and Minimum Cut Trees. {\it Internet Mathematics}, 1(4):385-408, 2004.
[23] S. Fortunato. Community Detection in Graphs. {\it Physics reports}, 486(3):75-174, 2010.
[24] D. E. Goldberg.{\it Genetic Algorithms in Search, Optimization, and Machine Learning}. Addison-Wesley, 1989.
[25] M. Hamann, B. Strasser, D. Wagner, and T. Zeitz. Simple Distributed Graph Clustering using Modularity and Map Equation. {\it arXiv preprint arXiv:1710.09605}, 2017.
[26] T. Hartmann, A. Kappes, and D. Wagner. Clustering Evolving Networks. In {\it Algorithm} {\it Engineering}, pages 280-329. Springer, 2016.
[27] R. Kannan, S. Vempala, and A. Vetta. On clusterings: Good, bad and spectral. {\it Journal} {\it of the ACM (JACM)}, 51(3):497-515, 2004.
[28] J. Kim, I. Hwang, Y. H. Kim, and B. R. Moon. Genetic Approaches for Graph Partitioning: A Survey. In {\it Proceedings of the 13th Annual Genetic and Evolutionary Computation} {\it Conference (GECCO’11)}, pages 473-480. ACM, 2011. doi:10.1145/2001576.2001642.
[29] D. LaSalle. Graph Partitioning, Ordering, and Clustering for Multicore Architectures, 2015.
[30] M. Lipczak and E. E. Milios. Agglomerative Genetic Algorithm for Clustering in Social Networks. In Franz Rothlauf, editor, {\it GECCO}, pages 1243-1250. ACM, 2009. URL: http: //dblp.uni-trier.de/db/conf/gecco/gecco2009.html#LipczakM09.
[31] H. Lu, M. Halappanavar, and A. Kalyanaraman. Parallel heuristics for scalable community detection. {\it Parallel Computing}, 47:19-37, 2015.
[32] S. McFarling. Program Optimization for Instruction Caches. {\it SIGARCH Comput. Archit.} {\it News}, 17(2):183-191, 1989. doi:10.1145/68182.68200.
[33] H. Meyerhenke, P. Sanders, and C. Schulz.Partitioning Complex Networks via SizeConstrained Clustering. In {\it SEA}, volume 8504 of {\it Lecture Notes in Computer Science}, pages 351-363. Springer, 2014.
[34] B. L Miller and D. E Goldberg. Genetic Algorithms, Tournament Selection, and the Effects of Noise. {\it Evolutionary Computation}, 4(2):113-131, 1996.
[35] M. E. J. Newman.Properties of Highly Clustered Networks.{\it Physical Review E}, 68(2):026121, 2003.
[36] M. E. J. Newman and M. Girvan. Finding and Evaluating Community Structure in Networks. {\it Physical review E}, 69(2):026113, 2004.
[37] M. Ovelgönne and A. Geyer-Schulz. An Ensemble Learning Strategy for Graph Clustering. In {\it Graph Partitioning and Graph Clustering}, number 588 in Contemporary Mathematics, 2013.
[38] J. B. Pereira-Leal, A. J. Enright, and C. A. Ouzounis. Detection of Functional Modules from Protein Interaction Networks. {\it Proteins: Structure, Function, and Bioinformatics}, 54(1):49-57, 2004. doi:10.1002/prot.10505.
[39] D. C. Porumbel, J.-K. Hao, and P. Kuntz. Spacing Memetic Algorithms. In {\it 13th Annual} {\it Genetic and Evolutionary Computation Conference, GECCO 2011, Proceedings, Dublin,} {\it Ireland, July 12-16, 2011}, pages 1061-1068, 2011.
[40] U. N. Raghavan, R. Albert, and S. Kumara.Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks. {\it Physical Review E}, 76(3), 2007.
[41] M. Rosvall, D. Axelsson, and C. T. Bergstrom. The Map Equation. {\it The European Physical} {\it Journal-Special Topics}, 178(1):13-23, 2009.
[42] S. Ryu and D. Kim. Quick Community Detection of Big Graph Data Using Modified Louvain Algorithm. In {\it High Performance Computing and Communications; IEEE 14th} {\it International Conference on Smart City; IEEE 2nd International Conference on Data Sci-} {\it ence and Systems (HPCC/SmartCity/DSS), 2016 IEEE 18th International Conference on}, pages 1442-1445. IEEE, 2016.
[43] P. Sanders and C. Schulz. Distributed Evolutionary Graph Partitioning. In {\it Proc. of the} {\it 12th Workshop on Algorithm Engineering and Experimentation (ALENEX’12)}, pages 16-29, 2012.
[44] P. Sanders and C. Schulz. Think Locally, Act Globally: Highly Balanced Graph Partitioning. In {\it 12th International Symposium on Experimental Algorithms (SEA’13)}. Springer, 2013.
[45] S. E. Schaeffer. Survey: Graph Clustering. {\it Comput. Sci. Rev.}, 1(1):27-64, 2007. doi: 10.1016/j.cosrev.2007.05.001.
[46] C. L. Staudt and H. Meyerhenke. Engineering High-Performance Community Detection Heuristics for Massive Graphs. In {\it Proceedings 42nd Conference on Parallel Processing} {\it (ICPP’13)}, 2013.
[47] C. L. Staudt and H. Meyerhenke. Engineering Parallel Algorithms for Community Detection in Massive Networks. {\it IEEE Trans. on Parallel and Distributed Systems}, 27(1):171-184, 2016. doi:10.1109/TPDS.2015.2390633.
[48] M. Tasgin and H. Bingol.Community Detection in Complex Networks using Genetic Algorithm. In {\it ECCS ’06: Proc. of the European Conference on Complex Systems}, 2006. arXiv:cond-mat/0604419.
[49] S. M. Van Dongen. {\it Graph Clustering by Flow Simulation}. PhD thesis, Utrecht University, 2001.
[50] D. Wagner and F. Wagner. Between Min Cut and Graph Bisection. In {\it Proceedings of the} {\it 18th International Symposium on Mathematical Foundations of Computer Science}, pages 744-750. Springer, 1993.
[51] Y. Xu, V. Olman, and D. Xu. Clustering Gene Expression Data using a Graph-Theoretic Approach: an Application of Minimum Spanning Trees. {\it Bioinformatics}, 18(4):536-545, 2002.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.