Research Of Link Prediction Algorithm Based On Network Structure In Complex Networks

In real world,many complex systems such as traffic,biological and information system,can be described by network.The individual in the system can be represented by node and the interaction or connection between individuals is represented by edge(link).Complex networks will evolve over time,and its information also change over time.It is very necessary to dig and research edge in network that acts as the carrier of the interactive information among the individuals.Link prediction is an important method of mining edge in network,and it can find some hidden and missing information and it is a kind of method to complete the network.With the in-depth research,many types of algorithms of link prediction have been proposed.Among them,methods based on node similarity is getting more and more attention.In general,the various information in the topology network is mixed together to define the similarity between the nodes,including nodes attributes and network structure.The external information,such as nodes attributes,can obtain a good prediction effect,but in many cases it is extremely difficult to obtain such information.Even though you can obtain nodes attributes information,it is also difficult to distinguish which information is useful to the prediction.In contrast,network structure information is simple and easy to screen.Moreover,the link prediction method based on network structure is universally applicable to the network with similar structure.However,research of link prediction algorithm based on network structure doesn't go far enough at this stage and it's not sufficient to mine which network structure has an impact on link.Based on this,we use network structure to define two methods that can compute similarity between nodes,and propose two new link prediction algorithms in this thesis.The main works and contributions of this thesis as listed as follow:1.In real network,because local network topology and properties of nodes are different,and the influence of each node is different,so the corresponding contribution to the link is also different.The link density between common neighbor nodes reflects the tightness of the local sub-network in which nodes are located.It may have an impact on link of nodes in the sub-network.Therefore,this thesis defines node contribution of and link density of common neighbor nodes,and proposes a new link prediction algorithm(LDNC for short)by combining two.Experiments are carried out on 9 real datasets.AUC and Precision are used in comparison with several algorithms,and the results show that the LDNC is very effective.2.Because the location of each node and path in network is different in network,they have different effects on the other parts of the network.In the link prediction problem,it's that different nodes and paths have different effects on link in network.This influence is represented by the weight of node and path.Based on this,this thesis gives a new method to calculate the weight of node and path,and proposes a new link prediction algorithm(CPNW for short)by combining two.Experiments are carried out on 9 real datasets.AUC and Precision are used in comparison with six Classical algorithms.The result show that the accuracy of the CPNW is high,which proves that the algorithm is effective.