Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
By Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, Michael W. Mahoney. 2008
2,059 citations recorded by the source corpus.
A large body of work has been devoted to defining and identifying clusters or communities in social and information networks, i.e., in graphs in which the nodes represent underlying social entities and the edges represent some sort of interaction between pairs of nodes. Most such research begins with the premise that a community or a cluster should be thought of as a set of nodes that has more and/or better connections between its members than to the remainder of the network. In this paper, we explore from a novel perspective several questions related to identifying meaningful communities in large social and information networks, and we come to several striking conclusions. Rather than defining a procedure to extract sets of nodes from a graph and then attempting to interpret these sets as "real" communities, we employ approximation algorithms for the graph-partitioning problem to characterize as a function of size the statistical and structural properties of partitions of graphs that could plausibly be interpreted as communities. In particular, we define the network community profile plot, which characterizes the "best" possible community—according to the conductance measure—over a wide range of size scales. We study over one hundred large real-world networks, ranging from traditional and online social networks, to technological and information networks and web graphs, and ranging in size from thousands up to tens of millions of nodes. Our results suggest a significantly more refined picture of community structure in large networks than has been appreciated previously. Our observations agree with previous work on small networks, but we show that large networks have a very different structure. In particular, we observe tight communities that are barely connected to the rest of the network at very small size scales (up to ≈ 100 nodes); and communities of size scale beyond ≈ 100 nodes gradually "blend into" the expander-like core of the network and thus become less "community-like," with a roughly inverse relationship between community size and optimal community quality. This observation agrees well with the so-called Dunbar number, which gives a limit to the size of a well-functioning community. However, this behavior is not explained, even at a qualitative level, by any of the commonly used network-generation models. Moreover, it is exactly the opposite of what one would expect based on intuition from expander graphs, low-dimensional or manifold-like graphs, and from small social networks that have served as test beds of community-detection algorithms. The relatively gradual increase of the network community profile plot as a function of increasing community size depends in a subtle manner on the way in which local clustering information is propagated from smaller to larger size scales in the network. We have found that a generative graph model, in which new edges are added via an iterative "forest fire" burning process, is able to produce graphs exhibiting a network community profile plot similar to what we observe in our network data sets.
Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics, Graph Learning, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Jure Leskovec
- Jaewon Yang
- Ion Stoica
- Michael W. Mahoney
- Joseph E. Gonzalez
- Tiago P. Peixoto
- M. Franklin
- Darko Hric
In Statistical and Nonlinear Physics
- Jure Leskovec
- Santo Fortunato
- Jaewon Yang
- Tiago P. Peixoto
- Darko Hric
- Michael W. Mahoney
- Kevin J. Lang
- M. A. Porter
In Graph Learning
- Jure Leskovec
- Jaewon Yang
- William L. Hamilton
- Julian McAuley
- Michael W. Mahoney
- Tiago P. Peixoto
- Michalis Vazirgiannis
- Jon M. Kleinberg
In Algorithms & Complexity
- Jure Leskovec
- Jaewon Yang
- Remco van der Hofstad
- Grant Robert Schoenebeck
- M. A. Porter
- Michalis Vazirgiannis
- Peter J. Mucha
- Darko Hric
Citations in the corpus
- Representation Learning on Graphs with Jumping Knowledge Networks (2018, background): “Social and web networks usually consist of an expander-like core part and an almost-tree (bounded treewidth) part, which represent well-connected entities and the small communities respectively (Leskovec et al., 2009; Maehara et al., 2014; Tsonis et al., 2006).”
- Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems (2010, background): “The network with the highest compression gain — i.e., the network with the greatest degree of nested hierarchical structure — is the California road network (23).”
- Handbook of Big Data (2016, background): “As typical graphs get larger and larger, much of the local structure does not change or grow [33,57]; instead, one simply observes more and more varied pockets of local structure.”
- PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs (2012, neutral): “Furthermore, power-law graphs are difficult to partition [1, 28] and represent in a distributed environment.”
- Overlapping community detection at scale: a nonnegative matrix factorization approach (2013, neutral): “Even though methods for identifying overlapping as well as hierarchically-nested communities in networks have been considered in the past [1, 2, 25, 32], identifying meaningful communities in large networks has proven to be a challenging task [9, 20, 34].”
- LASAGNE: Locality and Structure Aware Graph Node Embedding (2017, methodology): “The selection of networks captures different structures, and we use Network Community Profile (NCP) plots from [8, 9, 10, 11] to analyze them.”
- Listing All Maximal Cliques in Large Sparse Real-World Graphs (2011, neutral): “21 roadNet-TX [34] 1,379,917 1,921,660 3 1,763,318 * 1.”
- GraphX: a resilient distributed graph system on Spark (2013, methodology): “In contrast to edge-cuts which have been shown [8, 1, 7] to perform poorly on real-world graphs, there are theoretical [2] and experimental [6] results indicating that real-world graphs have good vertex-cuts.”
- Overlapping community detection in networks: The state-of-the-art and comparative study (2011, methodology): “Email: a communication network in Enron via emails [Leskovec et al. 2009].”
- GraphX: Graph Processing in a Distributed Dataflow Framework (2014, methodology): “However, the GAS decomposition also prohibits direct communication between vertices that are not adjacent in the graph and therefore hinders the expression of more general communication patterns. def Gather(a: Double, b: Double) = a + b def Apply(v, msgSum) { PR(v) = 0.15 + 0.85 * msgSum if…”
- A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning (2021, neutral): “Computer Science [145] 22,000 96,800 Chemistry [145] 35,400 157,400 Medicine [145] 63,300 810,300 Engineering [145] 14,900 49,300 Others Amazon [139] 334,863 925,872 Google [146] 875,000 4,320,000”
- Community detection in networks: A user guide (2016, background): “This view has been challenged, recently (Jeub et al., 2015; Leskovec et al., 2009), as we shall see in Section III.”
- Vital nodes identification in complex networks (2016, background): “Networks n m kmax c H Amazon 334863 925872 549 0.3967 2.0856 Cond-mat 27519 116181 202 0.6546 2.6393 Email-Enron 36692 183831 1383 0.4970 13.9796 Facebook 63731 817090 1098 0.2210 3.4331 from Jan. 1st, 1995 to Jun. 30th, 2003.”