A Sparsification Technique for Faster Hierarchical Community Detection in Social Networks

The proliferation of social networking sites and their rapidly growing user-base have made information sharing simpler than ever before. However, a typical social network user might get easily overloaded with information that may not be of interest to the user. Further the number of users and the links which they exhibit among their peers are very huge in a typical social network. Hence, identifying people of similar interests and forming communities is complex due to the diversity and scale of a social network. In this paper, we propose an algorithm to detect communities using an ontology based interest hierarchy. The approach that we propose uses a hierarchical top-down community formation using a sparsified form of the original social network graph. The novel sparsification heuristic helps in reducing the computational cost of our algorithm, at the same time improving the quality of the communities formed. However, for want of more savings in computational time, we have proposed a parallel implementation strategy for the community detection algorithm. Empirical evaluation of the proposed algorithm reveals that the communities formed by the algorithm are sound and modular. The parallel algorithm in conjunction with the sparsification technique exhibits a speed-up factor of 20.4 on a cluster of 8 quad core processors.