Community classification in decentralized social networks using local topological 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 Online Social Network (OSN) 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.