Detecting hierarchical and overlapping network communities using locally optimal modularity changes
- Michael J. Barber
- … show all 1 hide
Abstract
Agglomerative clustering is a well established strategy for identifying communities in networks. Communities are successively merged into larger communities, coarsening a network of actors into a more manageable network of communities. The order in which merges should occur is not in general clear, necessitating heuristics for selecting pairs of communities to merge. We describe a hierarchical clustering algorithm based on a local optimality property. For each edge in the network, we associate the modularity change for merging the communities it links. For each community vertex, we call the preferred edge that edge for which the modularity change is maximal. When an edge is preferred by both vertices that it links, it appears to be the optimal choice from the local viewpoint. We use the locally optimal edges to define the algorithm: simultaneously merge all pairs of communities that are connected by locally optimal edges that would increase the modularity, redetermining the locally optimal edges after each step and continuing so long as the modularity can be further increased. We apply the algorithm to model and empirical networks, demonstrating that it can efficiently produce high-quality community solutions. We relate the performance and implementation details to the structure of the resulting community hierarchies. We additionally consider a complementary local clustering algorithm, describing how to identify overlapping communities based on the local optimality condition.
- M.A. Porter, J.-P. Onnela, P.J. Mucha, Notices of the American Mathematical Society 56, 1082 (2009)
- S. Fortunato, Phys. Rep. 486, 75 (2010) CrossRef
- M.E.J. Newman, Phys. Rev. E 69, 066133 (2004) CrossRef
- M.E.J. Newman, M. Girvan, Phys. Rev. E 69, 026113 (2004) CrossRef
- L. Danon, A. Diaz-Guilera, A. Arenas, J. Stat. Mech. 2006, P11010 (2006) CrossRef
- M.J. Barber, J.W. Clark, Phys. Rev. E 80, 026129 (2009) CrossRef
- A. Clauset, M.E.J. Newman, C. Moore, Phys. Rev. E 70, 066111 (2004) CrossRef
- K. Wakita, T. Tsurumi, in Proceedings of the Sixteenth International World Wide Web Conference, 2007
- T. Hastie, R. Tibshirani, J. Friedman,The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd edn. (Springer Science + Business Media, New York, 2009)
- A.K. Jain, M.N. Murty, P.J. Flynn, ACM Comput. Surv. 31, 264 (1999) CrossRef
- J.H. Ward, J. Am. Stat. Assoc. 58, 236 (1963) CrossRef
- J. Reichardt, S. Bornholdt, Phys. Rev. E 74, 016110 (2006) CrossRef
- P. Schuetz, A. Caflisch, Phys. Rev. E 77, 046112 (2008) CrossRef
- P. Schuetz, A. Caflisch, Phys. Rev. E 78, 026112 (2008) CrossRef
- V.D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre, J. Stat. Mech. 2008, P10008 (2008) CrossRef
- A. Lancichinetti, S. Fortunato, F. Radicchi, Phys. Rev. E 78, 046110 (2008) CrossRef
- W.W. Zachary, J. Anthropological Res. 33, 452 (1977)
- D. Lusseau, K. Schneider, O.J. Boisseau, P. Haase, E. Slooten, S.M. Dawson, Behav. Ecology Sociobiol. 54, 396 (2003) CrossRef
- D.E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing, 1st edn. (Addison-Wesley Professional, Reading, MA, 1994)
- V. Krebs (2004), http://www.orgnet.com/divided2.html
- M.E.J. Newman, Phys. Rev. E 74, 036104 (2006) CrossRef
- M. Girvan, M.E.J. Newman, Proc. Natl. Acad. Sci. 99, 7821 (2002) CrossRef
- P.M. Gleiser, L. Danon, Adv. Complex Syst. 6, 565 (2003) CrossRef
- D.J. Watts, S.H. Strogatz, Nature 393, 440 (1998) CrossRef
- H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, A.L. Barabasi, Nature 407, 651 (2000) CrossRef
- R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, A. Arenas, Phys. Rev. E 68, 065103 (2003) CrossRef
- L.A. Adamic, N. Glance, in Proceedings of the 3rd international workshop on Link discovery, LinkKDD ’05, New York, USA, 2005, ACM pp. 36–43
- M.E.J. Newman, Proc. Natl. Acad. Sci. 98, 404 (2001) CrossRef
- M. Boguñá, R. Pastor-Satorras, A. Díaz-Guilera, A. Arenas, Phys. Rev. E 70, 056122 (2004) CrossRef
- M. Newman (2011), http://www-personal.umich.edu/˜mejn/netdata/
- M.J. Barber, Phys. Rev. E 76, 066102 (2007) CrossRef
- L. Angelini, S. Boccaletti, D. Marinazzo, M. Pellicoro, S. Stramaglia, Chaos 17, 023114 (2007) CrossRef
- M. Rosvall, D. Axelsson, C.T. Bergstrom, Eur. Phys. J. Special Topics 178, 13 (2009) CrossRef
- Title
- Detecting hierarchical and overlapping network communities using locally optimal modularity changes
- Journal
-
The European Physical Journal B
86:385
- Online Date
- September 2013
- DOI
- 10.1140/epjb/e2013-40645-6
- Print ISSN
- 1434-6028
- Online ISSN
- 1434-6036
- Publisher
- Springer Berlin Heidelberg
- Additional Links
- Topics
- Keywords
-
- Statistical and Nonlinear Physics
- Industry Sectors
- Authors
- Author Affiliations
-
- 1. Innovation Systems Department, AIT Austrian Institute of Technology GmbH, 1220, Vienna, Austria