Quantifying and identifying the overlapping community structure in networks
arXiv:0905.2666 · doi:10.1088/1742-5468/2009/07/P07042
Abstract
It has been shown that the communities of complex networks often overlap with each other. However, there is no effective method to quantify the overlapping community structure. In this paper, we propose a metric to address this problem. Instead of assuming that one node can only belong to one community, our metric assumes that a maximal clique only belongs to one community. In this way, the overlaps between communities are allowed. To identify the overlapping community structure, we construct a maximal clique network from the original network, and prove that the optimization of our metric on the original network is equivalent to the optimization of Newman's modularity on the maximal clique network. Thus the overlapping community structure can be identified through partitioning the maximal clique network using any modularity optimization method. The effectiveness of our metric is demonstrated by extensive tests on both the artificial networks and the real world networks with known community structure. The application to the word association network also reproduces excellent results.
9 pages, 7 figures
References in corpus (25)
- 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
- 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
- Functional cartography of complex metabolic networks
- Near linear time algorithm to detect community structures in large-scale networks
- Resolution limit in community detection
- Defining and identifying communities in networks
- Detecting the overlapping and hierarchical community structure of complex networks
- Community detection in complex networks using Extremal Optimization
- CFinder: Locating cliques and overlapping modules in biological networks
- Detect overlapping and hierarchical community structure in networks
- Line Graphs, Link Partitions and Overlapping Communities
- Extracting the hierarchical organization of complex systems
- Analysis of the structure of complex networks at different resolution levels
- Extending the definition of modularity to directed graphs with overlapping communities
- Weighted network modules
- Limited resolution in complex network community detection with Potts model approach
- Directed network modules
- Triangular clustering in document networks
Cited by in corpus (18)
- Community detection in graphs
- Overlapping Community Detection in Networks: the State of the Art and Comparative Study
- Line Graphs of Weighted Networks for Overlapping Communities
- Fuzzy overlapping communities in networks
- Spectral methods for the detection of network community structure: a comparative analysis
- Exploring the structural regularities in networks
- Uncovering the community structure associated with the diffusion dynamics of networks
- Covariance, correlation matrix and the multi-scale community structure of networks
- Modeling the clustering in citation networks
- GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
- Extraction of hidden information by efficient community detection in networks
- Extension of Modularity Density for Overlapping Community Structure
- Fast Detection of Community Structures using Graph Traversal in Social Networks
- Fuzzy Overlapping Community Quality Metrics
- Egomunities, Exploring Socially Cohesive Person-based Communities
- Bayesian Overlapping Community Detection in Dynamic Networks
- The Atlas for the Aspiring Network Scientist
- Metrics for Community Analysis: A Survey