Link communities reveal multiscale complexity in networks

By Yong-Yeol Ahn, James P. Bagrow, Sune Lehmann. Nature, 2009

1,946 citations recorded by the source corpus.

Networks have become a key approach to understanding systems of interacting objects, unifying the study of diverse phenomena including biological organisms and human society. One crucial step when studying the structure and dynamics of networks is to identify communities: groups of related nodes that correspond to functional subunits such as protein complexes or social spheres. Communities in networks often overlap such that nodes simultaneously belong to several groups. Meanwhile, many networks are known to possess hierarchical organization, where communities are recursively grouped into a hierarchical structure. However, the fact that many real networks have communities with pervasive overlap, where each and every node belongs to more than one group, has the consequence that a global hierarchy of nodes cannot capture the relationships between overlapping groups. Here we reinvent communities as groups of links rather than nodes and show that this unorthodox approach successfully reconciles the antagonistic organizing principles of overlapping communities and hierarchy. In contrast to the existing literature, which has entirely focused on grouping nodes, link communities naturally incorporate overlap while revealing hierarchical organization. We find relevant link communities in many networks, including major biological networks such as protein–protein interaction and metabolic networks, and show that a large social network contains hierarchically organized community structures spanning inner-city to regional scales while maintaining pervasive overlap. Our results imply that link communities are fundamental building blocks that reveal overlap and hierarchical organization in networks to be two aspects of the same phenomenon.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

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

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

Overlapping community detection at scale: a nonnegative matrix factorization approach (2013, methodology): “However, nodes in these communities contain attributes and [1] used “purity” metrics as surrogates for the quality of detected communities.”
Measuring Large-Scale Social Networks with High Resolution (2014, background): “Recently, we pointed out that communities in many real world networks display pervasive overlap, where each and every node belongs to more than one group [131].”
Communities, modules and large-scale structure in networks (2011, neutral): “(The generalized community-detection problem in which overlaps are allowed in this way has been an area of increasing interest within the field in recent years 22,31 .)”
Community detection in networks: A user guide (2016, methodology): “However, when one turns edge communities into vertex communities, multiple relationships can be still recovered [94].”
Learning to Discover Social Circles in Ego Networks (2012, methodology): “Conversely we considered Link Clustering [1] and Clique Percolation [21], which use network information, but ignore proﬁles.”
Multi-scale brain networks (2016, neutral): “They range both in terms of how they define communities and also their computational complexity (Palla et al., 2005; Ahn et al., 2010; Rosvall and Bergstrom, 2008; Delvenne et al., 2010; Karrer and Newman, 2011).”
Virality Prediction and Community Structure in Social Networks (2013, methodology): “Here we propose that network communities [30–32]—strongly clustered groups of people—provide a unique vantage point to the challenge of predicting viral memes.”
Efficient discovery of overlapping communities in massive networks (2013, methodology): “In this sense, our algorithm discovers link communities (2, 9).”
Overlapping Communities Explain Core–Periphery Organization of Networks (2014, methodology): “However, in many domains, nodes may belong to multiple communities at once, and thus the notion of structural communities has also been extended to include overlapping, hierarchical, and disassortative community structures [6], [31]–[34].”
Walklets: Multiscale Graph Embeddings for Interpretable Network Classification (2016, background): “Multiscale Community Detection Many techniques for detecting multiple scales of discrete communities in graphs have been proposed [1, 10, 15].”
Modular Brain Networks (2015, positive): “A second approach for clustering a network's line graph, proposed by Ahn et al. (2010), weights line graph connections according to their similarity (Jaccard index).”
Inferring gene ontologies from pairwise similarity data (2014, methodology): “Another relevant method has been proposed that hierarchically clusters links in a graph rather than edges (Ahn et al ., 2010).”