Quantifying and identifying the overlapping community structure in networks

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 (12)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Near linear time algorithm to detect community structures in large-scale networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Detect overlapping and hierarchical community structure in networks
• Line Graphs, Link Partitions and Overlapping Communities
• 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