Abstract.
The investigation of community structures in networks is an important issue in many domains and disciplines. In this paper we present a new class of local and fast algorithms which incorporate a quantitative definition of community. In this way the algorithms for the identification of the community structure become fully self-contained and one does not need additional non-topological information in order to evaluate the accuracy of the results. The new algorithms are tested on artificial and real-world graphs. In particular we show how the new algorithms apply to a network of scientific collaborations both in the unweighted and in the weighted version. Moreover we discuss the applicability of these algorithms to other non-social networks and we present preliminary results about the detection of community structures in networks of interacting proteins.
Similar content being viewed by others
References
R. Albert, A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002)
M.E.J. Newman, SIAM Review 45, 167 (2003)
R. Albert, H. Jeong, A.-L. Barabási, Nature 401, 130 (1999)
A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener, Computer Networks 33, 309 (2000)
C. Moore, M.E.J. Newman, Phys. Rev. E 61, 5678 (2000)
R. Pastor-Satorras, A. Vespignani, Phys. Rev. Lett. 86, 3200 (2001)
H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, A.-L. Barabási, Nature 407, 651 (2000)
A. Wagner, D. Fell, Proc. R. Soc. London B 268, 1803 (2001)
E. Ravasz, A. Somera, D.A. Mongru, Z.N. Oltvai, A.-L. Barabási, Science 297, 1551 (2002)
J.A. Dunne, R.J. Williams, N.D. Martinez, Proc. Natl. Acad. Sci. USA 99, 12917 (2002)
J. Camacho, R. Guimerá, L.A.N. Amaral, Phys. Rev. Lett. 88, 228102 (2002)
D. Garlaschelli, G. Caldarelli, L. Pietronero, Nature 423, 165 (2003)
S. Redner, Eur. Phys. J. B 4, 131 (1998)
M.E.J. Newman, Proc. Natl. Acad. Sci. USA 98, 404 (2001)
P. De Los Rios, Europhys. Lett. 56, 898 (2001)
A. Rives, T. Galitski, Proc. Natl. Acad. Sci. USA 100, 1128 (2003)
G.W. Flake, S.R. Lawrence, C.L. Giles, F.M. Coetzee, IEEE Computer 35, 66 (2002)
D. Wilkinson, B.A. Huberman, arXiv:cond-mat/0210147 (2002)
M.E.J. Newman, M. Girvan, Phys. Rev. E 69, 026116 (2004)
F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, D. Parisi, Proc. Natl. Acad. Sci. USA 101, 2658 (2004)
M.E.J. Newman, arXiv:cond-mat/0309508 (2003)
F. Wu, B.A. Huberman, arXiv:cond-mat/0310600 (2003)
S. Wasserman, K. Faust, Social Network Analysis (Cambridge Univ. Press, Cambridge, U.K., 1994)
M. Girvan, M.E.J. Newman, Proc. Natl. Acad. Sci. USA 99, 7821 (2002)
M.E.J. Newman, Phys. Rev. 64, 016131 (2001); U. Brandes, J. Mathematical Sociology 25, 163 (2001)
H. Zhou, Phys. Rev. E 67, 061901 (2003)
B. Bollobas, Random Graphs (Academic Press, New York, 1985)
W.W. Zachary, J. Anthrop. Res. 33, 452 (1977)
The comparison between the community structure in the network and the splitting of the club in two groups should be taken with care. While it is reasonable that the break-up pattern is correlated with the preexisting community structure, there is no reason to expect a perfect overlap. Therefore the misclassification of nodes is not an indication of the failure of the detection algorithm
M.E.J. Newman, J. Park, Phys. Rev. E 68, 036122 (2003)
R. Pastor-Satorras, A. Vásquez, A. Vespignani Phys. Rev. Lett. 87, 258701 (2001)
Q. Chen, H. Chang, R. Govindn, S. Jamin, S.J. Shenker, W. Willinger, Proceedings of the 21st Annaul Joint Conference of the IEEE Computer and Communications Societies, IEEE Computer Society (2002)
M.E.J. Newman, Phys. Rev. E. 67, 036126 (2003)
G. Caldarelli, R. Pastor-Satorras, A. Vespignani, arXiv:cond-mat/0212026 (2002)
G. Bianconi, A. Capocci, Phys. Rev. Lett. 90, 078701 (2003)
I. Xenarios, D.W. Rice, L. Salwinski, M.K. Baron, E.M. Marcotte, D. Eisenberg, Nuclelic Acids Res. 28, 289. The database is available at the web site http://dip.doe-mbi.ucla.edu/ (2000)
S.-H. Yook, Z.N. Oltvai, A.-L. Barabási, Proteomics 4, 928 (2004)
H.W. Mewes, D. Frishman, U. Guldener, G. Mannhaupt, K. Mayer, M. Mokrejs, B. Morgenstern, M. Munsterkotter, S. Rudd, B. Weil, Nucleic Acids Res 30, 31 (2002). The database is available at the web site http://mips.gsf.de/
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: 7 November 2003, Published online: 14 May 2004
PACS:
89.75.Hc Networks and genealogical trees - 87.23.Ge Dynamics of social systems - 87.90. + y Other topics in biological and medical physics
Rights and permissions
About this article
Cite this article
Castellano, C., Cecconi, F., Loreto, V. et al. Self-contained algorithms to detect communities in networks. Eur. Phys. J. B 38, 311–319 (2004). https://doi.org/10.1140/epjb/e2004-00123-0
Published:
Issue Date:
DOI: https://doi.org/10.1140/epjb/e2004-00123-0