A fast multi-level algorithm for community detection in directed online social networks

The discovery of underlying community structures plays a significant role in online social network (OSN) analysis. Many previous methods suffer from inaccuracy or incompleteness in community descriptions because of the multiple factors affecting OSNs and the high computational complexity caused by the large scale of these networks. We present a new community detection approach that focuses on two aspects. First, it relies on a combination of user interests and cohesiveness in describing community structures. Second, it introduces a multi-level community discovery algorithm for large-scale OSN datasets. The algorithm consists of three steps: (1) network coarsening based on the combination of two categories of properties, (2) stochastic inference to find an initial community assignment over the coarsest network and (3) projection and refinement of this assignment to obtain the final community detection result by solving a semi-supervised learning problem. The combination of user interests and cohesiveness leads to a complete and well-interpreted description of the communities embedded in OSNs, and the multi-level algorithm speeds up the computation process and improves the likelihood of finding the global optimal solution by reducing the parameter space. Experiments conducted on both synthetic and real datasets demonstrate the effectiveness and efficiency of our method.