A Hierarchical Diffusion Algorithm for Community Detection in Social Networks

Abstract

Community discovery is one of the most important steps to understand the social networks. We propose a hierarchical diffusion method to detect the community structure. Our algorithm is based on the idea that people in different communities usually share less common friends. We also make use of the fact that people usually make decisions based others’choices, especially their friends’. Our algorithm can distinguish between pseudo-communities and meaningful ones. Tests on both classical and synthetic benchmarks show that our algorithm is comparable to state-of-the-art community detection algorithms in both computational complexity and accuracy measured by the so-called normalized mutual information.