Overlapping Community Detection via Minimum Spanning Tree Computations

摘要

Contemporary social networks deal with Big Data in which a large amount of useful information is hidden. Detecting communities in such networks constitutes a particularly challenging computational task. In this paper, we propose an algorithm for detecting overlapping communities, which builds on an hierarchical divisive method called ST (AlgoCloud2018), originally designed to detect disjoint communities efficiently and without significant loss of information. The method is based on first computing a minimum spanning tree of the original graph and then calculating the edge and vertex betweenness centrality measures on the tree, considerably speeding up calculations.