Detecting the overlapping and hierarchical community structure of complex networks

Abstract

Many networks in nature, society and technology are characterized by a mesoscopic level of organization, with groups of nodes forming tightly connected units, called communities or modules, that are only weakly linked to each other. Uncovering this community structure is one of the most important problems in the field of complex networks. Networks often show a hierarchical organization, with communities embedded within other communities; moreover, nodes can be shared between different communities. Here we present the first algorithm that finds both overlapping communities and the hierarchical structure. The method is based on the local optimization of a fitness function. Community structure is revealed by peaks in the fitness histogram. The resolution can be tuned by a parameter enabling to investigate different hierarchical levels of organization. Tests on real and artificial networks give excellent results.

20 pages, 8 figures. Final version published on New Journal of Physics

References in corpus (25)

• 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
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• 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
• Hierarchical Structure in Financial Markets
• Self-similar community structure in organisations
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Synchronization reveals topological scales in complex networks
• Finding local community structure in networks
• Extracting the hierarchical organization of complex systems
• Analysis of the structure of complex networks at different resolution levels
• Subnetwork hierarchies of biochemical pathways
• Robustness of community structure in networks
• A Local Method for Detecting Communities
• Weighted network modules
• Limited resolution in complex network community detection with Potts model approach
• Synchronization processes in complex networks
• Structural Inference of Hierarchies in Networks

Cited by in corpus (213)

• Community detection in graphs
• Community detection algorithms: a comparative analysis
• Link communities reveal multiscale complexity in networks
• Community detection in networks: A user guide
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Consensus clustering in complex networks
• Finding overlapping communities in networks by label propagation
• Detect overlapping and hierarchical community structure in networks
• Line Graphs, Link Partitions and Overlapping Communities
• Limits of modularity maximization in community detection
• Community Discovery in Dynamic Networks: a Survey
• Memory in network flows and its effects on spreading dynamics and community detection
• Extending the definition of modularity to directed graphs with overlapping communities
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Community detection in node-attributed social networks: a survey
• A Classification for Community Discovery Methods in Complex Networks
• Detecting highly overlapping community structure by greedy clique expansion
• Characterizing the community structure of complex networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Multiresolution community detection for megascale networks by information-based replica correlations
• Community detection in networks: Structural communities versus ground truth
• Normalized Mutual Information to evaluate overlapping community finding algorithms
• Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
• Local resolution-limit-free Potts model for community detection
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• On community structure in complex networks: challenges and opportunities
• Community Structure of the Physical Review Citation Network
• Clique Graphs and Overlapping Communities
• Significant Scales in Community Structure
• Line Graphs of Weighted Networks for Overlapping Communities
• Fuzzy overlapping communities in networks
• Potential Theory for Directed Networks
• Quantifying and identifying the overlapping community structure in networks
• Resilience of networks with community structure behaves as if under an external field
• Large-scale structure of a nation-wide production network
• Element-centric clustering comparison unifies overlaps and hierarchy
• Structural transition in social networks: The role of homophily
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Connect and win: The role of social networks in political elections
• A Large-Scale Community Structure Analysis In Facebook
• Opinion and community formation in coevolving networks
• Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorization
• Modularity measure of networks with overlapping communities
• Multifractal Network Generator
• Spectral tripartitioning of networks
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• SLPA: Uncovering Overlapping Communities in Social Networks via A Speaker-listener Interaction Dynamic Process
• Median evidential c-means algorithm and its application to community detection
• Map equation for link community
• A network approach to cartel detection in public auction markets
• Finding and testing network communities by lumped Markov chains
• Multilayer weighted social network model
• Fundamental statistical features and self-similar properties of tagged networks
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• A New Metric for Quality of Network Community Structure
• Query-oriented text summarization based on hypergraph transversals
• Community structure and the evolution of interdisciplinarity in Slovenia's scientific collaboration network
• Exploring the solution landscape enables more reliable network community detection
• Markov random walk under constraint for discovering overlapping communities in complex networks
• A Survey of Hybrid Human-Artificial Intelligence for Social Computing
• Communities in Networks
• IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
• Clustering Memes in Social Media
• Tracking bitcoin users activity using community detection on a network of weak signals
• Fast consensus clustering in complex networks
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Followers Are Not Enough: A Question-Oriented Approach to Community Detection in Online Social Networks
• A testing based extraction algorithm for identifying significant communities in networks
• Limitation of multi-resolution methods in community detection
• Communities and beyond: mesoscopic analysis of a large social network with complementary methods
• Bi-Objective Community Detection (BOCD) in Networks using Genetic Algorithm
• Towards Linear Time Overlapping Community Detection in Social Networks
• Hierarchical Graph Clustering using Node Pair Sampling
• Detecting community structure in networks using edge prediction methods
• Significant communities in large sparse networks
• Leveraging disjoint communities for detecting overlapping community structure
• Overlapping Community Discovery Methods: A Survey
• Hierarchical community structure in networks
• Hierarchical benchmark graphs for testing community detection algorithms
• The inherent community structure of hyperbolic networks
• OLCPM: An Online Framework for Detecting Overlapping Communities in Dynamic Social Networks
• Information dynamics algorithm for detecting communities in networks
• Extracting tag hierarchies
• Efficient local behavioral change strategies to reduce the spread of epidemics in networks
• Dynamical origins of the community structure of multi-layer societies
• Memetic search for overlapping topics based on a local evaluation of link communities
• A Unified Method of Detecting Core-Periphery Structure and Community Structure in Networks
• On the evaluation potential of quality functions in community detection for different contexts
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Community detection in bipartite networks using weighted symmetric binary matrix factorization
• Improving the performance of algorithms to find communities in networks
• A linear streaming algorithm for community detection in very large networks
• Interconnections between networks act like an external field in first-order percolation transitions
• Identification of Overlapping Communities via Constrained Egonet Tensor Decomposition
• A density peaks clustering algorithm with sparse search and K-d tree
• Detecting Community Structure in Dynamic Social Networks Using the Concept of Leadership
• Identifying multi-scale communities in networks by asymptotic surprise
• Finding missing edges and communities in incomplete networks
• Discovering the hidden community structure of public transportation networks
• A similarity-based community detection method with multiple prototype representation
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Emergence of complex structures from nonlinear interactions and noise in coevolving networks
• Seeding for pervasively overlapping communities
• General Tensor Spectral Co-clustering for Higher-Order Data
• Extraction of hierarchical functional connectivity components in human brain using resting-state fMRI
• Fuzzy Overlapping Community Quality Metrics
• Clustering memes in social media streams
• Robustness of community structure to node removal
• Hierarchical organization of H. Eugene Stanley scientific collaboration community in weighted network representation
• Community detection based on significance optimization in complex networks
• Parallel clustering of high-dimensional social media data streams
• Global disorder transition in the community structure of large-q Potts systems
• The stability to instability transition in the structure of large scale networks
• Overlapping modularity at the critical point of k-clique percolation
• StaTIX - Statistical Type Inference on Linked Data
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• Scale-variant topological information for characterizing the structure of complex networks
• Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
• Modelling opinion formation driven communities in social networks
• Community Detection in Partially Observable Social Networks
• Community detection for networks with unipartite and bipartite structure
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Link community detection through global optimization and the inverse resolution limit of partition density
• Critical field-exponents for secure message-passing in modular networks
• Community Detection Across Multiple Social Networks based on Overlapping Users
• Ordered community structure in networks
• Eigenvector localization as a tool to study small communities in online social networks
• Formation of Modularity in a Model of Evolving Networks
• Online Tensor Methods for Learning Latent Variable Models
• Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time
• Discovering Social Circles in Ego Networks
• Nested partitions from hierarchical clustering statistical validation
• Scalable Spectral Algorithms for Community Detection in Directed Networks
• Identification of Overlapping Communities by Locally Calculating Community-Changing Resolution Levels
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• CommunityGAN: Community Detection with Generative Adversarial Nets
• Criterions for locally dense subgraphs
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Exploring triad-rich substructures by graph-theoretic characterizations in complex networks
• Off-Policy Evaluation of Probabilistic Identity Data in Lookalike Modeling
• Detecting network communities via greedy expanding based on local superiority index
• Graph Neural Network Encoding for Community Detection in Attribute Networks
• Obtaining Communities with a Fitness Growth Process
• Local multiresolution order in community detection
• Overlapping Communities in Social Networks
• Comparison and Benchmark of Graph Clustering Algorithms
• AOC; Assembling Overlapping Communities
• Detecting Statistically Significant Communities
• Community Detection in Networks: A Rough Sets and Consensus Clustering Approach
• Scaling Fine-grained Modularity Clustering for Massive Graphs
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Parallel Toolkit for Measuring the Quality of Network Community Structure
• Optimization of robustness based on reinforced nodes in a modular network
• Improving PageRank for Local Community Detection
• DANI: A Fast Diffusion Aware Network Inference Algorithm
• Bayesian Overlapping Community Detection in Dynamic Networks
• A Novel Metric Shows the Robustness of the Graph Communities to Brain-Tractography False-Positives
• The Atlas for the Aspiring Network Scientist
• Model Selection in Undirected Graphical Models with the Elastic Net
• Multi-scale graph principal component analysis for connectomics
• Estimating Network Parameters for Selecting Community Detection Algorithms
• Overlapping Community Detection in Temporal Text Networks
• Evaluating for Diversity in Question Generation over Text
• A multilevel clustering technique for community detection
• Using Model-based Overlapping Seed Expansion to detect highly overlapping community structure
• Metrics for Community Analysis: A Survey
• The effect of the pandemic on complex socio-economic systems: community detection induced by communicability
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Detecting Overlapping Link Communities by Finding Local Minima of a Cost Function with a Memetic Algorithm. Part 1: Problem and Method
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• From communities to interpretable network and word embedding: an unified approach
• A cognitive-inspired model for self-organizing networks
• ChartStory: Automated Partitioning, Layout, and Captioning of Charts into Comic-Style Narratives
• Overlapping community detection in networks via sparse spectral decomposition
• Community detection and tracking on networks from a data fusion perspective
• Evolutionary Multi Objective Optimization Algorithm for Community Detection in Complex Social Networks
• Further insights into the interareal connectivity of a cortical network
• A Generative Model for Exploring Structure Regularities in Attributed Networks
• Fast and reliable inference algorithm for hierarchical stochastic block models
• Community detection algorithm evaluation with ground-truth data
• A multilevel network approach to revealing patterns of online political selective exposure
• Trophic groups and modules: two levels of group detection in food webs
• Real-Time Community Detection in Large Social Networks on a Laptop
• Coalition Formation Algorithm of Prosumers in a Smart Grid Environment
• Clustering evolving data using kernel-based methods
• Partial order similarity based on mutual information
• Semi-Supervised Overlapping Community Finding based on Label Propagation with Pairwise Constraints
• Modeling Risk Perception in Networks with Community Structure
• Understanding Vulnerability of Communities in Complex Networks
• Analysis of Social Group Dynamics
• Overlapping community detection in weighted networks
• Graph clustering in industrial networks
• Optimisation dans la détection de communautés recouvrantes et équilibre de Nash
• Uncovering the Local Hidden Community Structure in Social Networks
• Coactivated Clique Based Multisource Overlapping Brain Subnetwork Extraction
• Improving Community Detection by Mining Social Interactions
• Partial Observability Approach for the Optimal Transparency Problem in Multi-agent Systems
• Searching for network modules
• Detección de comunidades en redes: Algoritmos y aplicaciones
• Semi-Supervised Deep Learning for Multiplex Networks
• Identification of hybrid node and link communities in complex networks
• Overlapping Community Detection Optimization and Nash Equilibrium
• Correlation-Based Community Detection
• Prior Signal Editing for Graph Filter Posterior Fairness Constraints
• Mining Application-aware Community Organization with Expanded Feature Subspaces from Concerned Attributes in Social Networks
• Opinion Divergence Reveals the Hierarchical and Overlapping Community Structure in Networks
• Overlapping Communities Detection via Measure Space Embedding
• Bayesian Modeling of Random Walker for Community Detection in Networks