Seeding for pervasively overlapping communities

Abstract

In some social and biological networks, the majority of nodes belong to multiple communities. It has recently been shown that a number of the algorithms that are designed to detect overlapping communities do not perform well in such highly overlapping settings. Here, we consider one class of these algorithms, those which optimize a local fitness measure, typically by using a greedy heuristic to expand a seed into a community. We perform synthetic benchmarks which indicate that an appropriate seeding strategy becomes increasingly important as the extent of community overlap increases. We find that distinct cliques provide the best seeds. We find further support for this seeding strategy with benchmarks on a Facebook network and the yeast interactome.

8 Pages

References in corpus (6)

• Uncovering the overlapping community structure of complex networks in nature and society
• Comparing community structure identification
• Detecting the overlapping and hierarchical community structure of complex networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Evaluating Local Community Methods in Networks
• Detection of node group membership in networks with group overlap

Cited by in corpus (3)

• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Effective Influence Spreading in Temporal Networks with Sequential Seeding
• Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning