Hierarchical community detection via rank-2 symmetric nonnegative matrix factorization

Area of Science:

• Network Science
• Computer Science
• Data Mining

Background:

• Community discovery is crucial for understanding large network structures.
• Scalability and evaluation of community detection in massive social networks remain challenging.

Purpose of the Study:

• To develop a scalable and efficient algorithm for hierarchical community discovery in large networks.
• To address the limitations of traditional graph clustering algorithms for massive datasets.

Main Methods:

• A divide-and-conquer strategy is employed for hierarchical community structure discovery.
• The algorithm utilizes rank-2 symmetric nonnegative matrix factorization for efficiency.
• Implementation challenges are addressed to optimize performance on modern architectures for sparse matrices.

Main Results:

• The proposed algorithm demonstrates competitive overall efficiency.
• It achieves leading performance in minimizing the average normalized cut.
• Nonoverlapping communities identified by the algorithm better recover ground-truth communities compared to state-of-the-art methods.

Conclusions:

• The algorithm offers a superior approach to community detection in large, sparse networks.
• A new DBLP dataset with richer metadata and ground truth is introduced to advance research.
• The findings facilitate better interpretation of communities within complex network structures.