A review on the detection of social circles in Facebook egonets
Published in Network science course, 2018
This paper reviews the use of community detection algorithms in social networks to automatically identify users social circles (ex. family, college friends) in social networks. With hierarchically nested and overlapping ground truth circles (hand labeled), we pose the problem as a multi-membership node clustering problem on a users ego-network, a network of connections between her friends. We first establish a model baseline for this problem, consisting of basic algorithms used in community detection: connected components, Girvan-Newman, greedy modularity optimization and k-clique. Then, we outline the current state of the art algorithm and implement it from scratch in Python (no publicly available code exists). Furthermore, as the evaluation of predicted communities is far from trivial for this problem, we give an exhaustive and comparative summary of methods used to this day. Finally, we evaluate and discuss the performance of all these algorithms on the standard dataset for this task, Facebook egonets. We show that the k-clique is the best algorithm among the baseline and that although theoritically powerful, the state of the art model is not robust to missing data. Finally, we suggest improvement directions for this task. Beside the review, our contribution to this problem is an open-source python package, containing the model baseline, the state of the art model, along with a complete evaluation module.
Recommended citation: Louis de Vitry, Cynthia El-Hayek, Maximilien Barbe (2018)"A review on the detection of social circles in Facebook egonets 2." Network science course. 1(2). http://devitrylouis.github.io/files/paper_egonet.pdf