A Link Prediction Algorithm Based On Socialized Semi-local Information

Social network is made up of the entities and relationships between entities in real society together. Link prediction is mainly used to analyze the interaction and relationship between entities which is the key research content of the social network. The hidden or links to appear at a certain moment in the future would be inferred on the basis of the characteristics of entities and the existing relationship between the entities. The study and research for link prediction has important theoretical and realistic significance.Because the traditional link prediction algorithms based on local structure information of the network only consider the common neighbor node number and degree between nodes. It is not very good prediction in a situation where two networks have the same common neighbor nodes' number and degree. In this paper, the new local path algorithm RA-CNI is put forward on the basis of considering public neighbor interactions between the nodes and the traditional resource allocation algorithm RA. The local algorithms have low time complexity and poor prediction effect because of using less network structure information, but global algorithms have high time complexity and satisfactory prediction effect for using most information of network structure,so a kind of improved semi-local algorithm LRA-CNI is put forward by extending the new local path algorithm RA-CNI to the third order to achieve good prediction effect and low computational complexity.Finally, the accuracy and running time of the presented algorithms RA-CNI and LRA-CNI are compared with classic local algorithms CN?RA?semi-local algorithm LP and global algorithm Katz through the simulation experiment. Experimental results show that the proposed improved algorithms improve the accuracy of link prediction and increased a little computational complexity but the running time is still within the same order of magnitude with the classical algorithm.