Papers › Efficient Detection of Communities with Significant Overlaps in Networks: Partial...
Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
Elvis H. W. Xu, P. M. Hui
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Detecting communities in large-scale networks is a challenging task when each vertex may belong to multiple communities, as is often the case in social networks. The multiple memberships of vertices and thus the strong overlaps among communities render many detection algorithms invalid. We develop a Partial Community Merger Algorithm (PCMA) for detecting communities with significant overlaps as well as slightly overlapping and disjoint ones. It is a bottom-up approach based on properly reassembling partial information of communities revealed in ego networks of vertices to reconstruct complete communities. Noise control and merger order are the two key issues in implementing this idea. We propose a novel similarity measure between two merged communities that can suppress noise and an efficient algorithm that recursively merges the most similar pair of communities. The validity and accuracy of PCMA is tested against two benchmarks and compared to four existing algorithms. It is the most efficient one with linear complexity and it outperforms the compared algorithms when vertices have multiple memberships. PCMA is applied to two huge online social networks, Friendster and Sina Weibo. Millions of communities are detected and they are of higher qualities than the corresponding metadata groups. We find that the latter should not be regarded as the ground-truth of structural communities. The significant overlapping pattern found in the detected communities confirms the need of new algorithms, such as PCMA, to handle multiple memberships of vertices in social networks.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections