Defining and identifying communities in networks.

By Filippo Radicchi, Claudio Castellano, F. Cecconi, Vittorio Loreto, Domenico Parisi. Proceedings of the National Academy of Sciences of the United States of America, 2003

2,435 citations recorded by the source corpus.

The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic and protein networks), or technological problems (optimization of large infrastructures). Several types of algorithms exist for revealing the community structure in networks, but a general and quantitative definition of community is not implemented in the algorithms, leading to an intrinsic difficulty in the interpretation of the results without any additional nontopological information. In this article we deal with this problem by showing how quantitative definitions of community are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability. The algorithm is tested on artificial and real-world graphs. In particular, we show how the algorithm applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods. This type of local algorithm could open the way to applications to large-scale technological and biological systems.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/a2b2a5d3d4c8d35663236a9548076327cfc685ca

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

In Statistical and Nonlinear Physics

Citations in the corpus

Community detection in graphs (2009, methodology): “For instance, a high edge density inside a cluster usually means that there are also several triangles in the cluster, and compara- tively few between clusters, a criterion that has inspired on its own popular graph clustering algorithms (Palla et al., 2005; Radicchi et al., 2004).”
Using Geodesic Space Density Gradients for Network Community Detection (2017, methodology): “[45] defined a strong community as a group of nodes with each node having more connections within the group than with the rest of the graph and a weak community has the sum of all degrees within the group larger than the sum of all degrees toward the rest of the network.”
GA-Net: A Genetic Algorithm for Community Detection in Social Networks (2008, background): “[20] propose two quantitative definitions of community and an algorithm to identify communities.”
Graph theory and networks in Biology. (2006, background): “In [68, 137, 150, 61] the notions of betweenness and information centrality were first extended to apply to edges rather than nodes.”
Multiscale Community Blockmodel for Network Exploration (2011, methodology): “Finally, methods such as Clauset et al. (2004), Radicchi et al. (2004) and Kemp et al. (2008) explicitly model some form of organizational structure, but do not permit actors to have multiple kinds of interactions, which precludes them from learning the kind of multiscale interactions we have…”
Big Data and supply chain management: a review and bibliometric analysis (2016, methodology): “To conduct data clustering (1) we placed nodes so that links of nodes within the same cluster are dense compared to the nodes belonging in different clusters (Clauset et al. 2004; Leydesdorff 2011; Radicchi et al. 2004).”
What's in a crowd? Analysis of face-to-face behavioral networks (2010, background): “While the concepts of node failures and targeted attacks are pertinent for infrastructure networks, successive removals of nodes or links is more generally a way to study network structures (Holme et al., 2002; Girvan and Newman, 2002; Radicchi et al., 2004; Dall’Asta et al., 2006).”