Issue Eur. Phys. J. B Volume 38, Number 2, March II 2004 Applications of Networks Page(s) 311 - 319 Section Interdisciplinary Results DOI 10.1140/epjb/e2004-00123-0 Published online 14 May 2004

Eur. Phys. J. B 38, 311-319 (2004)
DOI: 10.1140/epjb/e2004-00123-0

Self-contained algorithms to detect communities in networks

C. Castellano¹, F. Cecconi², V. Loreto¹, D. Parisi² and F. Radicchi<sup>3

1</sup>  Dipartimento di Fisica, Università di Roma "La Sapienza" and INFM-SMC, Unità di Roma 1, P.le A. Moro 5, 00185 Roma, Italy
²  Istituto di Scienze e Tecnologie della Cognizione, C.N.R., Viale Marx, 15, 00137, Roma, Italy
³  Dipartimento di Fisica, Università di Roma "Tor Vergata", Via della Ricerca Scientifica 1, 00133 Roma, Italy

loreto@roma1.infn.it

(Received 7 November 2003 / Published online 14 May 2004)

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.

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

What is OpenURL?