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

Self-contained algorithms to detect communities in networks

¹ 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

Corresponding author: ^a 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.