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.]

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

References in corpus (51)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Community detection in graphs
• 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
• Multilayer Networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Statistical Mechanics of Community Detection
• Link communities reveal multiscale complexity in networks
• Structure and tie strengths in mobile communication networks
• Dynamic reconfiguration of human brain networks during learning
• Proceedings of the 29th International Conference on Machine Learning (ICML-12)
• Finding statistically significant communities in networks
• Intensity and coherence of motifs in weighted complex networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Diffusion dynamics on multiplex networks
• The performance of modularity maximization in practical contexts
• Mathematical Formulation of Multi-Layer Networks
• Synchronization reveals topological scales in complex networks
• Consensus clustering in complex networks
• Generalizations of the clustering coefficient to weighted complex networks
• Social Structure of Facebook Networks
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Random Walks on Multiplex Networks
• 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
• An efficient and principled method for detecting communities in networks
• Structure and dynamics of core-periphery networks
• Uncovering space-independent communities in spatial networks
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• A Local Method for Detecting Communities
• Evaluating Local Community Methods in Networks
• Binary-state dynamics on complex networks: pair approximation and beyond
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• The unreasonable effectiveness of tree-based theory for networks with clustering
• The Influence of Network Topology on Sound Propagation in Granular Materials
• Community structure and ethnic preferences in school friendship networks
• An Information-Theoretic Approach to Network Modularity
• Ranking and clustering of nodes in networks with smart teleportation
• Flow graphs: interweaving dynamics and structure
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Interest communities and flow roles in directed networks: the Twitter network of the UK riots
• Towards realistic artificial benchmark for community detection algorithms evaluation
• Multiscale Dynamics in Communities of Phase Oscillators
• Network Structure, Topology and Dynamics in Generalized Models of Synchronization
• Invited review: Epidemics on social networks

Cited by in corpus (44)

• Community detection in networks: A user guide
• Random walks and diffusion on networks
• Network Analysis of Particles and Grains
• Topological data analysis of contagion maps for examining spreading processes on networks
• Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths
• Flow-based network analysis of the Caenorhabditis elegans connectome
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Layer Communities in Multiplex Networks
• Random walks on complex networks with first-passage resetting
• Hierarchical community structure in networks
• Capacity Releasing Diffusion for Speed and Locality
• Random walks on complex networks under node-dependent stochastic resetting
• Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering
• Community-Aware Graph Signal Processing
• Seeded PageRank Solution Paths
• Local Graph Clustering with Network Lasso
• Targeted Pandemic Containment Through Identifying Local Contact Network Bottlenecks
• A Simple and Strongly-Local Flow-Based Method for Cut Improvement
• From Spectra to Localized Networks: A Reverse Engineering Approach
• Impact of network topology on efficiency of proximity measures for community detection
• A Short Introduction to Local Graph Clustering Methods and Software
• Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Identifying robust features of community structure in complex networks
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Modular Networks for Validating Community Detection Algorithms
• Stochastic Block Models are a Discrete Surface Tension
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Improving PageRank for Local Community Detection
• $p$-Norm Flow Diffusion for Local Graph Clustering
• The Atlas for the Aspiring Network Scientist
• Learning from learning machines: a new generation of AI technology to meet the needs of science
• Parallel Local Graph Clustering
• 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 and Robust Local Community Detection via Adaptive Subgraph Extraction and Diffusions
• Finding community structure using the ordered random graph model
• Scalable Community Detection via Parallel Correlation Clustering
• Krylov Subspace Approximation for Local Community Detection in Large Networks
• Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddings
• An optimization approach to locally-biased graph algorithms
• Graph clustering in industrial networks
• Network construction: A learning framework through localizing principal eigenvector
• ${\ell }_2$-norm Flow Diffusion in Near-Linear Time
• Ensemble-based Overlapping Community Detection using Disjoint Community Structures