×

Modularity-maximizing graph communities via mathematical programming. (English) Zbl 1188.90262

Summary: In many networks, it is of great interest to identify communities, unusually densely knit groups of individuals. Such communities often shed light on the function of the networks or underlying properties of the individuals. Recently, Newman suggested modularity as a natural measure of the quality of a network partitioning into communities. Since then, various algorithms have been proposed for (approximately) maximizing the modularity of the partitioning determined. In this paper, we introduce the technique of rounding mathematical programs to the problem of modularity maximization, presenting two novel algorithms. More specifically, the algorithms round solutions to linear and vector programs. Importantly, the linear programing algorithm comes with an a posteriori approximation guarantee: by comparing the solution quality to the fractional solution of the linear program, a bound on the available “room for improvement” can be obtained. The vector programming algorithm provides a similar bound for the best partition into two communities. We evaluate both algorithms using experiments on several standard test cases for network partitioning algorithms, and find that they perform comparably or better than past algorithms, while being more efficient than exhaustive techniques.

MSC:

90C35 Programming involving graphs or networks
91D10 Models of societies, social and urban evolution
05C90 Applications of graph theory
90B10 Deterministic network models in operations research

Software:

GraphBase; CSDP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Newman, A. Barabási, D. Watts, The Structure and Dynamics of Networks (Princeton University Press, 2006) · Zbl 1362.00042
[2] J. Scott, Social Network Analysis: A Handbook, 2nd edn. (Sage Publications, 2000)
[3] S. Wasserman, K. Faust, Social Network Analysis (Cambridge University Press, 1994) · Zbl 0926.91066
[4] J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, The web as a graph: Measurements, models and methods, in International Conference on Combinatorics and Computing, 1999
[5] R. Guimerà, L. Amaral, Nature 433, 895 (2005)
[6] M. Newman, Phys. Rev. E 74, 036104 (2006)
[7] G. Flake, S. Lawrence, C.L. Giles, F. Coetzee, IEEE Computer 35, 66 (2002)
[8] M. Girvan, M. Newman, Proc. Natl. Acad. Sci. USA 99, 7821 (2002)
[9] M. Newman, Eur. Phys. J. B 38, 321 (2004)
[10] J. Duch, A. Arenas, Phys. Rev. E 72, 027104 (2005)
[11] G. Flake, R. Tarjan, K. Tsioutsiouliklis, Graph clustering techniques based on minimum cut trees, Technical Report 2002-06 (NEC, Princeton, 2002)
[12] A. Hayrapetyan, D. Kempe, M. Pál, Z. Svitkina, Unbalanced graph cuts, in Proc. 13th European Symp. on Algorithms, 2005, pp. 191–202 · Zbl 1162.05357
[13] M. Charikar, Greedy approximation algorithms for finding dense components in graphs, in Proc. 3rd Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2000 · Zbl 0976.05062
[14] M. Newman, M. Girvan, Phys. Rev. E 69, 026113 (2004)
[15] M. Newman, Phys. Rev. E 69, 066133 (2004)
[16] A. Clauset, M. Newman, C. Moore, Phys. Rev. E 70, 066111 (2004)
[17] A. Clauset, Phys. Rev. E 72, 026132 (2005)
[18] M. Newman, Proc. Natl. Acad. Sci. USA 103, 8577 (2006)
[19] L. Danon, J. Duch, A. Diaz-Guilera, A. Arenas, J. Stat. Mech. P09008 (2005)
[20] S. Fortunato, M. Barthélemy, Proc. Natl. Acad. Sci. USA 104, 36 (2007)
[21] J. Kleinberg, An impossibility theorem for clustering, in Proc. Advances in Neural Information Processing Systems (NIPS) (2002)
[22] U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, D. Wagner, IEEE Trans. Know, Data Eng. 20, 172 (2008)
[23] M. Charikar, V. Guruswami, A. Wirth, J. Comput. System Sci. 360 (2005)
[24] N. Bansal, A. Blum, S. Chawla, Machine Learning 56, 89 (2004)
[25] M. Goemans, D. Williamson, J. ACM 42, 1115 (1995)
[26] M. Gaertler, R. Görke, D. Wagner, Significance-driven graph clustering, in Proc. 3rd Intl. Conf. on Algorithmic Aspects in Information and Management, 2007, pp. 11–26 · Zbl 1137.68536
[27] V. Chvátal, Linear Programming (Freeman, 1983)
[28] H. Karloff, Linear Programming (Birkhäuser, 1991)
[29] V. Vazirani, Approximation Algorithms (Springer, 2001) · Zbl 0999.68546
[30] N. Karmarkar, Combinatorica 4, 373 (1984)
[31] M. Sales-Pardo, R. Guimera, A. Moreira, L. Amaral, Proc. Natl. Acad. Sci. USA 104, 15224 (2007)
[32] M. Fiedler, Czech. Math. J. 25, 619 (1975)
[33] B. Borchers, Optim. Meth. Softw. 11, 613 (1999)
[34] M. Charikar, A. Wirth, Maximizing quadratic programs: Extending grothendieck’s inequality, in Proc. 45th IEEE Symp. on Foundations of Computer Science, 2004, pp. 54–60
[35] Y. Nesterov, Optim. Meth. Softw. 9, 141 (1998)
[36] B. Kernighan, S. Lin, Bell Systems Tech. J. 49, 291 (1970)
[37] A. Lancichinetti, S. Fortunato, F. Radicchi, New benchmark in community detection, 2008, eprint arXiv: 0805.4770
[38] W. Zachary, J. Anthropol. Res. 33, (1977)
[39] A. Medus, G. Acuña, C. Dorso, Phys. A Stat. Mech. Appl. 358, 593 (2005)
[40] D. Gfeller, J.-C. Chappelier, P. De Los Rios, Phys. Rev. E 72, (2005)
[41] F. McSherry, Spectral partitioning of random graphs, in Proc. 42nd IEEE Symp. on Foundations of Computer Science, 2001, pp. 529–537
[42] R. Guimerà, M. Sales-Pardo, L. Amaral, Phys. Rev. E, 70, 025101 (2004)
[43] P. Gleiser, L. Danon, Advances in Complex Systems 6, 565 (2003)
[44] D. Lusseau, Proc. of the Royal Society of London B 270, 186 (2003)
[45] D. Knuth, The Stanford GraphBase: A Platform for Combinatorial Algorithms (ACM Press 1993) · Zbl 0806.68121
[46] M. Newman, Phys. Rev. E 64, (2001)
[47] H. Jeong, B. Tomber, R. Albert, Z. Oltvai, A.-L. Barabási, Nature 407, 651 (2000)
[48] R. Guimera, L. Danon, A. Diaz-Guilera, F. Giralt, A. Arenas, Phys. Rev. E 68, 065103 (2003)
[49] R. Guimerà, L. Amaral, J. Stat. Mech. P02001 (2005)
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.