Accelerating Link Community Detection in Social Networks

Online social networks such as Facebook have become the most popular sites on the Internet. These networks usually contain millions or even billions of registered users and the users can interact with each other, which results in highly connected communities of friends, families or occupations. The communities in social networks are usually overlapped or even nested, but most of overlapping detection methods have trouble scaling to large networks. In this paper, we propose a fast link clustering (FLC) algorithm to discover link communities. By studying power-law degree distribution of online social networks, we propose working with a reduced graph that has fewer nodes and links but nonetheless captures key community structure. Experiments demonstrate efficiency and accuracy on different real networks ranging from small-scale traditional benchmarks to large-scale ground-truth social networks. FLC can accurately discover network communities as well as the overlaps between communities, and meanwhile it can scale to online social networks with millions of nodes.