An information-theoretic framework for resolving community structure in complex networks

Abstract

To understand the structure of a large-scale biological, social, or technological network, it can be helpful to decompose the network into smaller subunits or modules. In this article, we develop an information-theoretic foundation for the concept of modularity in networks. We identify the modules of which the network is composed by finding an optimal compression of its topology, capitalizing on regularities in its structure. We explain the advantages of this approach and illustrate them by partitioning a number of real-world and model networks.

5 pages, 4 figures

References in corpus (18)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and 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
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Functional cartography of complex metabolic networks
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Statistical Mechanics of Community Detection
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Subnetwork hierarchies of biochemical pathways
• Modularity and Extreme Edges of the Internet
• When are networks truly modular?
• An Information-Theoretic Approach to Network Modularity

Cited by in corpus (151)

• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• The structure and dynamics of multilayer networks
• Community detection algorithms: a comparative analysis
• Stochastic blockmodels and community structure in networks
• Community structure in directed networks
• The performance of modularity maximization in practical contexts
• Mathematical Formulation of Multi-Layer Networks
• The map equation
• Social physics
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Clustering and Community Detection in Directed Networks: A Survey
• Centrality in Interconnected Multilayer Networks
• Narrow scope for resolution-limit-free community detection
• Robustness of community structure in networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• A sequential algorithm for fast clique percolation
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Identifying the Community Structure of the International-Trade Multi Network
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Efficiently inferring community structure in bipartite networks
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Spectral entropies as information-theoretic tools for complex network comparison
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Modeling sequences and temporal networks with dynamic community structures
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Estimating the number of communities in a network
• Improved community structure detection using a modified fine tuning strategy
• Bayesian stochastic blockmodeling
• Role models for complex networks
• Random walk centrality in interconnected multilayer networks
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Spectral methods for the detection of network community structure: a comparative analysis
• Z-score-based modularity for community detection in networks
• Density-based and transport-based core-periphery structures in networks
• A New Approach to Analyzing Patterns of Collaboration in Co-authorship Networks - Mesoscopic Analysis and Interpretation
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• Consistencies and inconsistencies between model selection and link prediction in networks
• Exploring the structural regularities in networks
• Consistency of community structure in complex networks
• Protein-Interaction-Networks: More than mere modules
• Community structure: A comparative evaluation of community detection methods
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Mesoscopic Structures Reveal the Network Between the Layers of Multiplex Datasets
• Link prediction based on path entropy
• Uncovering the community structure associated with the diffusion dynamics of networks
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• Covariance, correlation matrix and the multi-scale community structure of networks
• Large network community detection by fast label propagation
• Implicit Contextual Integrity in Online Social Networks
• Drivers of social influence in the Twitter migration to Mastodon
• Towards realistic artificial benchmark for community detection algorithms evaluation
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Network structure, metadata and the prediction of missing nodes and annotations
• Multilayer Network Science: from Cells to Societies
• Efficient community-based control strategies in adaptive networks
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Laplacian paths in complex networks: information core emerges from entropic transitions
• Detecting Cohesive and 2-mode Communities in Directed and Undirected Networks
• Community detection using boundary nodes in complex networks
• Significant communities in large sparse networks
• Leveraging disjoint communities for detecting overlapping community structure
• Modularity functions maximization with nonnegative relaxation facilitates community detection in networks
• A Mathematical Theory for Clustering in Metric Spaces
• Reinforced communication and social navigation generate groups in model networks
• Model validation of simple-graph representations of metabolism
• Representative community divisions of networks
• The Minimum Description Length Principle for Pattern Mining: A Survey
• Entropic one-class classifiers
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Community Detection in Dynamic Networks via Adaptive Label Propagation
• Sustainable Development Goals as unifying narratives in large UK firms' Twitter discussions
• Spatial regionalization based on optimal information compression
• The Infinite Degree Corrected Stochastic Block Model
• Sampling promotes community structure in social and information networks
• On Accuracy of Community Structure Discovery Algorithms
• Patterns of trading profiles at the Nordic Stock Exchange. A correlation-based approach
• Large-scale network motif analysis using compression
• Community detection using preference networks
• Dynamic Analyses of Contagion Risk and Module Evolution on the SSE A-Shares Market Based on Minimum Information Entropy
• Discovering Network Structure Beyond Communities
• A unified data representation theory for network visualization, ordering and coarse-graining
• Information sharing in Quantum Complex Networks
• Graph animals, subgraph sampling and motif search in large networks
• Multiple Hybrid Phase Transition: Bootstrap Percolation on Complex Networks with Communities
• Characterization of the community structure in a large-scale production network in Japan
• Extracting replicable associations across multiple studies: algorithms for controlling the false discovery rate
• Multi-resolution community detection in massive networks
• Detecting Communities in Tripartite Hypergraphs
• Variational Community Partition with Novel Network Structure Centrality Prior
• Inference for graphs and networks: Extending classical tools to modern data
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Overlapping modularity at the critical point of k-clique percolation
• A data-driven framework for dimensionality reduction and causal inference in climate fields
• Resampling effects on significance analysis of network clustering and ranking
• Synchronization Invariance Under Network Structural Transformations
• An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering
• Community detection based on "clumpiness" matrix in complex networks
• On the Permanence of Vertices in Network Communities
• Filtering higher-order datasets
• Compressing network populations with modal networks reveals structural diversity
• Comparing Graph Clusterings: Set partition measures vs. Graph-aware measures
• Modules in the metabolic network of E.coli with regulatory interactions
• Clarifying How Degree Entropies and Degree-Degree Correlations Relate to Network Robustness
• Regular Decomposition: an information and graph theoretic approach to stochastic block models
• Detecting groups of similar components in complex networks
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Decoding communities in networks
• Organizational structure and communication networks in a university environment
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Generalized network community detection
• Entrograms and coarse graining of dynamics on complex networks
• Metrics matter in community detection
• Criterions for locally dense subgraphs
• The art of community detection
• Active Learning for Hidden Attributes in Networks
• One-class classifiers based on entropic spanning graphs
• Mapping leadership and communities in EU-funded research through network analysis
• Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm
• Community Structure Characterization
• Modular decomposition of Markov chain: detecting hierarchical organization of pervasive communities
• Community detection analysis in wind speed-monitoring systems using mutual information-based complex network
• Considerations about multistep community detection
• SCOREH+: A High-Order Node Proximity Spectral Clustering on Ratios-of-Eigenvectors Algorithm for Community Detection
• Router-level community structure of the Internet Autonomous Systems
• Metrics for Community Analysis: A Survey
• Transforming complex network to the acyclic one
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Stochastic graph Voronoi tessellation reveals community structure
• Quantitative Function and Algorithm for Community Detection in Bipartite Networks
• Resolving Author Name Homonymy to Improve Resolution of Structures in Co-author Networks
• Une nouvelle mesure pour l'évaluation des méthodes de détection de communautés
• On role extraction for digraphs via neighbourhood pattern similarity
• An analysis of community structure in Brazilian political topic-based Twitter networks
• Universal Approximation of Edge Density in Large Graphs
• An Efficient homophilic model and Algorithms for Community Detection using Nash Dynamics
• VoG: Summarizing and Understanding Large Graphs
• The Extraction of Community Structures from Publication Networks to Support Ethnographic Observations of Field Differences in Scientific Communication
• Bayesian Modeling of Random Walker for Community Detection in Networks
• Toward Efficient Testing of Graph Neural Networks via Test Input Prioritization
• Beyond One Solution: The Case for a Comprehensive Exploration of Solution Space in Community Detection
• A Survey on Role-Oriented Network Embedding
• Visualizing Uncertainty in Probabilistic Graphs with Network Hypothetical Outcome Plots (NetHOPs)
• Understanding Vulnerability of Communities in Complex Networks
• Flow approaches to community detection in complex network systems
• Analysis of Social Group Dynamics