Using triangles and latent factor cosine similarity prior to improve community detection in multi-relational social networks

Community detection is a key to understanding the structure of complex networks. Communities, or clusters, are groups of vertices having higher probability of being connected to each other than to the members in other groups. Considering the importance of triangle structures, we first propose sigma-tensor to model ordinary relationships and triangle relationships simultaneously. Then, we propose a simple but effective latent factor prior, ie, latent factor cosine similarity prior, to improve community detection. The latent factor cosine similarity prior is a kind of statistics of the well-defined synthetic multi-relational social networks. It is based on a key observation that most latent feature factors of intra-group members in these networks are highly similar according to cosine similarity measure. Using this prior along with the RESCAL tensor factorization model, we can obtain a superior latent feature factor matrix. Moreover, N-RESCAL model, a variant of RESCAL model, and its corresponding algorithm N-RESCAL-ALS are proposed for the simplicity and the removal of the limit of cosine similarity. Once the latent factor matrix is obtained by factorizing sigma-tensor using N-RESCAL model, we apply agglomerative clustering algorithm for community discovery. We call this framework as TNRA. Experiment results on several real-world datasets are surprisingly promising, clearly demonstrating the power of the proposed prior and the effectiveness of our proposed methods.