Community detection by modularity maximization using GRASP with path relinking. (English) Zbl 1348.91237

Summary: Complex systems in diverse areas such as biology, sociology and physics are frequently being modelled as graphs, that provide the mathematical framework upon which small scale dynamics between the fundamental elements of the system can reveal large scale system behavior. Community structure in a graph is an important large scale characteristic, and can be described as a natural division of the vertices into densely connected groups, or clusters. Detection of community structure remains up to this date a computationally challenging problem despite the efforts of many researchers from various scientific fields in the past few years. The modularity value of a set of vertex clusters in a graph is a widely used quality measure for community structure, and the relating problem of finding a partition of the vertices into clusters such that the corresponding modularity is maximized is an NP-Hard problem.
In this paper we present a Greedy Randomized Adaptive Search Procedure (GRASP) with path relinking, for solving the modularity maximization problem in weighted graphs.
A class of \(\{0,1\}\) matrices is introduced that characterizes the family of clusterings in a graph, and a distance function is given that enables us to define an \(l\)-neighborhood local search, which generalizes most of the related local search methods that have appeared in the literature. Computational experiments comparing the proposed algorithm with other heuristics from the literature in a set of artificially generated graphs and some well known benchmark instances, indicate that our implementation of GRASP with path relinking consistently produces better quality solutions.


91D30 Social networks; opinion dynamics
05C85 Graph algorithms (graph-theoretic aspects)
90C35 Programming involving graphs or networks
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI Link


[1] \(\langle\)http://vlado.fmf.uni-lj.si/pub/networks/data/GD/GD.htm\(\rangle\)
[2] Agarwal, G.; Kempe, D., Modularity-maximizing graph communities via mathematical programming, European Physical Journal B, 66, 409-418, (2008) · Zbl 1188.90262
[3] Aiex, R. M.; Resende, M.; Pardalos, P. M.; Toraldo, G., GRASP with path-relinking for the three-index assignment problem, Parallel Computing, 29, 393-430, (2003)
[4] Aloise, D.; Cafieri, S.; Caporossi, G.; Hansen, P.; Perron, S.; Liberti, L., Column generation algorithms for exact modularity maximization in networks, Physical Review E, 82, 046112, (2010)
[5] Arenas, A.; Fernández, A.; Goméz, S., Analysis of the structure of complex networks at different resolution levels, New Journal of Physics, 10, 053039, (2008)
[6] Blondel, V. D.; Guillaume, J. L.; Lambiotte, R.; Lefebrvre, E., Fast unfolding of communities in large networks, Journal of Statistical Mechanics, P10008, (2008)
[7] Boguñá, M.; Pastor-Satorras, R.; Arenas, A., Models of social networks based on social distance attachment, Physical Review E, 70, 056122, (2004)
[8] Brandes, U.; Delling, D.; Gaertler, M.; Görke, R.; Hoefer, M.; Nikolosk, Z.; Wagner, D., On modularity clustering, IEEE Transactions on Knowledge and Data Engineering, 20, 172-188, (2008)
[9] Cafieri, S.; Hansen, P.; Liberti, L., Locally optimal heuristic for modularity maximization of networks, Physical Review E, 83, 056105, (2011)
[10] Clauset, A.; Newman, M. E.J.; Moore, C., Finding community structure in very large networks, Physical Review E, 70, 066111, (2004)
[11] Danon, L.; Díaz-Guilera, A.; Arenas, A., Effect of size heterogeneity on community identification in complex networks, Journal of Statistical MechanicsTheory and Experiment, 11010, (2006)
[12] Dartnell, L.; Simeonidis, E.; Hubank, M.; Tsoka, S.; Bogle, I.; Papageorgiou, L., Robustness of the p53 network and biological hackers, FEBS Letters, 579, 3037-3042, (2005)
[13] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming A, 91, 201-213, (2002) · Zbl 1049.90004
[14] Duch, J.; Arenas, A., Community identification using extremal optimization, Physical Review E, 72, 027104, (2005)
[15] Festa, P.; Pardalos, P. M.; Pitsoulis, L. S.; Resende, M. G.C., GRASP with path-relinking for the weighted maxsat problem, ACM Journal of Experimental Algorithmics, (2006) · Zbl 1140.68403
[16] Festa, P.; Resende, M. G.C., Graspan annotated bibliography, (Ribeiro, C. C.; Hansen, P., Essays and surveys on metaheuristics, (2002), Kluwer Academic Publishers), 325-367 · Zbl 1017.90001
[17] Fortunato, S., Community detection in graphs, Physics Reports, 486, (2010)
[18] Girvan, M.; Newman, M., Community structure in social and biological networks, Proceedings of the National Academy of Sciences of the USA, 99, 7821-7826, (2002) · Zbl 1032.91716
[19] Gleiser, P.; Danon, L., Community structure in jazz, Advances in Complex Systems, 6, 565-573, (2003)
[20] Glover, F., Tabu search and adaptive memory programming—advances, applications and challenges, (Barr, R. S.; Helgason, R. V.; Kennington, J. L., Interfaces in computer science and operations research, (1996), Kluwer), 1-75 · Zbl 0882.90111
[21] Guimerá, R.; Sales-Pardo, M.; Amaral, L. A.N., Modularity from fluctuations in random graphs and complex networks, Physical Review E, 70, 2, 025101, (2004)
[22] Kernighan, B. W.; Lin, S., An efficient heuristic procedure for partitioning graphs, The Bell System Technical Journal, 49, 291-307, (1970) · Zbl 0333.05001
[23] Knuth, D. E., The Stanford graphbasea platform for combinatorial computing, (1993), Addison-Wesley Reading, MA
[24] Krebs V. Books on US politics, unpublished. \(\langle\)http://www.orgnet.com\(\rangle\). · JFM 06.0672.01
[25] Lancichinetti, A.; Fortunato, S., Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities, Physical Review E, 80, 016118, (2009)
[26] Lancichinetti, A.; Fortunato, S.; Radicchi, F., Benchmark graphs for testing community detection algorithms, Physical Review E, 78, 046110, (2008)
[27] Lawler, E., Combinatorial optmizationnetworks and matroids, (1976), Dover Publications
[28] Liu X, Li D, Wang S, Tao Z. Effective algorithm for detecting community structure in complex networks based on ga and clustering In: Proceedings of the 7th international conference on computational science. Springer-Verlag; 2007. p. 657-64.
[29] Lusseau, D.; Schneider, K.; Boisseau, O. J.; Haase, P.; Slooten, E.; Dawson, S. M., The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, Behavioral Ecology and Sociobiology, 54, 396-405, (2003)
[30] Medus, A.; Acuña, G.; Dorso, C. O., Detection of community structures in networks via global optimization, Physica A, 358, 593-604, (2005)
[31] Nascimento, M. C.V.; Toledo, F. M.B.; Carvalho, A. P.L. F., Investigation of a new GRASP-based clustering algorithm applied to biological data, Computers & Operations Research, 37, 1381-1388, (2010) · Zbl 1183.68494
[32] Newman, M. E.J., Scientific collaboration networks. II. shortest paths, weighted networks, and centrality, Physical Review E, 64, 016132, (2001)
[33] Newman, M. E.J., Finding community structure in networks using the eigenvectors of matrices, Physical Review E, 74, 036-104, (2006)
[34] Newman, M. E.J., Analysis of weighted networks, Physical Review E, 70, 056131, (2004)
[35] Newman, M. E.J., Fast algorithm for detecting community structure in networks, Physical Review E, 69, 066133, (2004)
[36] Newman, M. E.J.; Girvan, M., Finding and evaluating community structure in networks, Physical Review E, 69, 026113, (2004)
[37] Noack A, Rotta R. Multi-level algorithms for modularity clustering. In: Proceedings of the 8th international symposium on experimental algorithms (SEA 2009), Lecture notes in computer science, vol. 5526. Springer; 2009. p. 257-68.
[38] Pitsoulis L., Resende MGC. Greedy randomized adaptive search procedures. In: Handbook of applied optimization. Oxford University Press; 2002. p. 168-81.
[39] Porter, M. A.; Onnela, J.-P.; Mucha, P. J., Communities in networks, Notices of the American Mathematical Society, 56, 9, 1082-1097, (2009) · Zbl 1188.05142
[40] Reichardt, J.; Bornholdt, S., Statistical mechanics of community detection, Physical Review E, 74, 016110, (2006)
[41] Resende, M. G.C.; Ribeiro, C. C., A grasp with path-relinking for private virtual circuit routing, Networks, 41, 1, 104-114, (2003) · Zbl 1028.90502
[42] Resende, MGC, Ribeiro CC. Grasp with path-relinking: Recent advances and applications. In: Metaheuristics: progress as real problem solvers. Springer; 2005. p. 29-63.
[43] Rotta R. A multi-level algorithm for modularity graph clustering. PhD thesis, Brandenburgische Technische Universität Cottbus; 2008.
[44] Schuetz, P.; Caflisch, A., Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement, Physical Review E, 77, 046112, (2008)
[45] Wakita K, Tsurumi T. Finding community structure in a mega-scale social networking service. In: Proceedings of IADIS international conference on WWW/Internet; 2007. p. 153-162.
[46] Watts, D.; Strogatz, S., Collective dynamics of small-world networks, Nature, 393, 440-442, (1998) · Zbl 1368.05139
[47] White S, Smyth P. A spectral clustering approach to finding communities in graphs. In: Proceedings of SIAM international conference on data mining; 2005. p. 76-84.
[48] Xu, G.; Tsoka, S.; Papageorgiou, L. G., Finding community structures in complex networks using mixed integer optimisation, European Physical Journal B, 60, 231-239, (2007) · Zbl 1189.90027
[49] Ye, Z.; Hu, S.; Yu, J., Adaptive clustering algorithm for community detection in complex networks, Physical Review E, 78, 046115, (2008)
[50] Zachary, W., An information flow model for conflict and fission in small groups, Journal of Anthropological Research, 33, 452-473, (1977)
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.