Proceedings

A Convex Formulation of Modularity Maximization for Community Detection

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2218-2224.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-370

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

Complex networks pervade in diverse areas ranging from the natural world to the engineered world and from traditional application domains to new and emerging domains, including web-based social networks. Of crucial importance to the understanding of many network phenomena, dynamics and functions is the study of network structural properties. One important type of network structure is known as community structure which refers to the existence of communities that are tightly knit local groups with relatively dense connections among their members. Community detection is the problem of detecting these communities automatically. In this paper, based on the modularity measure proposed previously for community detection, we first propose a reformulation of an optimization problem for the 2-partition problem. Based on this new formulation, we can extend it naturally for tackling the general k-partition problem directly without having to tackle multiple 2-partition subproblems like what other methods do. We then propose a convex relaxation scheme to give an iterative algorithm which solves a simple quadratic program in each iteration. We empirically compare our method with some related methods and find that our method is both scalable and competitive in performance via maintaining a good tradeoff between efficiency and quality.

  1. [Agarwal and Kempe, 2008] G. Agarwal and D. Kempe. Modularity-maximizing network communities via mathe- matical programming. The European Physical Journal B, 66(3):409-418, 2008.
  2. [Brandes et al., 2008] U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, and D. Wagner. On modularity clustering. IEEE Transactions on Knowledge Data Engineering, 20(2):172-188, 2008.
  3. [Clauset et al., 2004] A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large net- works. Physical Review E, 70(6):066111, Dec 2004.
  4. [Fortunato and Barthélemy, 2007] S. Fortunato and M. Barthélemy. Resolution limit in community de- tection. Proceedings of the National Academy of Sciences of the United States of America, 104(1):36, 2007.
  5. [Girvan and Newman, 2002] M. Girvan and M. E. J. New- man. Community structure in social and biological net- works. Proceedings of the National Academy of Sciences of the United States of America, 99(12):7821-7826, June 2002.
  6. [Gleiser and Danon, 2003] P. Gleiser and L. Danon. Com- munity Structure in Jazz. Advances in Complex Systems, 6(4):565-573, 2003.
  7. [Guimerà et al., 2003] R. Guimerà, L. Danon, A. Díaz- Guilera, F. Giralt, and A. Arenas. Self-similar community structure in a network of human interactions. Physical Re- view E, 68(6):065103, Dec 2003.
  8. [Jeong et al., 2000] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A. L. Barabàsi. The large-scale organization of metabolic networks. Nature, 407(6804):651-654, Oct 2000.
  9. [Kernighan and Lin, 1970] B. Kernighan and S. Lin. An effi- cient heuristic procedure for partitioning graphs. Bell Sys- tem Technical Journal, pages 291-307, 1970.
  10. [Lusseau et al., 2003] D. Lusseau, K. Schneider, O. Bois- seau, P. Haase, E. Slooten, and S. Dawson. The bottlenose dolphin community of doubtful sound features a large pro- portion of long-lasting associations. Behavioral Ecology and Sociobiology, 54:396-405, 2003. 10.1007/s00265- 003-0651-y. DOI
  11. [Newman and Girvan, 2004] M. E. J. Newman and M. Gir- van. Finding and evaluating community structure in net- works. Physical Review E, 69(2):026113-+, feb 2004.
  12. [Newman et al., 2006] M. Newman, A.L. Barabási, and D.J. Watts, editors. The Structure and Dynamics of Networks. Princeton University Press, Princeton, NJ, USA, 2006.
  13. [Newman, 2001] M. E. J. Newman. The structure of sci- entific collaboration networks. Proceedings of the Na- tional Academy of Sciences of the United States of Amer- ica, 98(2):404-409, 2001.
  14. [Newman, 2006] M. E. J. Newman. Modularity and com- munity structure in networks. Proceedings of the Na- tional Academy of Sciences of the United States of Amer- ica, 103(23):8577-8582, 6 2006.
  15. [Noack and Rotta, 2009] A. Noack and R. Rotta. Multi-level algorithms for modularity clustering. In Jan Vahrenhold, editor, SEA, volume 5526 of Lecture Notes in Computer Science, pages 257-268. Springer, 2009.
  16. [Shi and Malik, 1997] J. Shi and J. Malik. Normalized cuts and image segmentation. In Proceedings of the IEEE Com- puter Society Conference on Computer Vision and Pattern Recognition, pages 731-737, San Juan, Puerto Rico, 17- 19 June 1997.
  17. [Zachary, 1977] W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthro- pological Research, 33:452-473, 1977.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards