φ~1-Graph Based Community Detection in Online Social Networks

摘要

Detecting community structures in online social network is a challenging job for traditional algorithms, such as spectral clustering algorithms, due to the unprecedented large scale of the network. In this paper, we present an efficient algorithm for community detection in online social network, which chooses relatively small sample matrix to alleviate the computational cost. We use φ~1-graph to construct the similarity graph and integrate the graph laplacian with random walk in directed social network. The experimental results show the effectiveness of the proposed method.