An Edge-based Clustering Algorithm to Detect Social Circles in Ego Networks

Abstract

Organizing users’ friends in personal social networks, i.e., ego networks, into circles is an important task for online social networks. Social networking sites allow users to manually categorize their friends into social circles. However, it is time consuming and does not update automatically as a user adds more friends. In this paper, we propose an edge-based clustering algorithm to detect social circles in ego networks automatically. Firstly, we reconstruct ego networks by predicting the missing links. Then, we define the similarity of adjacent edges and cluster edges by single-linkage hierarchical clustering algorithm. Finally, we label each circle by abstracting its common properties to explain why this circle forms. The experimental results demonstrate it is a better way to characterize social circles from the respect of edges. Our algorithm outperforms the link community algorithm and low-rank embedding algorithm in terms of accuracy, and is more efficient than the probabilistic model algorithm. Our proposed method is validated as an effective algorithm in identifying social circles.