Scalable and robust community detection via Proximity-based Cut and Merge

Online Social Networks (OSNs) heavily rely on community detection algorithms to support many of their core services. Common functions such as friend recommendation, and timeline personalization all require the fast discovery of communities over some massive graph(s). For such applications, scalability, flexibility and speed are much more important than marginal improvement in the theoretical quality of the results. While the community detection problem has been studied intensively in the past, existing work tends to emphasize on theoretical optimality than the aforementioned practical needs. In this paper, we present a 2-stage framework called Proximity-Based Cut and Merge (PBCM), for scalable and robust community detection. In the first stage, edges between low proximity nodes are eliminated in one pass. In the second stage, high proximity nodes are merged iteratively to produce results conforming to the intuitive notion of community. We explore the design space via extensive numerical evaluation to instantiate an effective community detection algorithm under the framework, and compare the performance of PBCM-based designs against state-of-the-art baselines. Our results show that the proposed PBCM framework is effective, scalable and robust. We also demonstrate the flexibility of PBCM by extending it to handle both overlapping and non-overlapping communities.