Hierarchical and overlapping social circle identification in ego networks based on link clustering

As online social networks receive rising popularity, social circle identification has gradually attracted attention from researchers. However, the existing approaches are incapable of utilizing both structural and attributional information in an efficient way, which creates a space of improvement to performance. In this paper, HOSCIEN, as a novel solution to identifying hierarchical and overlapping social circles in ego networks, is developed. Rather than directly partitioning nodes into different groups, social circles are identified based on the link clustering. An efficient scheme is proposed to evaluate the similarity of links according to both structural and attributional information. Then a hierarchical clustering method is applied to construct a dendrogram of links. Two methods are suggested to perform calculations of proper cuts for the dendrogram, which leads to circles with varying granularity. Besides, a supervised classifier is trained to identify the category of a circle based on the structural and attributional features. The performance of HOSCIEN is assessed based on three benchmark datasets. As revealed by the results, HOSCIEN performs better than the state-of-the-art methods for all of the four evaluation metrics. Our method is also applied to real social networks by implementing a WeChat applet for classification of a user's friends into proper circles.