Finding statistically significant communities in networks

Abstract

Community structure is one of the main structural features of networks, revealing both their internal organization and the similarity of their elementary units. Despite the large variety of methods proposed to detect communities in graphs, there is a big need for multi-purpose techniques, able to handle different types of datasets and the subtleties of community structure. In this paper we present OSLOM (Order Statistics Local Optimization Method), the first method capable to detect clusters in networks accounting for edge directions, edge weights, overlapping communities, hierarchies and community dynamics. It is based on the local optimization of a fitness function expressing the statistical significance of clusters with respect to random fluctuations, which is estimated with tools of Extreme and Order Statistics. OSLOM can be used alone or as a refinement procedure of partitions/covers delivered by other techniques. We have also implemented sequential algorithms combining OSLOM with other fast techniques, so that the community structure of very large networks can be uncovered. Our method has a comparable performance as the best existing algorithms on artificial benchmark graphs. Several applications on real networks are shown as well. OSLOM is implemented in a freely available software (http://www.oslom.org), and we believe it will be a valuable tool in the analysis of networks.

24 pages, 25 figures, 1 table. Final version published in PLoS One. The code of OSLOM is freely available at http://www.oslom.org

References in corpus (43)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Error and attack tolerance of complex networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Functional cartography of complex metabolic networks
• Near linear time algorithm to detect community structures in large-scale networks
• Evolution of networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Hierarchical structure and the prediction of missing links in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Quantifying social group evolution
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The performance of modularity maximization in practical contexts
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Finding overlapping communities in networks by label propagation
• Line Graphs, Link Partitions and Overlapping Communities
• Extracting the hierarchical organization of complex systems
• Fuzzy communities and the concept of bridgeness in complex networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Subnetwork hierarchies of biochemical pathways
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Towards real-time community detection in large networks
• Characterizing the community structure of complex networks
• Assessing the relevance of node features for network structure
• Structural Inference of Hierarchies in Networks
• Statistical significance of communities in networks
• When are networks truly modular?
• Partitioning and modularity of graphs with arbitrary degree distribution
• Combinatorial approach to Modularity

Cited by in corpus (153)

• Community detection in networks: A user guide
• Human Mobility: Models and Applications
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Consensus clustering in complex networks
• Social physics
• Limits of modularity maximization in community detection
• Memory in network flows and its effects on spreading dynamics and community detection
• Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach
• Social features of online networks: the strength of intermediary ties in online social media
• Community detection in networks: Structural communities versus ground truth
• Nestedness in complex networks: Observation, emergence, and implications
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Systemic delay propagation in the US airport network
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• 20 years of network community detection
• Online Popularity and Topical Interests through the Lens of Instagram
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Detection of gene communities in multi-networks reveals cancer drivers
• Mixing local and global information for community detection in large networks
• Significant Scales in Community Structure
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Entropy of stochastic blockmodel ensembles
• Analyzing complex functional brain networks: fusing statistics and network science to understand the brain
• Faster unfolding of communities: speeding up the Louvain algorithm
• Element-centric clustering comparison unifies overlaps and hierarchy
• Social significance of community structure: Statistical view
• Enhancing community detection using a network weighting strategy
• Detecting communities using asymptotical Surprise
• A Large-Scale Community Structure Analysis In Facebook
• Comparing and modeling land use organization in cities
• Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering
• Finding missing edges in networks based on their community structure
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Exploring the limits of community detection strategies in complex networks
• Distinguishing Topical and Social Groups Based on Common Identity and Bond Theory
• Finding and testing network communities by lumped Markov chains
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• Community structure: A comparative evaluation of community detection methods
• People are Strange when you're a Stranger: Impact and Influence of Bots on Social Networks
• Multi-scale analysis of the European airspace using network community detection
• Community structure and the evolution of interdisciplinarity in Slovenia's scientific collaboration network
• Human diffusion and city influence
• Community detection in networks using graph embeddings
• IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
• Followers Are Not Enough: A Question-Oriented Approach to Community Detection in Online Social Networks
• Compression of Flow Can Reveal Overlapping-Module Organization in Networks
• Mixed Membership Estimation for Social Networks
• A testing based extraction algorithm for identifying significant communities in networks
• Multilevel Hierarchical Kernel Spectral Clustering for Real-Life Large Scale Complex Networks
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Community Detection in Quantum Complex Networks
• Significant communities in large sparse networks
• Community detection using boundary nodes in complex networks
• In a World That Counts: Clustering and Detecting Fake Social Engagement at Scale
• Leveraging disjoint communities for detecting overlapping community structure
• A Mathematical Theory for Clustering in Metric Spaces
• Overlapping Community Discovery Methods: A Survey
• Hierarchical community structure in networks
• Hierarchical benchmark graphs for testing community detection algorithms
• A generalised significance test for individual communities in networks
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• Community extraction in multilayer networks with heterogeneous community structure
• Modularity-based approach for tracking communities in dynamic social networks
• Dynamical origins of the community structure of multi-layer societies
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Improving the performance of algorithms to find communities in networks
• An Enhanced Multi-Objective Biogeography-Based Optimization for Overlapping Community Detection in Social Networks with Node Attributes
• Community Detection in Dynamic Networks via Adaptive Label Propagation
• Identification of Overlapping Communities via Constrained Egonet Tensor Decomposition
• Enhancing community detection by local structural information
• Biogeographical network analysis of plant species distribution in the Mediterranean region
• Closed benchmarks for network community structure characterization
• Simplex2Vec embeddings for community detection in simplicial complexes
• Core of communities in bipartite networks
• Community detection using preference networks
• Detecting Overlapping Communities from Local Spectral Subspaces
• Discovering Network Structure Beyond Communities
• Emergence of scale-free close-knit friendship structure in online social networks
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Mapping flows on weighted and directed networks with incomplete observations
• An Improved Phrase-based Approach to Annotating and Summarizing Student Course Responses
• Extraction of hierarchical functional connectivity components in human brain using resting-state fMRI
• Dynamics in online social networks
• Temporal stability of network partitions
• Topical alignment in online social systems
• Identifying Topical Twitter Communities via User List Aggregation
• Community detection based on significance optimization in complex networks
• Finding overlapping communities in networks using evolutionary method
• Graph coarse-graining reveals differences in the module-level structure of functional brain networks
• Weighted Community Detection and Data Clustering Using Message Passing
• Growing networks of overlapping communities with internal structure
• Resampling effects on significance analysis of network clustering and ranking
• Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
• Generalization of Clustering Agreements and Distances for Overlapping Clusters and Network Communities
• The Probabilistic Backbone of Data-Driven Complex Networks: An example in Climate
• An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Link community detection through global optimization and the inverse resolution limit of partition density
• Ordered community structure in networks
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Voter model on networks partitioned into two cliques of arbitrary sizes
• Bioregionalization analyses with the bioregion R-package
• Generalized Markov stability of network communities
• Criterions for locally dense subgraphs
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• DANI: Fast Diffusion Aware Network Inference with Preserving Topological Structure Property
• Exploring triad-rich substructures by graph-theoretic characterizations in complex networks
• Local multiresolution order in community detection
• Off-Policy Evaluation of Probabilistic Identity Data in Lookalike Modeling
• Statistical Characteristics and Community analysis of Urban Road Networks
• Detecting Statistically Significant Communities
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Comparison and Benchmark of Graph Clustering Algorithms
• Evolving community structure in the international pesticide trade networks
• Graph clustering with Boltzmann machines
• Building the MSR Tool Kaiaulu: Design Principles and Experiences
• Clubmark: a Parallel Isolation Framework for Benchmarking and Profiling Clustering Algorithms on NUMA Architectures
• Shaping Communities out of Triangles
• Animal daily mobility patterns analysis using resting event networks
• The Atlas for the Aspiring Network Scientist
• Bayesian Overlapping Community Detection in Dynamic Networks
• Trusses and Trapezes: Easily-Interpreted Communities in Social Networks
• Graph Clustering Via QUBO and Digital Annealing
• Metrics for Community Analysis: A Survey
• Smoothness Sensor: Adaptive Smoothness-Transition Graph Convolutions for Attributed Graph Clustering
• A new method for community detection in social networks based on message distribution
• The way to uncover community structure with core and diversity
• Krylov Subspace Approximation for Local Community Detection in Large Networks
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• Overlapping community detection in networks via sparse spectral decomposition
• Community Detection in Weighted Multilayer Networks with Ambient Noise
• Improving community detection via community association strength scores
• ECHO: Encoding Communities via High-order Operators
• From communities to interpretable network and word embedding: an unified approach
• Streaming Local Community Detection through Approximate Conductance
• Understanding Information Flow in Cascades Using Network Motifs
• An analysis of community structure in Brazilian political topic-based Twitter networks
• Ensembles based on the Rich-Club and how to use them to build soft-communities
• Une nouvelle mesure pour l'évaluation des méthodes de détection de communautés
• Community Detection by a Riemannian Projected Proximal Gradient Method
• Consistency of regularized spectral clustering in degree-corrected mixed membership model
• Understanding Vulnerability of Communities in Complex Networks
• Large Deviation Principle for the Exploration Process of the Configuration Model
• Community membership consistency applied to corporate board interlock networks
• Sparse Nonnegative Matrix Factorization for Multiple Local Community Detection
• The efficiency of community detection by most similar node pairs
• Reinventing the Triangles: Rule of Thumb for Assessing Detectability
• Binomial Tails for Community Analysis
• Dynamic Virtual Graph Significance Networks for Predicting Influenza
• Structure Amplification on Multi-layer Stochastic Block Models
• Uncovering the Local Hidden Community Structure in Social Networks