Detection of node group membership in networks with group overlap

Abstract

Most networks found in social and biochemical systems have modular structures. An important question prompted by the modularity of these networks is whether nodes can be said to belong to a single group. If they cannot, we would need to consider the role of "overlapping communities." Despite some efforts in this direction, the problem of detecting overlapping groups remains unsolved because there is neither a formal definition of overlapping community, nor an ensemble of networks with which to test the performance of group detection algorithms when nodes can belong to more than one group. Here, we introduce an ensemble of networks with overlapping groups. We then apply three group identification methods--modularity maximization, k-clique percolation, and modularity-landscape surveying--to these networks. We find that the modularity-landscape surveying method is the only one able to detect heterogeneities in node memberships, and that those heterogeneities are only detectable when the overlap is small. Surprisingly, we find that the k-clique percolation method is unable to detect node membership for the overlapping case.

12 pages, 6 figures. To appear in Euro. Phys. J B

References in corpus (21)

• Finding and evaluating community structure in networks
• Modularity and 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
• Functional cartography of complex metabolic networks
• Resolution limit in community detection
• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Community detection in complex networks using Extremal Optimization
• Identity and Search in Social Networks
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Synchronization reveals topological scales in complex networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Extracting the hierarchical organization of complex systems
• Properties of highly clustered networks
• Fuzzy communities and the concept of bridgeness in complex networks
• Detecting Network Communities: a new systematic and efficient algorithm
• Community Detection as an Inference Problem
• Limited resolution in complex network community detection with Potts model approach
• Finding instabilities in the community structure of complex networks

Cited by in corpus (12)

• Community detection in graphs
• Community detection algorithms: a comparative analysis
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The performance of modularity maximization in practical contexts
• Missing and spurious interactions and the reconstruction of complex networks
• Community Discovery in Dynamic Networks: a Survey
• Characterizing the community structure of complex networks
• Clique Graphs and Overlapping Communities
• Line Graphs of Weighted Networks for Overlapping Communities
• Fuzzy overlapping communities in networks
• Random Graph Modeling: A survey of the concepts
• Seeding for pervasively overlapping communities