Research On Link Prediction And Role Similarity Measure In Complex Network

With the rapid development and widespread applications of information technol-ogy, a variety of complex networks have been proliferating. The research and analysis of complex networks have become an important interdisciplinary field. The structural similarity measure of nodes is the most fundamental and a very important task in com-plex network analysis. This dissertation focuses on two problems which are both closely related to the structural similarity measure.The first problem is similarity-based link prediction. The purpose of link predic-tion is to find the missing links or predict the emergence of new links according to the structural-context. Similarity-based link prediction is the mainstream and its key is how to compute similarities accurately. In this dissertation, we make a comparatively deep analysis of the similarity-based link prediction and propose two novel structural simi-larity measure to solve the existing issues.(1) SAC. This measure computes the similarity between two nodes via the activ-ities of them in their common neighborhood and the connectivities between them and their common neighbors. The higher the activities are and the stronger the connectivities are, the more similar these two nodes are. SAC commendably distinguishes the contri-butions of paths and incorporates the influence of endpoints themselves. Therefore, it can achieve a better predicting result.(2) Scope. This measure defines the contributions of paths to their endpoints and the contributions of endpoints themselves. Scope computes the similarity between two endpoints by combing these two kinds of contributions. Scope can easily distinguish the contributions of paths and obtains better predicting results.In order to verify the performance of these two measures, we conduct experiments on ten real-world networks. Experimental results show that the accuracies of SAC and Scope are significantly better than the six baselines.The second one is role similarity measure. Role similarity between two nodes does not depend on their common neighbors or paths connecting them, but is only relevant to their roles in a network. RoleSim which is a real-valued role similarity metric can better search peer nodes. However, the accuracy of RoleSim is not high enough and the time performance of RoleSim is very low. To solve these two issues, the dissertation presents two novel role similarity metrics.(1) CentSim. The role of a node is related to its position and centrality is a general measure of how the position of a node is within a network. CentSim employs cen-tralities of nodes to calculate their role similarities. CentSim achieves a very high time performance and accurate results. Furthermore, CentSim is an admissible role similarity metric.(2) Simon. When computing the similarity between two nodes, Simon only com-pares the PageRank scores of their direct neighbors as well as the PageRank scores of the two nodes themselves. The time complexity of Simon is low and the similarity of any node-pair assigned by Simon is very accurate. Simon is also an admissible role similarity metric.To evaluate the performance of these two metrics, we perform experiments on five real-world benchmark networks. Compared with the five other methods, both CentSim and Simon can quickly and more accurately calculate the role similarities. So they are both good role similarity measures.