Uncovering the overlapping community structure of complex networks in nature and society

By Gergely Palla, Imre Derényi, Illés J. Farkas, Tamás Vicsek. Nature, 2005

5,425 citations recorded by the source corpus.

Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of. A key question is how to interpret the global organization of such networks as the coexistence of their structural subunits (communities) associated with more highly interconnected parts. Identifying these a priori unknown building blocks (such as functionally related proteins, industrial sectors and groups of people) is crucial to the understanding of the structural and functional properties of networks. The existing deterministic methods used for large networks find separated communities, whereas most of the actual networks are made of highly overlapping cohesive groups of nodes. Here we introduce an approach to analysing the main statistical features of the interwoven sets of overlapping communities that makes a step towards uncovering the modular structure of complex systems. After defining a set of new characteristic quantities for the statistics of communities, we apply an efficient technique for exploring overlapping communities on a large scale. We find that overlaps are significant, and the distributions we introduce reveal universal features of networks. Our studies of collaboration, word-association and protein interaction graphs show that the web of communities has non-trivial correlations and specific scaling properties.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

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

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

Dynamics and Control of Diseases in Networks with Community Structure (2010, background): “Despite the demonstration that social networks show significant community structure [15,16,17,18], and that social processes such as homophily and transitivity result in highly clustered and modular networks [19], the effect of such microstructures on epidemic dynamics has only recently started to b”
Finding community structure in networks using the eigenvectors of matrices. (2006, background): “Social networks [5], biochemical networks [7, 8, 9], and information networks such as the web [10], have all been shown to possess strong community structure, a ﬁnding that has substantial practical implications for our understanding of the systems these networks represent.”
Community Discovery in Dynamic Networks (2017, positive): “The algorithm proposed in (Palla et al. , 2007) is based on clique percolation (CPM (Palla et al. , 2005)).”
Hierarchical block structures and high-resolution model selection in large networks (2013, methodology): “This type of approach should, in principle, also be applicable to other model classes, such as those based on overlapping [9, 83–85], or link communities [25, 86].”
Community-Affiliation Graph Model for Overlapping Network Community Detection (2012, methodology): “To deal with this community detection algorithms based on identifying overlapping cliques [23], articulation points, as well as hierarchical clustering of”
Label Distribution Learning (2013, background): “Thus, all the labels with a non-zero description degree are actually the ‘correct’ labels to describe the instance, but just with different importance measured by d y x .”
Detecting highly overlapping community structure by greedy clique expansion (2010, methodology): “Similarly, in complex networks of interactions between proteins, it has been claimed that many proteins belong to multiple communities, each of which in turn corresponds to some biological function [8, 9].”
Modular Brain Networks (2015, methodology): “Clique percolation is one of the earliest methods for identifying overlapping communities (Palla et al. 2005).”