×

Divisive heuristic for modularity density maximization. (English) Zbl 1349.90850

Summary: In this paper we consider a particular method of clustering for graphs, namely the modularity density maximization. We propose a hierarchical divisive heuristic which works by splitting recursively a cluster into two new clusters by maximizing the modularity density, and we derive four reformulations for the mathematical programming model used to obtain the optimal splitting. We report computational results of the eight algorithms (four reformulations with two different symmetry breaking strategies) obtained on some instances from the literature. Statistical tests show that the best model in terms of computational time is the one that is obtained with a dual reformulation of the bilinear terms arising in the objective function. Moreover, the hierarchical divisive heuristic provides generally near-optimal solutions in terms of modularity density.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
05C85 Graph algorithms (graph-theoretic aspects)
62H30 Classification and discrimination; cluster analysis (statistical aspects)
90C35 Programming involving graphs or networks

Software:

CPLEX; BARON
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Newman, M. E.J., Networks: an introduction (2010), Oxford University Press: Oxford University Press Oxford · Zbl 1029.68010
[2] Fortunato, S., Community detection in graphs, Phys Rep, 486, 3-5, 75-174 (2010)
[3] Adomavicius, G.; Tuzhilin, A., Toward the next generation of recommender systemsa survey of the state-of-the-art and possible extensions, IEEE Trans Knowl Data Eng, 17, 6, 734-749 (2005)
[5] Guimerà, R.; Amaral, L. A.N., Functional cartography of complex metabolic networks, Nature, 433, 895-900 (2005)
[6] Palla, G.; Derényi, I.; Farkas, I.; Vicsek, T., Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 7043, 814-818 (2005)
[8] Hu, Y.; Chen, H.; Zhang, P.; Li, M.; Di, Z.; Fan, Y., Comparative definition of community and corresponding identifying algorithm, Phys Rev E, 78, 2, 026121 (2008)
[9] Cafieri, S.; Caporossi, G.; Hansen, P.; Perron, S.; Costa, A., Finding communities in networks in the strong and almost-strong sense, Phys Rev E, 85, 4, 046113 (2012)
[10] Newman, M.; Girvan, M. E.J., Finding and evaluating community structure in networks, Phys Rev E, 69, 2, 026113 (2004)
[11] Nascimento, M. C.V.; Pitsoulis, L., Community detection by modularity maximization using GRASP with path relinking, Comput Oper Res, 40, 12, 3121-3131 (2013) · Zbl 1348.91237
[12] Blondel, V.; Guillaume, J.-L.; Lambiotte, R.; Lefebvre, E., Fast unfolding of communities in large networks, J Stat Mech Theory Exp, P10008 (2008) · Zbl 1459.91130
[13] Medus, A.; Acuna, G.; Dorso, C., Detection of community structures in networks via global optimization, Phys A, 358, 2-4, 593-604 (2005)
[14] Lehmann, S.; Hansen, L., Deterministic modularity optimization, Eur Phys J B, 60, 1, 83-88 (2007)
[15] Duch, J.; Arenas, A., Community identification using extremal optimization, Phys Rev E, 72, 2, 027104 (2005)
[16] Agarwal, G.; Kempe, D., Modularity-maximizing graph communities via mathematical programming, Eur Phys J B, 66, 3, 409-418 (2008) · Zbl 1188.90262
[17] Noack, A.; Rotta, R., Multi-level algorithms for modularity clustering, Lect Notes Comput Sci, 5526, 257-268 (2009)
[18] Schuetz, P.; Caflisch, A., Efficient modularity optimization by multistep algorithm and vertex mover refinement, Phys Rev E, 77, 4, 046112 (2008)
[19] Cafieri, S.; Hansen, P.; Liberti, L., Locally optimal heuristic for modularity maximization of networks, Phys Rev E, 83, 5, 056105 (2011)
[20] Cafieri, S.; Costa, A.; Hansen, P., Reformulation of a model for hierarchical divisive graph modularity maximization, Ann Oper Res, 222, 1, 213-226 (2014) · Zbl 1303.90111
[21] Xu, G.; Tsoka, S.; Papageorgiou, L. G., Finding community structures in complex networks using mixed integer optimisation, Eur Phys J B, 60, 2, 231-239 (2007) · Zbl 1189.90027
[22] Brandes, U.; Delling, D.; Gaertler, M.; Görke, R.; Hoefer, M.; Nikoloski, Z., On modularity clustering, IEEE Trans Knowl Data Eng, 20, 2, 172-188 (2008)
[23] Aloise, D.; Cafieri, S.; Caporossi, G.; Hansen, P.; Perron, S.; Liberti, L., Column generation algorithms for exact modularity maximization in networks, Phys Rev E, 82, 4, 046112 (2010)
[24] Cafieri, S.; Costa, A.; Hansen, P., Adding cohesion constraints to models for modularity maximization in networks, J Complex Netw, 3, 3, 388-410 (2015) · Zbl 1397.05170
[25] Grötschel, M.; Wakabayashi, Y., A cutting plane algorithm for a clustering problem, Math Progr, 45, 59-96 (1989) · Zbl 0675.90072
[27] Miyauchi, A.; Sukegawa, N., Redundant constraints in the standard formulation for the clique partitioning problem, Optim Lett, 9, 1, 199-207 (2015) · Zbl 1316.90057
[29] Good, B. H.; de Montjoye, Y.-A.; Clauset, A., Performance of modularity maximization in practical contexts, Phys Rev E, 81, 4, 046106 (2010)
[30] Li, Z.; Zhang, S.; Wang, R.-S.; Zhang, X.-S.; Chen, L., Quantitative function for community detection, Phys Rev E, 77, 3, 036109 (2008)
[31] Costa, A., MILP formulations for the modularity density maximization problem, Eur J Oper Res, 245, 1, 14-21 (2015) · Zbl 1346.05266
[33] Costa, A.; Hansen, P., A locally optimal hierarchical divisive heuristic for bipartite modularity maximization, Optim Lett, 8, 3, 903-917 (2014) · Zbl 1292.90301
[34] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim Methods Softw, 24, 4-5, 597-634 (2009) · Zbl 1179.90237
[37] McCormick, G. P., Computability of global solutions to factorable nonconvex programspart I - convex underestimating problems, Math Progr, 10, 146-175 (1976) · Zbl 0349.90100
[38] Liberti, L., Reformulations in mathematical programmingdefinitions and systematics, RAIRO-OR, 43, 1, 55-86 (2009) · Zbl 1158.90390
[39] Fortet, R., Applications de l׳algèbre de Boole en recherche opérationelle, Rev Fr Rech Opér, 4, 14, 17-26 (1960)
[40] Benati, S.; García, S., A mixed integer linear model for clustering with variable selection, Comput Oper Res, 43, 280-285 (2014) · Zbl 1349.62258
[41] Rikun, A., A convex envelope formula for multilinear functions, J Glob Optim, 10, 4, 425-437 (1997) · Zbl 0881.90099
[42] Tardella, F., Existence and sum decomposition of vertex polyhedral convex envelopes, Optim Lett, 2, 363-375 (2008) · Zbl 1152.90614
[44] Costa, A.; Hansen, P.; Liberti, L., On the impact of symmetry-breaking constraints on spatial branch-and-bound for circle packing in a square, Discrete Appl Math, 161, 1-2, 96-106 (2013) · Zbl 1262.90143
[46] Conover, W. J., Practical nonparametric statistics (1999), John Wiley & Sons: John Wiley & Sons New York · Zbl 0151.23503
[47] Bounova, G.; de Weck, O., Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles, Phys Rev E, 85, 1, 016117 (2012)
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.