Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks

Abstract

It is common in the study of networks to investigate meso-scale features to try to gain an understanding of network structure and function. For example, numerous algorithms have been developed to try to identify "communities," which are typically construed as sets of nodes with denser connections internally than with the remainder of a network. In this paper, we adopt a complementary perspective that "communities" are associated with bottlenecks of locally-biased dynamical processes that begin at seed sets of nodes, and we employ several different community-identification procedures (using diffusion-based and geodesic-based dynamics) to investigate community quality as a function of community size. Using several empirical and synthetic networks, we identify several distinct scenarios for ``size-resolved community structure'' that can arise in real (and realistic) networks. Depending on which scenario holds, one may or may not be able to successfully identify ``good'' communities in a given network, the manner in which different small communities fit together to form meso-scale network structures can be very different, and processes such as viral propagation and information diffusion can exhibit very different dynamics.In addition, our results suggest that, for many large realistic networks, the output of locally-biased methods that focus on communities that are centered around a given seed node might have better conceptual grounding and greater practical utility than the output of global community-detection methods. They also illustrate subtler structural properties that are important to consider in the development of better benchmark networks to test methods for community detection. [Note: Because of space limitations in the arXiv's abstract field, this is an abridged version of the paper's abstract.]

32 pages, 19 figures (many with multiple parts); the abstract is abridged because of space limitations in the arXiv's abstract field

References in corpus (18)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Structure and tie strengths in mobile communication networks
• Proceedings of the 29th International Conference on Machine Learning (ICML-12)
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Diffusion dynamics on multiplex networks
• Consensus clustering in complex networks
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Extracting the hierarchical organization of complex systems
• Robust Detection of Dynamic Community Structure in Networks
• Analysis of the structure of complex networks at different resolution levels
• Evaluating Local Community Methods in Networks

Cited by in corpus (15)

• Community detection in networks: A user guide
• Layer Communities in Multiplex Networks
• Random walks on complex networks under node-dependent stochastic resetting
• Community-Aware Graph Signal Processing
• Impact of network topology on efficiency of proximity measures for community detection
• Modular Networks for Validating Community Detection Algorithms
• Improving PageRank for Local Community Detection
• $p$-Norm Flow Diffusion for Local Graph Clustering
• Scalable and Robust Local Community Detection via Adaptive Subgraph Extraction and Diffusions
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• An Efficient Quadratic Penalty Method for a Class of Graph Clustering Problems
• Scalable Community Detection via Parallel Correlation Clustering
• Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddings
• ${\ell }_2$-norm Flow Diffusion in Near-Linear Time
• An optimization approach to locally-biased graph algorithms