Community classification on Decentralized Social Networks based on 2-hop neighbourhood information

摘要

Decentralized Social Network (DSN) has attracted a lot of research and development interest in recent years. It is believed to be the solution to many problems of centralized services. Due to the data limitation imposed by common decentralized architectures, centralized algorithms that support social networking functions need to be re-designed. In this work, we tackle the problem of community detection for a given user under the constraint of limited local topology information. This naturally yields a classification formulation for community detection. As an initial study, we focus on a specific type of classifiers - classification by thresholding against a proximity measure between nodes. We investigated four proximity measures: Common Neighbours (CN), Adamic/Adar score (AA), Page Rank (PR), Personalized PageRank (PPR). Using data collected from a large-scale Social Networking Service (SNS) in practice, we show that PPR can outperform the others with a few pre-known labels (37.5% to 64.97% relative improvement in terms of Area Under the ROC Curve). We further carry out extensive numerical evaluation of PPR, showing that more pre-known labels can linearly increase the capability of the single-feature classifier based on PPR. Users can thus seek for a trade-off between labeling cost and classification accuracy.