Seeding for pervasively overlapping communities

Area of Science:

• Network science
• Computational social science
• Bioinformatics

Background:

• Many real-world networks exhibit significant community overlap, where nodes belong to multiple groups.
• Existing overlapping community detection algorithms often fail in highly overlapping network scenarios.
• Algorithms optimizing local fitness measures using greedy expansion are a common approach.

Purpose of the Study:

• To investigate the performance of local fitness-based community detection algorithms in highly overlapping networks.
• To identify optimal seeding strategies for improving the accuracy of these algorithms.
• To validate findings using both synthetic and real-world network data.

Main Methods:

• Development and application of synthetic network benchmarks with varying degrees of community overlap.
• Implementation of a greedy heuristic algorithm that expands seed nodes into communities based on a local fitness measure.
• Testing distinct node types (e.g., cliques) as potential seeds.
• Benchmarking algorithm performance on a Facebook social network and the yeast protein-protein interaction network.

Main Results:

• Algorithm performance is highly sensitive to the initial seeding strategy, especially in highly overlapping networks.
• Distinct cliques consistently outperform other seeding strategies in promoting accurate community detection.
• The effectiveness of clique-based seeding is validated across both synthetic and empirical network datasets.

Conclusions:

• The choice of seeding strategy is critical for the success of local fitness-based overlapping community detection algorithms.
• Employing distinct cliques as seeds offers a robust and effective solution for detecting communities in complex, highly overlapping networks.
• These findings have implications for analyzing social, biological, and other complex systems with overlapping community structures.