Detection of node group membership in networks with group overlap

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 ef...

Full description

Saved in:
Bibliographic Details
Published in:The European physical journal. B, Condensed matter physics Condensed matter physics, 2009-02, Vol.67 (3), p.277-284
Main Authors: Sawardecker, E. N., Sales-Pardo, M., Amaral, L. A.N.
Format: Article
Language:English
Subjects:
Complex Systems
Condensed Matter Physics
Exact sciences and technology
Fluid- and Aerodynamics
Interdisciplinary Physics
Physics
Physics and Astronomy
Solid State Physics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1434-6028
1434-6036
DOI:10.1140/epjb/e2008-00418-0