Statistical Mechanics of Community Detection

Abstract

Starting from a general \textit{ansatz}, we show how community detection can be interpreted as finding the ground state of an infinite range spin glass. Our approach applies to weighted and directed networks alike. It contains the \textit{at hoc} introduced quality function from \cite{ReichardtPRL} and the modularity $Q$ as defined by Newman and Girvan \cite{Girvan03} as special cases. The community structure of the network is interpreted as the spin configuration that minimizes the energy of the spin glass with the spin states being the community indices. We elucidate the properties of the ground state configuration to give a concise definition of communities as cohesive subgroups in networks that is adaptive to the specific class of network under study. Further we show, how hierarchies and overlap in the community structure can be detected. Computationally effective local update rules for optimization procedures to find the ground state are given. We show how the \textit{ansatz} may be used to discover the community around a given node without detecting all communities in the full network and we give benchmarks for the performance of this extension. Finally, we give expectation values for the modularity of random graphs, which can be used in the assessment of statistical significance of community structure.

References in corpus (12)

• Finding and evaluating community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Specificity and stability in topology of protein networks
• Defining and identifying communities in networks
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Finding Communities in Linear Time: A Physics Approach
• Local modularity measure for network clusterizations
• Finding instabilities in the community structure of complex networks
• Eprints and the Open Archives Initiative

Cited by in corpus (314)

• Community detection in graphs
• From Louvain to Leiden: guaranteeing well-connected communities
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Characterization of complex networks: A survey of measurements
• Critical phenomena in complex networks
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Community detection in networks: A user guide
• A smart local moving algorithm for large-scale modularity-based community detection
• Community structure in directed networks
• Controllability of Brain Networks
• The performance of modularity maximization in practical contexts
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• An information-theoretic framework for resolving community structure in complex networks
• A High-Resolution Human Contact Network for Infectious Disease Transmission
• Modularity and community detection in bipartite networks
• Social Structure of Facebook Networks
• Hierarchical modularity in human brain functional networks
• Random walks and diffusion on networks
• Line Graphs, Link Partitions and Overlapping Communities
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Assessing Vaccination Sentiments with Online Social Media: Implications for Infectious Disease Dynamics and Control
• Limits of modularity maximization in community detection
• Robust Detection of Dynamic Community Structure in Networks
• Community detection in networks with positive and negative links
• Analysis of the structure of complex networks at different resolution levels
• Statistical physics of inference: Thresholds and algorithms
• Module identification in bipartite and directed networks
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Detecting network communities by propagating labels under constraints
• Uncovering space-independent communities in spatial networks
• Robustness of community structure in networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• A Bayesian Approach to Network Modularity
• A Classification for Community Discovery Methods in Complex Networks
• Dynamic fluctuations coincide with periods of high and low modularity in resting-state functional brain networks
• Analysis of community structure in networks of correlated data
• Modularity clustering is force-directed layout
• Parsimonious module inference in large networks
• Multiresolution community detection for megascale networks by information-based replica correlations
• Assessing the relevance of node features for network structure
• Community Detection as an Inference Problem
• Hiding Individuals and Communities in a Social Network
• Dynamic network drivers of seizure generation, propagation and termination in human epilepsy
• Evaluating Local Community Methods in Networks
• Local resolution-limit-free Potts model for community detection
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Limited resolution in complex network community detection with Potts model approach
• On community structure in complex networks: challenges and opportunities
• 20 years of network community detection
• The Diverse Club: The Integrative Core of Complex Networks
• Maximizing Modularity is hard
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Clique Graphs and Overlapping Communities
• Increasing trend of scientists to switch between topics
• Community detection for correlation matrices
• Significant Scales in Community Structure
• Revisiting Date and Party Hubs: Novel Approaches to Role Assignment in Protein Interaction Networks
• Diffusion on networked systems is a question of time or structure
• Line Graphs of Weighted Networks for Overlapping Communities
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Extraction of Force-Chain Network Architecture in Granular Materials Using Community Detection
• Faster unfolding of communities: speeding up the Louvain algorithm
• Multi-scale community organization of the human structural connectome and its relationship with resting-state functional connectivity
• Improved community structure detection using a modified fine tuning strategy
• The Influence of Network Topology on Sound Propagation in Granular Materials
• Role models for complex networks
• When are networks truly modular?
• ModuLand plug-in for Cytoscape: determination of hierarchical layers of overlapping network modules and community centrality
• Detecting communities using asymptotical Surprise
• Resolving structural variability in network models and the brain
• Surprise maximization reveals the community structure of complex networks
• Z-score-based modularity for community detection in networks
• The frustrated brain: From dynamics on motifs to communities and networks
• Spectral tripartitioning of networks
• Time-evolving controllability of effective connectivity networks during seizure progression
• Partitioning and modularity of graphs with arbitrary degree distribution
• On the relationship between the structural and socioacademic communities of a coauthorship network
• Real-time Event Detection on Social Data Streams
• Finding multiple core-periphery pairs in networks
• Statistical inference of assortative community structures
• Exploring the limits of community detection strategies in complex networks
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Resolving Structure in Human Brain Organization: Identifying Mesoscale Organization in Weighted Network Representations
• Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• The stability of a graph partition: A dynamics-based framework for community detection
• Exposing Fake Images with Forensic Similarity Graphs
• Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis
• Community Structure in the United Nations General Assembly
• Local dominance unveils clusters in networks
• Consistency of community structure in complex networks
• wTO: an R package for computing weighted topological overlap and consensus networks with an integrated visualization tool
• Will the US Economy Recover in 2010? A Minimal Spanning Tree Study
• Protein-Interaction-Networks: More than mere modules
• Trust transitivity in social networks
• Community structure: A comparative evaluation of community detection methods
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• A New Metric for Quality of Network Community Structure
• The strength of strong ties in scientific collaboration networks
• Accuracy and Precision of Methods for Community Identification in Weighted Networks
• Graph-based data clustering via multiscale community detection
• Magnetic eigenmaps for community detection in directed networks
• Large network community detection by fast label propagation
• Multiscale dynamical embeddings of complex networks
• Community detection in networks without observing edges
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Towards realistic artificial benchmark for community detection algorithms evaluation
• Network community-based model reduction for vortical flows
• Stability of spontaneous, correlated activity in mouse auditory cortex
• MPA network design based on graph network theory and emergent properties of larval dispersal
• Mesoscopic Community Structure of Financial Markets Revealed by Price and Sign Fluctuations
• Post-processing partitions to identify domains of modularity optimization
• Revealing In-Block Nestedness: detection and benchmarking
• Deterministic Modularity Optimization
• Limitation of multi-resolution methods in community detection
• Collective Decision Dynamics in the Presence of External Drivers
• Inversion method for content-based networks
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
• Axioms for graph clustering quality functions
• Stochastic block model and exploratory analysis in signed networks
• Measuring Significance of Community Structure in Complex Networks
• Multiscale core-periphery structure in a global liner shipping network
• Fast and accurate determination of modularity and its effect size
• Hierarchical Graph Clustering using Node Pair Sampling
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Comparing multiple networks using the Co-expression Differential Network Analysis (CoDiNA)
• Identifying vortical network connectors for turbulent flow modification
• Universality of the stochastic block model
• Functional brain modules reconfigure at multiple scales across the human lifespan
• Optimizing an Organized Modularity Measure for Topographic Graph Clustering: a Deterministic Annealing Approach
• The role of modularity in self-organisation dynamics in biological networks
• Quantum caustics in resonance fluorescence trajectories
• Mesoscale analyses of fungal networks as an approach for quantifying phenotypic traits
• Community Detection with and without Prior Information
• Network analyses reveal negative link between changes in adipose tissue GDF15 and BMI during dietary-induced weight loss
• Overlapping community detection in signed networks
• Hierarchical community structure in networks
• Hierarchical benchmark graphs for testing community detection algorithms
• Synwalk -- Community Detection via Random Walk Modelling
• Versatility of nodal affiliation to communities
• q-state Potts model on the Apollonian network
• eBay users form stable groups of common interest
• Representative community divisions of networks
• The relationship between acquaintanceship and coauthorship in scientific collaboration networks
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• Detecting modules in dense weighted networks with the Potts method
• Is academia becoming more localised? The growth of regional knowledge networks within international research collaboration
• Ensemble Clustering for Graphs
• Cell assembly dynamics of sparsely-connected inhibitory networks: a simple model for the collective activity of striatal projection neurons
• SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
• Ensemble Clustering for Graphs: Comparisons and Applications
• Walk modularity and community structure in networks
• Flickering emergences: The question of locality in information-theoretic approaches to emergence
• Modular organization of cancer signaling networks is associated with patient survivability
• Community detection in networks via nonlinear modularity eigenvectors
• A Graph Analysis of the Linked Data Cloud
• On Accuracy of Community Structure Discovery Algorithms
• Co-community Structure in Time-varying Networks
• Core of communities in bipartite networks
• Identifying multi-scale communities in networks by asymptotic surprise
• Discovering Network Structure Beyond Communities
• Modularity and Projection of Bipartite Networks
• Discovering link communities in complex networks by exploiting link dynamics
• Spectral methods and cluster structure in correlation-based networks
• Information theoretic network approach to socioeconomic correlations
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• Reading the Source Code of Social Ties
• Comparative analysis on the selection of number of clusters in community detection
• Label propagation for clustering
• Multislice Modularity Optimization in Community Detection and Image Segmentation
• Asymptotic resolution bounds of generalized modularity and multi-scale community detection
• An algebraic analysis of the graph modularity
• Community detection based on significance optimization in complex networks
• Geometric Multiscale Community Detection: Markov Stability and Vector Partitioning
• Finding overlapping communities in networks using evolutionary method
• Global disorder transition in the community structure of large-q Potts systems
• The stability to instability transition in the structure of large scale networks
• Graph coarse-graining reveals differences in the module-level structure of functional brain networks
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• The Mesh of Civilizations and International Email Flows
• An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering
• Multiple phases in modularity-based community detection
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• Maximal modularity and the optimal size of parliaments
• Quality functions in community detection
• Multiresolution Consensus Clustering in Networks
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• Analytical Formulation of the Block-Constrained Configuration Model
• Detecting the optimal number of communities in complex networks
• Hierarchical community detection by recursive partitioning
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Comparing Graph Clusterings: Set partition measures vs. Graph-aware measures
• Modularity in Multilayer Networks using Redundancy-based Resolution and Projection-based Inter-Layer Coupling
• A Review of Spatial Network Insights and Methods in the Context of Planning: Applications, Challenges, and Opportunities
• Infinite Multiple Membership Relational Modeling for Complex Networks
• Multi-scale Laplacian community detection in heterogeneous networks
• Multi-level algorithms for modularity clustering
• Generalized Markov stability of network communities
• Geosocial Graph-Based Community Detection
• Resolution Limits for Detecting Community Changes in Multilayer Networks
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
• A k-core Decomposition Framework for Graph Clustering
• Multi-modal Networks Reveal Patterns of Operational Similarity of Terrorist Organizations
• Criterions for locally dense subgraphs
• Multiscale Evolutionary Perturbation Attack on Community Detection
• On the reliable and efficient numerical integration of the Kuramoto model and related dynamical systems on graphs
• The Hyperspherical Geometry of Community Detection: Modularity as a Distance
• Mining the modular structure of protein interaction networks
• Measuring the effect of node aggregation on community detection
• Clustering online social network communities using genetic algorithms
• Convex Relaxation Methods for Community Detection
• Community detection in weighted brain connectivity networks beyond the resolution limit
• Communities in C.elegans connectome through the prism of non-backtracking walks
• Mapping robust multiscale communities in chromosome contact networks
• Community Detection Graph Convolutional Network for Overlap-Aware Speaker Diarization
• Matching Community Structure Across Online Social Networks
• Metrics matter in community detection
• Local multiresolution order in community detection
• Mutual information and the encoding of contingency tables
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Term-community-based topic detection with variable resolution
• An algorithm for network community structure determination by surprise
• Extending modularity by capturing the similarity attraction feature in the null model
• A Spectral Representation of Power Systems with Applications to Adaptive Grid Partitioning and Cascading Failure Localization
• Commonsense Reasoning and Large Network Analysis: A Computational Study of ConceptNet 4
• Community Detection on Networks with Ricci Flow
• Making Communities Show Respect for Order
• Finding Community Structure with Performance Guarantees in Complex Networks
• Evading Community Detection via Counterfactual Neighborhood Search
• Detection of hidden structures on all scales in amorphous materials and complex physical systems: basic notions and applications to networks, lattice systems, and glasses
• Community Detection in networks by Dynamical Optimal Transport Formulation
• Comparison and Benchmark of Graph Clustering Algorithms
• On weakly optimal partitions in modular networks
• Vulnerable Connectivity Caused by Local Communities in Spatial Networks
• Modular structure in labour networks reveals skill basins
• On the modularity of 3-regular random graphs and random graphs with given degree sequences
• A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme
• Complex networks and public funding: the case of the 2007-2013 Italian program
• Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm
• Polarization Rank: A Study on European News Consumption on Facebook
• Mesoscopic architecture enhances communication across the Macaque connectome revealing structure-function correspondence in the brain
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Community detection in bipartite signed networks is highly dependent on parameter choice
• Finding spin glass ground states through deep reinforcement learning
• The Atlas for the Aspiring Network Scientist
• Fast Topological Clustering with Wasserstein Distance
• Community detection analysis in wind speed-monitoring systems using mutual information-based complex network
• Flow-based Community Detection in Hypergraphs
• Bayesian Overlapping Community Detection in Dynamic Networks
• Ranking of Communities in Multiplex Spatiotemporal Models of Brain Dynamics
• Multi-scale graph principal component analysis for connectomics
• Communities of Minima in Local Optima Networks of Combinatorial Spaces
• TeCoMiner: Topic Discovery Through Term Community Detection
• The Importance of Being Negative: A serious treatment of non-trivial edges in brain functional connectome
• Metrics for Community Analysis: A Survey
• Community Detection Algorithm Combining Stochastic Block Model and Attribute Data Clustering
• Percolation Threshold for Competitive Influence in Random Networks
• Bad Communities with High Modularity
• A new method for quantifying network cyclic structure to improve community detection
• Clique-based Method for Social Network Clustering
• Leveraging Evolution Dynamics to Generate Benchmark Complex Networks with Community Structures
• A new measure of modularity density for community detection
• Real-Time Community Detection in Large Social Networks on a Laptop
• Small-world of communities: communication and correlation of the meta-network
• Mesoscale properties of mutualistic networks in ecosystems
• Low-rank Similarity Measure for Role Model Extraction
• Generic criticality of community structure in random graphs
• Skeleton coupling: a novel interlayer mapping of community evolution in temporal networks
• Vortical interactions in turbulent thermoacoustic systems
• Detecting hierarchical and overlapping network communities using locally optimal modularity changes
• Global decomposition of networks into multiple cores formed by local hubs
• Multiscale Community Mining in Networks Using Spectral Graph Wavelets
• A modified Ricci flow on arbitrary weighted graph
• A multilevel network approach to revealing patterns of online political selective exposure
• Sentiment-Driven Community Detection in a Network of Perfume Preferences
• From Leiden to Pleasure Island: The Constant Potts Model for Community Detection as a Hedonic Game
• Refinement for community structures of bipartite networks
• Scalable Community Detection via Parallel Correlation Clustering
• CellSegmenter: unsupervised representation learning and instance segmentation of modular images
• Overcoming Bias in Community Detection Evaluation
• Clustering evolving data using kernel-based methods
• Controlled Label Propagation: Preventing Over-Propagation through Gradual Expansion
• A new methodology for constructing a publication-level classification system of science
• Long-time tails in sheared fluids
• On Varying Topology of Complex Networks and Performance Limitations of Community Detection Algorithms
• Community Structure in Interaction Web Service Networks
• Detection of network inhomogeneity by total neighbor degree
• From Community Detection to Community Deception
• Community Integration Algorithms (CIAs) for Dynamical Systems on Networks
• Community Detection in the Network of German Princes in 1225: a Case Study
• Ground state energy of $q$-state Potts model: the minimum modularity
• Learning Graph Representations by Dendrograms
• Graph-Community Detection for Cross-Document Topic Segment Relationship Identification
• The Function of Communities in Protein Interaction Networks at Multiple Scales
• A framework for community detection in heterogeneous multi-relational networks
• Spiking label propagation for community detection
• Mind the gap in university rankings: a complex network approach towards fairness
• An Empirical Study of Compression-friendly Community Detection Methods
• Graph Clustering with Surprise: Complexity and Exact Solutions
• Interplay between Network Topology and Dynamics in Neural Systems
• SGPD Volume Maximization for Community Detection
• Community Structure and Topical Differentiation in European RTD Collaborations
• Modularity of regular and treelike graphs
• Learning Resolution Parameters for Graph Clustering
• Extraction of diverse gene groups with individual relationship from gene co-expression networks
• A Self-Organized Tower of Babel: Diversification through Competition
• Recommendation systems: a joint analysis of technical aspects with marketing implications