Research On Link Prediction Algorithms For Weak Clique Structure

In the real world,there are a large number of complex systems,such as biological,electrical and social relations systems.These complex systems can be ed into complex networks,in which the individuals in the system are represented by nodes in the network,and the relationships among individuals are represented by linked edges.Researching complex networks is of great importance for exploring the formation and evolution mechanism of networks,while link prediction links complex networks with information science closely.Complex networks will change dynamically with the development of time.It is of great significance to study and explore the evolution mechanism of complex networks.Link prediction is an important branch of the complex network domain.It predicts the possibility of interconnection between two nodes in a network through known network structures and network node attribute information.Link prediction is an important direction of data mining,which can be used to study the evolution of dynamic networks and information completion of incomplete networks,and so on.With the rapid development of link prediction technology,many similarity algorithms have been proposed.Traditional link prediction algorithms mainly include link prediction algorithms based on local information,global information and random walk.This dissertation mainly studies the link prediction algorithm based on local information.In the local information of the network,the node attributes in the network are often difficult to obtain,even when they are acquired,they are often accompanied by noise data.Therefore,link prediction methods based on network local structure have received increasing attention in recent years.Weak clique structure is a special network topology prevalent in real networks.In this dissertation,the link prediction algorithm of this particular local structure is studied in depth.In this dissertation,two methods for computing node similarity are defined,and two new link prediction algorithms for weak clique structure are proposed.The main works and contributions are composed of the following two aspects:1.There are a large number of weak clique structures in real networks,and building algorithms for different network structures is the core problem of link prediction.The FR algorithm proposed by the social network friend recommendation strategy cannot distinguish the affinity relationship between the candidate node and the intermediary node.Considering that intermediary tends to introduce the person who is more familiar to the target user,a node similarity measurement index is proposed,and a link prediction algorithm of weighted friend recommendation model called WFR(Weighted Friend Recommendation)is proposed.This index combines local feature description and effectively distinguishes the influence between user nodes,which is more suitable for a specific weak clique structure.The performance of the proposed algorithm is comprehensively analyzed from three aspects:the influence of similarity index selection on the algorithm,the influence of weight ratio change on the algorithm and the application analysis of the algorithm in the typical artificial network environment.The experimental results of the weighted friend recommendation model link prediction algorithm based on this index on 12 data sets show that the algorithm has obvious advantages in two evaluation indexes of AUC and Prediction.2.At present,most link prediction algorithms do not introduce enough network information,resulting in poor prediction performance of link prediction.Since the local node embedding method can extract more network inform ation,the link prediction using the node similarity index constructed by the local node embedding method can often obtain better performance.Therefore,this dissertation combines friend recommendation FR algorithm and local node embedded Deep Walk algorithm to construct similarity index,proposes a new node similarity index,and proposes a new link prediction algorithm,called DFR(DeepWalk plus Friend Recommendation)algorithm.This index combines local feature description and can obtain the topological structure information of the target node more accurately.It is more suitable for a specific weak clique structure and large-scale networks.The experimental results of the link prediction algorithm on 12 data sets show that the algorithm has advantages in two evaluation indexes of AUC and Precision,especially in fewer training sets.