Research On Vertex Rank And Structural Similarity Metric In Social Network

Social network, such as Facebook and Twitter, is gradually becoming the most popular platform where people enjoy entertainment, information sharing and socializing. Lots of valuable information is contained in social network, for example utilizing the network structure can evaluate the friendship between friends in daily life. Thus, analyzing and exploring network is inevitably to be a research hotspot including computer science, biology, physics, etc. As the important means in social network analysis, link-based mining makes full use of the vertex link-structure to explore the characteristic, shape and function of social network, and it has been widely used in various related research fields, including community detection, recommender systems, proximity query processing, bioinformatics and collaborative filtering technology. Due to vertex rank and structural similarity measure of vertex-pair are two basic tasks in link-based mining, they are attracting more and more attention in academic circles.With the popularity of social networks and the emergence of mining applications, to find useful and interesting information, researchers are trying to fetch the top-k dominant vertices in the network and get a set of vertices which are similar to a given one. However, most existing works independently investigate these two issues, and the connection between them is ignored arbitrarily.In fact, according to our experimental results, vertex rank and similarity calculation are associated and constrained mutually each other. Based on this observation, we proposed an innovative computing framework named S2R&R2S, which can rank vertices and compute vertex-pair structural similarity simultaneously. Two primary algorithms are included in it, they are S2R and R2S. S2R is motivated by "the ranks of two vertices are similar if they have highly structural similarity in the social network". It can effectively measure various vertex ranks, when assisted by the vertex-pair structural similarities. Unlike SimRank-based methods, structural characteristic information of vertex is considered in R2S. Thus, R2S didn’t encounter the so-called "zero similarity" and unreasonable phenomenon which happened in SimRank algorithms.In S2R&R2S, S2R and R2S are executed alternately and iteratively until convergence.Experiment results evaluated on real datasets have shown that the proposed scheme is outstanding in both vertex rank and similarity measure. Compared with others, the R2S scores of vertex-pairs are with more clear interpretation and usefulness. In conclusion, S2R&R2S is an efficient method to rank vertices and compute structural similarity between vertices.