EgoLP: Fast and Distributed Community Detection in Billion-node Social Networks.

Authors

Buzun N., Korshunov A., Avanesov V., Filonenko I., Kozlov I., Turdakov D., Kim H.

Abstract

Community structure is one of the most important and characteristic features of social networks. Numerous methods for discovering implicit user communities from a social graph of users have been proposed in recent years. However, most of them have performance and scalability issues which make them hardly applicable to population-wide analysis of modern social networks (billions of users and growing). In this paper we present EgoLP – an efficient and fully distributed method for social community detection. The method is based on propagating community labels through the network with the help of friendship groups of individual users. Experimental evaluation of Apache Spark implementation of the method showed that it outperforms some state-of-the-art methods in terms of a) similarity of extracted communities to the reference ones from synthetic networks; b) precision of user attributes prediction in Facebook based solely on community memberships; c) likelihood of the discovered community structure according to the proposed generative model. At the same time, the method retains near-linear complexity in the number of edges and is thus applicable to social graphs of up to 10⁹ users.

Full text of the paper in pdf

Keywords

Community detection, social networks, graph clustering, distributed algorithms

Edition

Proceeding of DaMNet-2014: The Fourth IEEE ICDM Workshop on Data Mining in Networks. December 14, 2014, Shenzhen, China.

Research Group

Information Systems

All publications during 2014

All publications