Weighted-Ring Similarity Measurement for Community Detection in Social Networks

Abstract

Community discovery using topological structure of social network graph is a key issue in community mining algorithms. In the social network, the rings are formed between vertices and vertices. The closer relationship between two vertices, the more rings are formed. Since the vertices contribute differently to the ring, the same type of rings contributes differently to the similarity between the vertices. Therefore, how to assign a reasonable weighting coefficient to each ring so that it can correctly represent the similarity between the vertices is the key issue. In this paper, according to using the theory of set pair analysis, the social network is regarded as a combination of a certain and an uncertain system, considering the topology's contribution to the similarity between vertices, a new algorithm for measuring the similarity between vertices based on weighted rings is proposed, and then the algorithm is applied to community discovery. The experimental results show that the proposed methods provide us with a useful way for measuring the similarity between the vertices.