| Complex networks have witnessed the traditional graph theory created by Euler,random graph theory pioneered by Erd?s and Rényi and network science based on real data by Newman and Barabási et al.During the development,the structural research represented by the centrality measure and the functional research represented by the link prediction and network dynamics on complex networks have been growing in the hands of many outstanding scientists.As one of the youngest and most dynamic branches in the field of complex networks,link prediction has sprung up in the 1960s and 1970s,and was formally proposed in Liben-Nowell and Kleinberg’s paper published in 2007 on the temporal evolution of social networks.In 2008,the paper by Newman et al.on network hierarchical model and missing link prediction made the concept of link prediction widely known.Since then,link prediction as a link version of network evolution mechanisms,has flourished in the empirical field—network science scholars have developed hundreds of link prediction methods based on node centrality,network generation model and machine learning.Based on the many contributions of predecessors in the field of link prediction,we summarize the link prediction system LP on static network data into 3 steps.The first step is scoring,that is,the network topology is divided into training set and test set;the second step is to use the algorithm to calculate the scores of all node pairs on the training set;the third step is to combine the known test set information to evaluate the performance of the algorithm.Among them,network data G and algorithm f are system input,partition strategy D and evaluation index M are system parameters,and specific performance evaluation index m is the final output of the system,that is,m=LP(G,f;M,D)is the performance of f on G.In the link prediction system LP(AUC,RDp),we get a more specific AUC analytical expression,which can be applicable to all link prediction algorithms.For more specific local-topology-based algorithms such as PA and Salton,we transform the score distribution into a local topological distribution,and then use mathematical tools such as random graph theory and generating functions to achieve topological distribution in training set from the original network.And then,the mathematical transformation from the original network topology to the output of the link prediction system is obtained.Corresponding empirical analysis not only confirms the effectiveness and robustness of the analytical framework,but also discovers the correlation between the global topology indicators and the performance of algorithms,such as the positive correlation between AUCCN and the clustering coefficient(CC).As for the predictability analysis,we found that for a single network,there is a contradiction between the generalization performance and the accurate performance of the algorithm;for a lot of networks,the commonality of these network topology often determines the upper limit of the algorithm’s performance.For example,the predictability of networks generated by the ER random graph model is only 0.5.In the link prediction system LP(AUC,LOOT),the mathematical expression of AUC is relatively simple and obtained only by the scoring and sorting of the algorithm in the original network,which shows that links in the core area of the network own larger predictability.At the same time,the robustness analysis of the structural controllability of the network structure shows that the critical link affecting the minimum number of driving nodes in the network is often located in the edge area of the network.Combining the above two,we naturally come to the conclusion that the predictability of the critical link is lower,which is called the structural reciprocity phenomenon.This phenomenon has been confirmed on datasets based on real networks and artificial networks.Further structural coordination analysis tells us that,not only the link properties and the ratio of critical links have a significant impact on structural reciprocity;but also the core-edge structure of the network is the root cause of structural reciprocity. |
PDF Full Text Request