Research On Key Technologies Of Link Prediction And Network Evolution Of Complex Network

Recently,in the context of ongoing intensive research on complex networks,more and more complex systems are becoming research objects of complex network.As the research hotspot of network science,the research on evolving model and link prediction can verify different evolution mechanisms respectively from the perspective of macro statistics and real network,and play an important role in evolution of complex system,network construction,scientific researches and daily life.There is close relationship between evolving model and link prediction.The research on the evolving model can provide new ideas for link prediction.On the other hand,the study of link prediction can verify the evolution mechanism and evolving model.In the past few years,though grater progress has been made in the research on evolving model and link prediction,there are still some problems: i)There are many evolving models to describe the power-law distribution.But statistical studies show that the distribution of many real networks are not purely power-law distribution,but near power-law distribution,double power-law distribution,shift power-law distribution or other types of distributions.Therefore,in order to verify these statistical phenomena,we need propose new targeted evolving models.ii)For variable real network datasets,it still has a great desire to propose some link prediction methods with lower time complexity and higher prediction accuracy.iii)Many researches on the evolving model and link prediction are almost irrelevant,and ignore the close relationship between them.Supported by the national 863 program,this paper is focused on the key technologies of link prediction and network evolution of complex network.Firstly,based on network motif and information transmission,two evolving models are proposed.Then,we analyze the influence of node-weight,path and edge-weight on link prediction,and propose three similarity indices based on weighted common neighbors,resource interaction and weighted local topology respectively.At last,to verify the close relationship between evolving model and link prediction,a new weighted method is proposed based on local topology information.In conclusion,the main research results of this dissertation are as follows.To discuss the influence of different scale of preferential attachment on network evolution,an evolving model based on the attraction of network motif vertex.In the perspective of network motif which is a bigger “scale” than nodes,the model proposes the attraction of network motif vertex to calculate the preferential attachment attracted by the organization around each node.Then,based on the local world evolving model,an evolving model based on the attraction of network motif vertex is proposed.Numerical simulation results denote that the proposed model can not only reproduce small-world and high network clustering,but also show the variations from power-law distribution to exponential distribution,and it can also show the double power law distribution under some circumstances.In addition,the model can construct network with assortative or disassortative mixing pattern with the ratio between different motifs changing.To study the influence of information transmission which is the important inner motivation of network to the complex network evolution,a new evolving model of network growth promoted by information transmission is proposed.The model includes three major steps:(i)new links attach to the nodes on the information transmission path whose source point is chosen preferentially;(ii)the first link of the new node attach to the nodes in the local-world;(iii)the other links of the new node attach to the nodes on the information transmission path whose source point is the new node.The process of information transmission is simulated by self-avoid random walk,and considering the local information including degree and distance,selective connection is established between the nodes on the information transmission path.Theoretical analysis and numerical simulation results denote that the proposed model can not only reproduce small-world and scale-free network characteristics,but also show “shift power-law distribution” and “truncated power law” function forms under different parameters which bring some non-power-law features such as exponential cutoff and saturation for small variables.Moreover,in our model,the clustering coefficient is tunable without changing the degree distribution and the model can construct network with assortative or disassortative mixing pattern.To study the influence of weighted common neighbors on the link prediction accuracy(precision),two similarity indices for link prediction are proposed respectively based on the clustering coefficient and connectivity of common neighbors.Firstly,by analyzing the effect of clustering on the connection between two nodes,a clustered common neighbor(CCN)is proposed with the common neighbors weighted by their clustering coefficient.With a parameter adjusting the strength,CCN can get optimal prediction accuracy for different networks.Then,the connectivity of common neighbors is proposed to calculate the close relationship between common neighbors and predicted endpoints.A parameter is also introduced to adjust the strength of connectivity,and the new index is called RCN,Empirical study on nine real networks has shown that the indices we proposed can achieve a good performance,compared with seven mainstream baselines.For most of datasets,the performance of RCN is better than CCN,but CCN can get higher prediction accuracy in some networks such as power grid.To improve the AUC and Precision of resource allocation index,an extended resource allocation index(ERA)is proposed based on the resource interaction between two endpoints.ERA index considers the potential resources transferred by some longer local paths.With an adjust proportion of resource assigned to each branch of common neighbors,the ERA index can measure the times and the amount of resources interacted between two endpoints.Empirical study on twelve real networks has shown that the index we proposed can achieve a good performance,compared with seven mainstream baselines.To find a method which can improve the precision accuracy of several similarity indices,a local weighted method is proposed and several local weighted similarity indices are proposed based on the local weighted method.By analyzing the closeness between two nodes with different topology structures,a link weight assignment method is proposed for weighting the strength of connection between each pair of nodes.With the local weighted method extended to six similarity indices,several local weighted similarity indices are proposed,including LwCN?LwSalton?LwJaccard?LwRA?LwAA and LwLP.Empirical study has shown that the local weighted method can significantly improve the prediction accuracy of these unweighted similarity indices and that in sparse and weakly clustered networks,these local weighted indices perform even better.To verify the unity of evolving model and link prediction,a new weighted method is proposed based on the mechanism that information coupling of local topology promote the network evolution.Firstly,the weighted method is applied to BA model;EwBA and the local world model EwLW are proposed based on the topology weighted method.Simulation experiments show that the degree distribution of EwBA can be rapidly changed from exponential distribution to power law distribution with the increasing of the connection numbers for new added nodes,which confirmes that the phenomenon of accelerating growth appears widely in the evolution of many real scale-free networks.Then,based on EwBA model,an accelerating growth model A-EwBA is proposed,and the A-EwBA model presents power law distribution for different accelerating growth rates.The degree distribution of EwLW is changed from stretched exponential distribution to power law distribution for different sizes of local world.Finally,the proposed weighted method is applied to link prediction methods(including CN,Salton and RA index),and three weighted indices are proposed.Empirical study shows that the weighted proposed method can significantly improve the prediction accuracy of these basic indices,and some of them are higher than those of the global indices.