Detection of node group membership in networks with group overlap
- E. N. Sawardecker,
- M. Sales-Pardo,
- L. A.N. Amaral
- … show all 3 hide
Abstract
Most networks found in social and biochemical systems have modular structures. An important question prompted by the modularity of these networks is whether nodes can be said to belong to a single group. If they cannot, we would need to consider the role of “overlapping communities.” Despite some efforts in this direction, the problem of detecting overlapping groups remains unsolved because there is neither a formal definition of overlapping community, nor an ensemble of networks with which to test the performance of group detection algorithms when nodes can belong to more than one group. Here, we introduce an ensemble of networks with overlapping groups. We then apply three group identification methods – modularity maximization, k-clique percolation, and modularity-landscape surveying – to these networks. We find that the modularity-landscape surveying method is the only one able to detect heterogeneities in node memberships, and that those heterogeneities are only detectable when the overlap is small. Surprisingly, we find that the k-clique percolation method is unable to detect node membership for the overlapping case.
- M.E.J. Newman, M. Girvan, Phys. Rev. E 69, 026113 (2004)
- R. Guimerà, L.A.N. Amaral, J. Stat. Mech.: Theor. Exp. P02001 (2005)
- D.J. Watts, P.S. Dodds, M.E.J. Newman, Science 296, 1302 (2002)
- L. Donetti, M.A. Muñoz, J. Stat. Mech.: Theor. Exp. P10012 (2004)
- R. Guimerà, M. Sales-Pardo, L.A.N. Amaral, Phys. Rev. E 70, 025101 (2004)
- J. Reichardt, S. Bornholdt, Phys. Rev. Lett. 93, 218701 (2004)
- J. Duch, A. Arenas, Phys. Rev. E 72, 027104 (2005)
- G. Palla, I. Derényi, I. Farkas, T. Vicsek, Nature 435, 814 (2005)
- J. Baumes, M. Goldberg, M. Magdon-Ismail, Efficient Identification of Overlapping Communities, in Intelligence and Security Informatics: IEEE International Conference on Intelligence and Security Informatics, ISI 2005, edited by P. Kantor, G. Muresan, F. Roberts, D. Zeng, F.Y. Wang, H. Chen, R. Merkle, IEEE (Springer, Berlin, 2005), Vol. 3495 of Lecture Notes in Computer Science, pp. 27–36
- D. Gfeller, J.C. Chappelier, P.D.L. Rios, Phys. Rev. E 72, 056135 (2005)
- T. Nepusz, A. Petróczi, L. Négyessy, F. Bazsó, Phys. Rev. E 77, 016107 (2008)
- J.B. Pereira-Leal, A.J. Enright, C.A. Ouzounis, Proteins 54, 49 (2004)
- M. Sales-Pardo, R. Guimerà, A.A. Moreira, L.A.N. Amaral, Proc. Natl. Acad. Sci. USA 104, 15224 (2007)
- A. Clauset, C. Moore, M.E.J. Newman, Nature 453, 98 (2008)
- R. Guimerà, L.A.N. Amaral, Nature 433, 895 (2005)
- M.E.J. Newman, Proc. Natl. Acad. Sci. USA 103, 8577 (2006)
- M.E.J. Newman, Phys. Rev. E 68, 026121 (2003)
- R. Guimerà, S. Mossa, A. Turtschi, L.A.N. Amaral, Proc. Natl. Acad. Sci. USA 102, 7794 (2005)
- M.B. Hastings, Phys. Rev. E 74, 035102 (2006)
- M.E.J. Newman, Phys. Rev. E 74, 036104 (2006)
- S. Fortunato, M. Barthélemy, Proc. Natl. Acad. Sci. USA 104, 36 (2007)
- J.M. Kumpula, J. Saramäki, K. Kaski, J. Kertész, Eur. Phys. J. B 56, 41 (2007)
- L. Danon, A. Díaz-Guilera, J. Duch, A. Arenas, J. Stat. Mech.: Theor. Exp. P09008 (2005)
- F.H. Stillinger, T.A. Weber, Phys. Rev. A 25, 978 (1982)
- F.H. Stillinger, T.A. Weber, Science 225, 983 (1984)
- F.H. Stillinger, T.A. Weber, Phys. Rev. B 31, 5262 (1985)
- A. Arenas, A. Díaz-Guilera, C.J. Pérez-Vicente, Phys. Rev. Lett. 96, 114102 (2006)
- Title
- Detection of node group membership in networks with group overlap
- Journal
-
The European Physical Journal B
Volume 67, Issue 3 , pp 277-284
- Cover Date
- 2009-02-01
- DOI
- 10.1140/epjb/e2008-00418-0
- Print ISSN
- 1434-6028
- Online ISSN
- 1434-6036
- Publisher
- Springer-Verlag
- Additional Links
- Topics
- Keywords
-
- 89.75.Fb Structures and organization in complex systems
- Industry Sectors
- Authors
-
-
E. N. Sawardecker
(1)
- M. Sales-Pardo (1) (2) (3)
-
L. A.N. Amaral
(1) (2)
-
E. N. Sawardecker
- Author Affiliations
-
- 1. Department of Chemical and Biological Engineering, Northwestern University, Evanston, IL, 60208, USA
- 2. Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL, 60208, USA
- 3. Northwestern University Clinical and Translational Sciences Institute, Chicago, IL, 60611, USA