zbMATH — the first resource for mathematics

Efficient modularity density heuristics for large graphs. (English) Zbl 1394.90578
Summary: Modularity density maximization is a community detection optimization problem which improves the resolution limit degeneracy of modularity maximization. This paper presents seven scalable heuristics for modularity density and compares them with literature results from exact mixed integer linear programming and GAOD, iMeme-Net, HAIN, and BMD-\(\lambda\) heuristics. The results are also compared with CNM and Louvain, which are scalable heuristics for modularity maximization. The results suggest that our seven heuristics are faster than GAOD, iMeme-Net, HAIN, and BMD-\(\lambda\) modularity density heuristics. Our experiments also show that some of our heuristics surpassed the objective function value reported by iMeme-Net, Hain, and BMD-\(\lambda\) for some real graphs. Our seven heuristics were tested with real graphs from the Stanford Large Network Dataset Collection and the experiments show that they are scalable. This feature was confirmed by an amortized complexity analysis which reveals average linear time for three of our heuristics. Hypothesis tests suggest that four proposed heuristics are state-of-the-art since they are scalable for hundreds of thousands of nodes for the modularity density problem, and they find the high objective value partitions for the largest instances. Ground truth experiments in artificial random graphs were performed and suggest that our heuristics lead to better cluster detection than both CNM and Louvain.

90C59 Approximation methods and heuristics in mathematical programming
90C35 Programming involving graphs or networks
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
Full Text: DOI
[1] Agarwal, G.; Kempe, D., Modularity-maximizing graph communities via mathematical programming, The European Physical Journal B, 66, 3, 409-418, (2008) · Zbl 1188.90262
[2] 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, 4, 046112, (2010)
[3] Aloise, D.; Caporossi, G.; Hansen, P.; Liberti, L.; Perron, S.; Ruiz, M., Modularity maximization in networks by variable neighborhood search, (Bader, D. A.; Meyerhenke, H.; Sanders, P.; Wagner, D., Contemporary mathematics, Graph Partitioning and Graph Clustering, 588, (2013)), 113-127 · Zbl 1276.90055
[4] Arenas, A.; Fernandez, A.; Gomez, S., Analysis of the structure of complex networks at different resolution levels, New Journal of Physics, 10, 053039, (2008)
[5] Batagelj, V., & Mrvar, A. (2006). Pajek datasets. http://vlado.fmf.uni-lj.si/pub/networks/data/. · Zbl 1054.68564
[6] Blondel, V. D.; Guillaume, J.-L.; Lambiotte, R.; Lefebvre, E., Fast unfolding of communities in large networks, Journal of Statistical Mechanics, 2008, 10, P10008, (2008)
[7] Brandes, U.; Delling, D.; Gaertler, M.; Gorke, R.; Hoefer, M.; Nikoloski, Z., On modularity clustering, IEEE Transactions on Knowledge and Data Engineering, 20, 2, 172-188, (2008)
[8] Cafieri, S.; Costa, A.; Hansen, P., Adding cohesion constraints to models for modularity maximization in networks, Journal of Complex Networks, 3, 3, 388-410, (2015) · Zbl 1397.05170
[9] Cafieri, S.; Costa, A.; Hansen, P., Reformulation of a model for hierarchical divisive graph modularity maximization, Annals of Operations Research, 222, 1, 213-226, (2014) · Zbl 1303.90111
[10] Cafieri, S.; Hansen, P.; Liberti, L., Loops and multiple edges in modularity maximization of networks., Physical Review. E, 81, 4, 046102, (2010)
[11] Cafieri, S.; Hansen, P.; Liberti, L., Locally optimal heuristic for modularity maximization of networks., Physical Review. E, 83, 5, 056105, (2011)
[12] Cafieri, S.; Hansen, P.; Liberti, L., Improving heuristics for network modularity maximization using an exact algorithm, Discrete Applied Mathematics, 163, 65-72, (2014) · Zbl 1303.90112
[13] Chakraborty, T.; Srinivasan, S.; Ganguly, N.; Bhowmick, S.; Mukherjee, A., Constant communities in complex networks., Scientific reports, 3, 1825, (2013)
[14] Chen, M.; Nguyen, T.; Szymanski, B. K., On measuring the quality of a network community structure, Proceedings of international conference on social computing (SocialCom), 2013, 122-127, (2013), IEEE Alexandria
[15] Chen, P.-y.; Hero, A. O., Local Fiedler vector centrality for detection of deep and overlapping communities in networks, Proceedings of 2014 IEEE international conference on acoustics, speech and signal processing (ICASSP), vol. 2, 1120-1124, (2014), IEEE
[16] Clauset, A.; Newman, M. E.J.; Moore, C., Finding community structure in very large networks, Physical Review E, 70, 6, 066111-1-066111-6, (2004)
[17] Costa, A., MILP formulations for the modularity density maximization problem, European Journal of Operational Research, 245, 1, 14-21, (2015) · Zbl 1346.05266
[18] Costa, A.; Kushnarev, S.; Liberti, L.; Sun, Z., Divisive heuristic for modularity density maximization, Computers & Operations Research, 71, 100-109, (2016) · Zbl 1349.90850
[19] Danon, L.; Duch, J.; Diaz-Guilera, A.; Arenas, A., Comparing community structure identification, Journal of Statistical Mechanics: Theory and Experiment, 2005, 09, 10, (2005) · Zbl 07077983
[20] Darst, R. K.; Nussinov, Z.; Fortunato, S., Improving the performance of algorithms to find communities in networks, Physical Review E, 89, 3, 032809, (2014)
[21] De Meo, P.; Ferrara, E.; Fiumara, G.; Provetti, A., Enhancing community detection using a network weighting strategy, Information Sciences, 222, 648-668, (2013) · Zbl 1293.91164
[22] De Meo, P.; Ferrara, E.; Fiumara, G.; Provetti, A., Mixing local and global information for community detection in large networks, Journal of Computer and System Sciences, 80, 1, 72-87, (2014) · Zbl 1311.68133
[23] Dinh, T. N.; Thai, M. T., Toward optimal community detection: from trees to general weighted networks, Internet Mathematics, 11, 3, 181-200, (2015)
[24] Djidjev, H. N.; Onus, M., Scalable and accurate graph clustering and community structure detection, IEEE Transactions on Parallel and Distributed Systems, 24, 5, 1022-1029, (2013)
[25] Ferrara, E.; De Meo, P.; Catanese, S.; Fiumara, G., Detecting criminal organizations in mobile phone networks, Expert Systems with Applications, 41, 13, 5733-5750, (2014)
[26] Fortunato, S.; Barthélemy, M., Resolution limit in community detection., Proceedings of the National Academy of Sciences of the United States of America, 104, 1, 36-41, (2007)
[27] Fortunato, S.; Castellano, C., Community structure in graphs, (Meyers, R. A., Computational complexity, (2012), Springer New York New York, NY), 490-512
[28] Gong, M.; Cai, Q.; Li, Y.; Ma, J., An improved memetic algorithm for community detection in complex networks, 2012 ieee congress on evolutionary computation, 1-8, (2012), IEEE Brisbane, QLD
[29] Good, B. H.; de Montjoye, Y.-A.; Clauset, A., Performance of modularity maximization in practical contexts, Physical Review E, 81, 4, 046106, (2010)
[30] Granell, C.; Gómez, S.; Arenas, A., Hierarchical multiresolution method to overcome the resolution limit in complex networks, International Journal of Bifurcation and Chaos, 22, 07, 1250171-1-1250171-7, (2012)
[31] Guimera, R.; Amaral, L., Functional cartography of complex metabolic networks, Nature, 433, 895-900, (2005)
[32] Hric, D.; Darst, R. K.; Fortunato, S., Community detection in networks: structural communities versus ground truth, Physical Review E, 90, 6, 062805, (2014)
[33] Izunaga, Y.; Matsui, T.; Yamamoto, Y., A doubly nonnegative relaxation for modularity density maximization, Technical Report, 1339, (2016), University of Tsukuba Tsukuba
[34] Jarukasemratana, S.; Murata, T., Edge weight method for community detection in scale-free networks, Proceedings of the 4th international conference on web intelligence, mining and semantics (WIMS14) - WIMS ’14, 1(c), 1-9, (2014)
[35] Jia, S.; Gao, L.; Gao, Y.; Wang, H., Anti-triangle centrality-based community detection in complex networks., IET systems biology, 8, 3, 116-125, (2014)
[36] Jiang, J. Q.; McQuay, L. J., Modularity functions maximization with nonnegative relaxation facilitates community detection in networks, Physica A, 391, 3, 854-865, (2012)
[37] Junttila, T.; Kaski, P., Engineering an efficient canonical labeling tool for large and sparse graphs, Proceedings of the ninth workshop on algorithm engineering and experiments, 135-149, (2007)
[38] Junttila, T., & Kaski, P. (2015). A tool for computing automorphism groups and canonical labelings of graphs. http://www.tcs.hut.fi/Software/bliss/. Accessed 20.06.16.
[39] Karimi-Majd, A.-M.; Fathian, M.; Amiri, B., A hybrid artificial immune network for detecting communities in complex networks, Computing, 97, 5, 483-507, (2014) · Zbl 1358.91085
[40] Kernighan, B. W.; Lin, S., An efficient heuristic procedure for partitioning graphs, Bell System Technical Journal, 49, 2, 291-307, (1970) · Zbl 0333.05001
[41] Krzakala, F.; Moore, C.; Mossel, E.; Neeman, J.; Sly, A.; Zdeborová, L., Spectral redemption in clustering sparse networks., Proceedings of the National Academy of Sciences of the United States of America, 110(52), 20935-20940, (2013) · Zbl 1359.62252
[42] Lancichinetti, A.; Fortunato, S., Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities, Physical Review E, 80, 1, 016118, (2009)
[43] Lancichinetti, A.; Fortunato, S., Consensus clustering in complex networks., Scientific reports, 2, 336, (2012)
[44] Lancichinetti, A.; Radicchi, F.; Ramasco, J. J.; Fortunato, S., Finding statistically significant communities in networks., PloS one, 6, 4, e18961, (2011)
[45] Leskovec, J., & Krevl, A. (2014). SNAP datasets: Stanford large network dataset collection. http://snap.stanford.edu/data. Accessed 01.07.16.
[46] Li, Z.; Zhang, S.; Wang, R.-S.; Zhang, X.-S.; Chen, L., Quantitative function for community detection, Physical Review E, 77, 3, 036109, (2008)
[47] Liu, J.; Zeng, J., Community detection based on modularity density and genetic algorithm, Proceedings of the international conference on computational aspects of social networks, cason’10, 29-32, (2010)
[48] Matthews, B. W., Comparison of the predicted and observed secondary structure of T4 phage lysozyme, BBA - Protein Structure, 405, 2, 442-451, (1975)
[49] Meilǎ, M., Comparing clusterings, Proceedings of the 22nd international conference on machine learning - ICML ’05, 577-584, (2005), ACM Press New York, New York, USA
[50] Meunier, D.; Fonlupt, P.; Saive, A.-L.; Plailly, J.; Ravel, N.; Royet, J.-P., Modular structure of functional networks in olfactory memory., NeuroImage, 95, 264-275, (2014)
[51] Miyauchi, A.; Sukegawa, N., Redundant constraints in the standard formulation for the clique partitioning problem, Optimization Letters, 9, 1, 199-207, (2014) · Zbl 1316.90057
[52] Muff, S.; Rao, F.; Caflisch, A., Local modularity measure for network clusterizations, Physical Review E, 72, 5, 056107, (2005)
[53] Nascimento, M. C.; Pitsoulis, L., Community detection by modularity maximization using GRASP with path relinking, Computers & Operations Research, 40, 12, 3121-3131, (2013) · Zbl 1348.91237
[54] Nepusz, T.; Yu, H.; Paccanaro, A., Detecting overlapping protein complexes in protein-protein interaction networks, Nature Methods 9, 471-472, (2012)
[55] Newman, M.; Girvan, M., Finding and evaluating community structure in networks, Physical Review E, 69, 2, 026113, (2004)
[56] Newman, M. E.J., Spectral community detection in sparse networks, CoRR, abs/1308.6494, (2013)
[57] Ovelgönne, M.; Geyer-Schulz, A., An ensemble learning strategy for graph clustering, Proceedings of the 10th DIMACS implementation challenge - graph partitioning and graph clustering, 187-205, (2013) · Zbl 1269.05104
[58] Park, H.; Lee, K., Dependence clustering, a method revealing community structure with group dependence, Knowledge-Based Systems, 60, 58-72, (2014)
[59] Pizzuti, C., Boosting the detection of modular community structure with genetic algorithms and local search, Proceedings of the 27th annual ACM symposium on applied computing - SAC ’12, 226, (2012), ACM Press New York, New York, USA
[60] R Foundation (2015). The r project for statistical computing. https://www.r-project.org/. Accessed 10.07.16.
[61] Radicchi, F.; Castellano, C.; Cecconi, F.; Loreto, V.; Parisi, D., Defining and identifying communities in networks., Proceedings of the National Academy of Sciences of the United States of America, 101(9), 2658-2663, (2004)
[62] Rotta, R.; Noack, A., Multilevel local search algorithms for modularity clustering, Journal of Experimental Algorithmics, 16, 2, 2.1, (2011) · Zbl 1284.05309
[63] Sun, P. G., Weighting links based on edge centrality for community detection, Physica A: Statistical Mechanics and its Applications, 394, 346-357, (2014)
[64] Tian, F.; Gao, B.; Cui, Q.; Chen, E.; Liu, T.-y., Learning deep representations for graph clustering, Proceedings of the twenty-eighth AAAI conference on artificial intelligence, 1293-1299, (2014), AAAI Press
[65] Traag, V. A.; Van Dooren, P.; Nesterov, Y., Narrow scope for resolution-limit-free community detection, Physical Review E, 84, 1, 016114, (2011)
[66] Xie, J.; Kelley, S.; Szymanski, B. K., Overlapping community detection in networks, ACM Computing Surveys, 45, 4, 1-35, (2013) · Zbl 1288.68191
[67] 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
[68] Zhang, J.; Qiu, Y.; Zhang, X. S., Detecting community structure: from parsimony to weighted parsimony, Journal of Systems Science and Complexity, 23, 5, 1024-1036, (2010) · Zbl 1208.91121
[69] Zhao, Y.; Jiang, W.; Li, S.; Ma, Y.; Su, G.; Lin, X., A cellular learning automata based algorithm for detecting community structure in complex networks, Neurocomputing, 151, 1216-1226, (2015)
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.