https://doi.org/10.1140/epjb/e2004-00123-0
Self-contained algorithms to detect communities in networks
1
Dipartimento di Fisica, Università di Roma “La Sapienza”
and INFM-SMC, Unità di Roma 1, P.le A. Moro 5, 00185 Roma, Italy
2
Istituto di Scienze e Tecnologie della Cognizione, C.N.R.,
Viale Marx, 15, 00137, Roma, Italy
3
Dipartimento di Fisica, Università di Roma “Tor Vergata”,
Via della Ricerca Scientifica 1, 00133 Roma, Italy
Corresponding author: a loreto@roma1.infn.it
Received:
7
November
2003
Published online:
14
May
2004
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.
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
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2004