Uncovering the overlapping community structure of complex networks in nature and society
arXiv:physics/0506133 · doi:10.1038/nature03607
Abstract
Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of. A key question is how to interpret the global organization of such networks as the coexistence of their structural subunits (communities) associated with more highly interconnected parts. Identifying these a priori unknown building blocks (such as functionally related proteins, industrial sectors and groups of people) is crucial to the understanding of the structural and functional properties of networks. The existing deterministic methods used for large networks find separated communities, whereas most of the actual networks are made of highly overlapping cohesive groups of nodes. Here we introduce an approach to analysing the main statistical features of the interwoven sets of overlapping communities that makes a step towards uncovering the modular structure of complex systems. After defining a set of new characteristic quantities for the statistics of communities, we apply an efficient technique for exploring overlapping communities on a large scale. We find that overlaps are significant, and the distributions we introduce reveal universal features of networks. Our studies of collaboration, word-association and protein interaction graphs show that the web of communities has non-trivial correlations and specific scaling properties.
The free academic research software, CFinder, used for the publication is available at the website of the publication: http://angel.elte.hu/clustering
References in corpus (3)
Cited by in corpus (324)
- Fast unfolding of communities in large networks
- Finding community structure in networks using the eigenvectors of matrices
- Maps of random walks on complex networks reveal community structure
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Evolutionary games on graphs
- Comparing community structure identification
- The Product Space Conditions the Development of Nations
- Hierarchical structure and the prediction of missing links in networks
- Statistical Mechanics of Community Detection
- Detecting the overlapping and hierarchical community structure of complex networks
- Structure and tie strengths in mobile communication networks
- Community detection in networks: A user guide
- Quantifying social group evolution
- Finding statistically significant communities in networks
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- Weight-conserving characterization of complex functional brain networks
- CFinder: Locating cliques and overlapping modules in biological networks
- Statistical physics of vaccination
- Consensus clustering in complex networks
- An information-theoretic framework for resolving community structure in complex networks
- Modularity and community detection in bipartite networks
- Communicability in complex networks
- Detect overlapping and hierarchical community structure in networks
- Line Graphs, Link Partitions and Overlapping Communities
- Mixture models and exploratory analysis in networks
- Community detection in networks with positive and negative links
- Analysis of the structure of complex networks at different resolution levels
- Understanding brain networks and brain organization
- Percolation on complex networks: Theory and application
- How to calculate the fractal dimension of a complex network: the box covering algorithm
- Extending the definition of modularity to directed graphs with overlapping communities
- Cooperation in noisy case: prisoner's dilemma game on two types of regular random graphs
- A Classification for Community Discovery Methods in Complex Networks
- Towards real-time community detection in large networks
- Triadic closure as a basic generating mechanism of communities in complex networks
- Analysis of community structure in networks of correlated data
- Characterizing the community structure of complex networks
- Weighted network modules
- Community detection in networks: Structural communities versus ground truth
- A sequential algorithm for fast clique percolation
- Emergence of communities in weighted networks
- The clustering coefficient and community structure of bipartite networks
- Identification of core-periphery structure in networks
- Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
- Robust network community detection using balanced propagation
- Evaluating Local Community Methods in Networks
- Limited resolution in complex network community detection with Potts model approach
- Identifying network communities with a high resolution
- 20 years of network community detection
- GED: the method for group evolution discovery in social networks
- Statistical physics approaches to the complex Earth system
- Spectral entropies as information-theoretic tools for complex network comparison
- Community Structure in Congressional Cosponsorship Networks
- Synchronization processes in complex networks
- Communities, Knowledge Creation, and Information Diffusion
- Clustering in complex networks. I. General formalism
- A system of mobile agents to model social networks
- Worldwide spreading of economic crisis
- Clique Graphs and Overlapping Communities
- Spectral coarse-graining of complex networks
- Creative elements: network-based predictions of active centres in proteins, cellular and social networks
- Assortative mixing in Protein Contact Networks and protein folding kinetics
- Quantifying and identifying the overlapping community structure in networks
- Bi-clique Communities
- Core percolation on complex networks
- Role models for complex networks
- Opportunistic Routing Based on Daily Routines
- Articulation Points in Complex Networks
- Social significance of community structure: Statistical view
- When are networks truly modular?
- k-Core percolation on multiplex networks
- Directed network modules
- Enhancing community detection using a network weighting strategy
- Dynamical Systems on Networks: A Tutorial
- The Naming Game in Social Networks: Community Formation and Consensus Engineering
- Alignment and integration of complex networks by hypergraph-based spectral clustering
- Collective synchronization induced by epidemic dynamics on complex networks with communities
- Directed clustering in weighted networks: a new perspective
- 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
- The low-rank hypothesis of complex systems
- Multifractal Network Generator
- A New Comparative Definition of Community and Corresponding Identifying Algorithm
- Spectral tripartitioning of networks
- Stress-induced rearrangements of cellular networks: consequences for protection and drug design
- Partitioning and modularity of graphs with arbitrary degree distribution
- Community structure of complex software systems: Analysis and applications
- Chaperones as integrators of cellular networks: Changes of cellular integrity in stress and diseases
- Data-driven Computational Social Science: A Survey
- Assessing the consistency of community structure in complex networks
- Communicability Graph and Community Structures in Complex Networks
- The structural role of weak and strong links in a financial market network
- Note on the equivalence of the label propagation method of community detection and a Potts model approach
- Preferential attachment of communities: the same principle, but a higher level
- Qualitative Comparison of Community Detection Algorithms
- Local dominance unveils clusters in networks
- Fundamental statistical features and self-similar properties of tagged networks
- Social cohesion, structural holes, and a tale of two measures
- Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
- Network clique cover approximation to analyze complex contagions through group interactions
- Community structure and the evolution of interdisciplinarity in Slovenia's scientific collaboration network
- Potts model based on a Markov process computation solves the community structure problem effectively
- Covariance, correlation matrix and the multi-scale community structure of networks
- Anomalous lifetime distributions and topological traps in ordering dynamics
- Multi-scale Modularity in Complex Networks
- Number of cliques in random scale-free network ensembles
- Practical Attacks Against Graph-based Clustering
- Markov random walk under constraint for discovering overlapping communities in complex networks
- Spectral and network methods in the analysis of correlation matrices of stock returns
- Detecting Overlapping Communities in Networks Using Spectral Methods
- Structure and Overlaps of Communities in Networks
- Immunization Strategies Based on the Overlapping Nodes in Networks with Community Structure
- Perspective: network-guided pattern formation of neural dynamics
- Detection of node group membership in networks with group overlap
- Deterministic Modularity Optimization
- Detecting Communities in Networks by Merging Cliques
- Inversion method for content-based networks
- From Quantum Chemistry to Networks in Biology: A Graph Spectral Approach to Protein Structure Analyses
- Topological properties and fractal analysis of recurrence network constructed from fractional Brownian motions
- Predicting Community Evolution in Social Networks
- How to become a superhero
- The critical point of k-clique percolation in the Erdos-Renyi graph
- Stochastic block model and exploratory analysis in signed networks
- Fractal and complex network analyses of protein molecular dynamics
- Modeling the emergence of modular leadership hierarchy during the collective motion of herds made of harems
- Fast and accurate determination of modularity and its effect size
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- Spatiotemporal correlations of handset-based service usages
- Disentangling homophily, community structure and triadic closure in networks
- Finding network communities using modularity density
- Community structures and role detection in music networks
- Reconstructing networks
- Broad lifetime distributions for ordering dynamics in complex networks
- Homological percolation transitions in growing simplicial complexes
- Fractal and multifractal analysis of complex networks: Estonian network of payments
- Spectral Detection of Simplicial Communities via Hodge Laplacians
- Communicability and multipartite structures in complex networks at negative absolute temperatures
- Tracking and Predicting Evolution of Social Communities
- Leveraging disjoint communities for detecting overlapping community structure
- Impact of hierarchical modular structure on ranking of individual nodes in directed networks
- Overlapping Community Discovery Methods: A Survey
- Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks
- Genetic Algorithm with Ensemble Learning for Detecting Community Structure in Complex Networks
- Spectral transitions in networks
- Revealing and exploiting hierarchical material structure through complex atomic networks
- Identification of Group Changes in Blogosphere
- Dynamics of the threshold model on hypergraphs
- Community detection and Social Network analysis based on the Italian wars of the 15th century
- Detecting modules in dense weighted networks with the Potts method
- Synchronizability of chaotic logistic maps in delayed complex networks
- Synchronization over and community detection in multiplex signed networks with constraints
- Structure of n-clique networks embedded in a complex network
- Identifying overlapping communities in social networks using multi-scale local information expansion
- Surveying the side-chain network approach to protein structure and dynamics: The SARS-CoV-2 spike protein as an illustrative case
- Topological basis of signal integration in the transcriptional-regulatory network of the yeast, Saccharomyces cerevisiae
- Phase of Ising spins on modular networks analogous to social polarization
- Contact Tracing Enhances the Efficiency of COVID-19 Group Testing
- Multiscale Network Generation
- Sampling promotes community structure in social and information networks
- Scaling theory of fractal complex networks
- Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks
- Effect of size heterogeneity on community identification in complex networks
- Hyperlink communities in higher-order networks
- Dynamic Multi-Factor Clustering of Financial Networks
- Discovering link communities in complex networks by exploiting link dynamics
- Spectral methods and cluster structure in correlation-based networks
- Network clustering and community detection using modulus of families of loops
- Local degree blocking model for link prediction in complex networks
- Evolving network structure of academic institutions
- Hierarchical core-periphery structure in networks
- How to design multi-target drugs: Target search options in cellular networks
- Discovering Patterns in Time-Varying Graphs: A Triclustering Approach
- An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
- Node mixing and group structure of complex software networks
- Egomunities, Exploring Socially Cohesive Person-based Communities
- Interplay between HIV/AIDS Epidemics and Demographic Structures Based on Sexual Contact Networks
- Partition of Networks into Basins of Attraction
- Centrality properties of directed module members in social networks
- Identifying Stress Responsive Genes using Overlapping Communities in Co-expression Networks
- Cycle Analysis of Directed Acyclic Graphs
- A Method for Group Extraction and Analysis in Multilayer Social Networks
- Community structure revealed by phase locking
- Nested Subgraphs of Complex Networks
- Resampling effects on significance analysis of network clustering and ranking
- Lumping of Degree-Based Mean Field and Pair Approximation Equations for Multi-State Contact Processes
- Minimum Long-Loop Feedback Vertex Set and Network Dismantling
- Subdivisions and Crossroads: Identifying Hidden Community Structures in a Data Archive's Citation Network
- K-Scaffold subgraphs of Complex networks
- Fast Complex Network Clustering Algorithm Using Agents
- Robustness of community structure under edge addition
- Triangles to Capture Social Cohesion
- Heterogeneous Network Motifs
- Efficient Bayesian Community Detection using Non-negative Matrix Factorisation
- Consistent Community Identification in Complex Networks
- Discovering Social Circles in Ego Networks
- POISED: Spotting Twitter Spam Off the Beaten Paths
- Classifying Clustering Schemes
- Eigenvector localization as a tool to study small communities in online social networks
- Hochschild homology, and a persistent approach via connectivity digraphs
- Evidential Communities for Complex Networks
- Emergence of Clustering in an Acquaintance Model without Homophily
- Identifying Influential Nodes Using Overlapping Modularity Vitality
- Clique percolation method: memory efficient almost exact communities
- Rise of QAnon: A Mental Model of Good and Evil Stews in an Echochamber
- Model-based clustering in networks with Stochastic Community Finding
- Defining and Evaluating Network Communities based on Ground-truth
- Discovering Nested Communities
- Diophantine Networks
- Topic-aware latent models for representation learning on networks
- Topics in social network analysis and network science
- Ising-Based Louvain Method: Clustering Large Graphs with Specialized Hardware
- Group fairness without demographics using social networks
- Some remarks on modularity density
- Identifying robust features of community structure in complex networks
- Mutual information and the encoding of contingency tables
- Overlapping Communities in Social Networks
- The art of community detection
- A Spatial Logic for Simplicial Models
- Modeling Social Networks with Overlapping Communities Using Hypergraphs and Their Line Graphs
- Compressive Network Analysis
- Growing Hypergraphs with Preferential Linking
- AOC; Assembling Overlapping Communities
- On Efficiently Detecting Overlapping Communities over Distributed Dynamic Graphs
- Shaping Communities out of Triangles
- Clustering attributed graphs: models, measures and methods
- Evolving complex networks with conserved clique distributions
- A bibliometric approach to Systematic Mapping Studies: The case of the evolution and perspectives of community detection in complex networks
- Graph fractal dimension and structure of fractal networks: a combinatorial perspective
- Community detection in hypergraphs through hyperedge percolation
- NISQ-ready community detection based on separation-node identification
- Community detection by resistance distance: automation and benchmark testing
- Trusses and Trapezes: Easily-Interpreted Communities in Social Networks
- SamWalker++: recommendation with informative sampling strategy
- Providing an Approach to Predicting Customer Quality in E-Commerce Social Networks Based on Big Data and Unsupervised Learning Method
- Parallel clustering with CFinder
- Overlapping Community Detection in Temporal Text Networks
- De-anonymizing Social Networks with Overlapping Community Structure
- Hidden Community Detection in Social Networks
- Motif Clustering and Overlapping Clustering for Social Network Analysis
- Network-based analysis of fluid flows: Progress and outlook
- GRM: Group Regularity Mobility Model
- Complex Contagions and hybrid phase transitions in unclustered and clustered random networks
- Random walk based snapshot clustering for detecting community dynamics in temporal networks
- Using Model-based Overlapping Seed Expansion to detect highly overlapping community structure
- Tourists Profiling by Interest Analysis
- Hub-collision avoidance and leaf-node options algorithm for fractal dimension and renormalization of complex networks
- Clustering of tag-induced sub-graphs in complex networks
- Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
- Fast Graphlet Transform of Sparse Graphs
- A Continuous Opinion Dynamic Model in Co-evolving Networks--A Novel Group Decision Approach
- Analysis of Coauthorship Network in Political Science using Centrality Measures
- Around Average Behavior: 3-lambda Network Model
- Potential energy of complex networks: a novel perspective
- Small world is not enough: Criteria for network choice and conclusiveness of simulations
- Network analysis of protein dynamics
- Fair treatment allocations in social networks
- Trophic groups and modules: two levels of group detection in food webs
- Hybrid evolving clique-networks and their communicability
- Sampling node group structure of social and information networks
- Link Analysis for Communities Detection on Facebook
- Values That Are Explicitly Present in Fairy Tales: Comparing Samples from German, Italian and Portuguese Traditions
- Reconstructing propagation networks with temporal similarity metrics
- Kernelization Algorithms for Packing Problems Allowing Overlaps (Extended Version)
- Clustering evolving data using kernel-based methods
- Faster maximal clique enumeration in large real-world link streams
- Skeleton coupling: a novel interlayer mapping of community evolution in temporal networks
- Extracting Hidden Groups and their Structure from Streaming Interaction Data
- Spectral Analysis of Dow Jones Index and Comparison with Model Predicted Cycles During 1900-2005
- Network compression with configuration models and the minimum description length
- Overlapping Community Detection Using Neighborhood-Inflated Seed Expansion
- On role extraction for digraphs via neighbourhood pattern similarity
- Learning Asynchronous-Time Information Diffusion Models and its Application to Behavioral Data Analysis over Social Networks
- Percolation Computation in Complex Networks
- Predicting Group Evolution in the Social Network
- A Note on Community Trees in Networks
- Community detection algorithm evaluation with ground-truth data
- Beyond One Solution: The Case for a Comprehensive Exploration of Solution Space in Community Detection
- Cognitive computation with autonomously active neural networks: an emerging field
- Overlapping Communities in Complex Networks
- Homophilic organization of egocentric communities in ICT services
- A Local Approach for Identifying Clusters in Networks
- A Hierarchical Security Events Correlation Model for Real-time Cyber Threat Detection and Response
- Cascading failures in anisotropic interdependent networks of spatial modular structures
- Contact Tracing Information Improves the Performance of Group Testing Algorithms
- Community Structure and Topical Differentiation in European RTD Collaborations
- Analysis of Social Group Dynamics
- Building Mini-Categories in Product Networks
- Multi-Likelihood Methods for Developing Stock Relationship Networks Using Financial Big Data
- Modeling Protein Contact Networks
- Models of Social Groups in Blogosphere Based on Information about Comment Addressees and Sentiments
- Overlapping community detection in weighted networks
- Empirical Network Structure of Malicious Programs
- Controlling nosocomial infection based on structure of hospital social networks
- MOHCS: Towards Mining Overlapping Highly Connected Subgraphs
- A new fast algorithm for reproducing complex networks with community structure
- Coactivated Clique Based Multisource Overlapping Brain Subnetwork Extraction
- Statistical Behavior of Embeddedness and Communities of Overlapping Cliques in Online Social Networks
- Overlapping Community Structure in Co-authorship Networks: a Case Study
- Structural Entropy of the Stochastic Block Models
- A Sketch Based Game Theoretic Approach to Detect Anomalous Dense Sub-Communities in Large Data Streams
- On the Estimation and Use of Statistical Modelling in Information Retrieval
- Multiplex Structures: Patterns of Complexity in Real-World Networks
- Overlapping Community Detection by Local Decentralised Vertex-centred Process
- Rigidity percolation in random 3D rod systems
- Networks with degree-degree correlations is a special case of edge-coloured random graphs
- Detección de comunidades en redes: Algoritmos y aplicaciones
- Estimate Metabolite Taxonomy and Structure with a Fragment-Centered Database and Fragment Network
- A Maximum Entropy approach to Massive Graph Spectra
- Dynamic Structural Clustering on Graphs
- Structure Amplification on Multi-layer Stochastic Block Models
- Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering
- Competing spreading dynamics in simplicial complex
- Group Evolution Discovery in Social Networks
- Local Core Members Aided Community Structure Detection
- Model Selection in Overlapping Stochastic Block Models
- Expertise localization discovered through correlation of key term distribution and community detection in co-author networks
- An efficient high-quality hierarchical clustering algorithm for automatic inference of software architecture from the source code of a software system
- Fast Adaptively Weighted Matrix Factorization for Recommendation with Implicit Feedback
- Detecting overlapping community structure: Estonian network of payments
- Overlapping Community Detection Optimization and Nash Equilibrium
- A Threshold For Clusters in Real-World Random Networks
- Ranking and Cooperation in Real-World Complex Networks