Detecting communities in large networks

By Andrea Capocci, V. Servedio, Guido Caldarelli, F. Colaiori. 2004

308 citations recorded by the source corpus.

We develop an algorithm to detect community structure in complex networks. The algorithm is based on spectral methods and takes into account weights and link orientation. Since the method detects efficiently clustered nodes in large networks even when these are not sharply partitioned, it turns to be specially suitable for the analysis of social and information networks. We test the algorithm on a large-scale data-set from a psychological experiment of word association. In this case, it proves to be successful both in clustering words, and in uncovering mental association patterns.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/94aa37850131858bcb83cf391b1b85b439553694

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

1. Santo Fortunato
2. M. A. Porter
3. Peter J. Mucha
4. Michalis Vazirgiannis
5. Fragkiskos D. Malliaros
6. Claudio Castellano
7. Francisco Aparecido Rodrigues
8. Jukka-Pekka Onnela

In Statistical and Nonlinear Physics

1. M. A. Porter
2. Santo Fortunato
3. Peter J. Mucha
4. Olaf Sporns
5. Michalis Vazirgiannis
6. Fragkiskos D. Malliaros
7. Claudio Castellano
8. Francisco Aparecido Rodrigues

Citations in the corpus

• Analyzing and modeling real-world phenomena with complex networks: a survey of applications (2007, background): “Using this syntactic dependence network for the Romanian language [483], it was also shown that spectral methods developed to detect community structure [484] can be useful to group words of the same class.”
• Community Structure in Graphs (2007, result): “Similarly to Donetti and Mu˜noz, Capocci et al. used eigenvector components to identify communities [64].”
• Finding community structure in networks using the eigenvectors of matrices. (2006, methodology): “In this paper we focus on one approach to community detection that has proven particularly effective, the optimization of the benefit function known as “modu-larity” over the possible divisions of a network.”
• Clustering and Community Detection in Directed Networks: A Survey (2013, background): “[81] presented an approach where the underlying community structure is revealed by correlations between the same components of different eigenvectors.”
• Communities in Networks (2009, background): “ne then applies two-group partitioning recursively to the smaller networks one obtains as long as it is desirable to do so. (One can also partition networks into more than two groups during each step [21,29,86,107].) For a single partitioning step, one defines an index vector s whose components take ”
• Community detection in graphs (2009, methodology): “Capocci et al. derived a similarity matrix, where the similarity between vertices i and j is the Pearson correlation coefficient between their corresponding eigenvector components, averaged over a small set of eigenvectors.”
• Characterization of complex networks: A survey of measurements (2005, methodology): “sions. Although spectral bisection is easy to implement, it tends to be a poor approach for detecting communities in real networks [130]. There are many alternative methods based on spectral analysis [133], to be found in [127, 128]. Recently, Newman [134] proposed a method which reformulates the mo”