Using triangles and latent factor cosine similarity prior to improve community detection inmulti-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 otherthan to the members in other groups. Considering the importance of triangle structures, we firstpropose ğœ-tensor tomodel ordinary relationships and triangle relationships simultaneously.Then,we propose a simple but effective latent factor prior, ie, latent factor cosine similarity prior, toimprove community detection. The latent factor cosine similarity prior is a kind of statistics ofthe well-defined synthetic multi-relational social networks. It is based on a key observation thatmost latent feature factors of intra-group members in these networks are highly similar accordingto 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 ofRESCAL model, and its corresponding algorithm N-RESCAL-ALS are proposed for the simplicityand the removal of the limit of cosine similarity. Once the latent factor matrix is obtainedby factorizing ğœ-tensor using N-RESCAL model, we apply agglomerative clustering algorithm forcommunity discovery.We call this framework as TNRA. Experiment results on several real-worlddatasets are surprisingly promising, clearly demonstrating the power of the proposed prior andthe effectiveness of our proposed methods.