Research On Temporal Link Prediction For Dynamic Complex Networks

As an important interdisciplinary research field,complex networks have attracted extensive attention of researchers in physics,biology,engineering,mathematics,computer and other disciplines.Link prediction is an important research direction in the field of complex networks.Link prediction is based on the known information such as network node attributes and network structure to predict the possibility of connection between nodes that are not connected in the network.In theory,link prediction can help researchers understand the evolution mechanism of complex networks.In application,it can also solve many practical problems such as recommendation system,social network analysis,biological network experimental analysis and so on.Therefore,link prediction has important theoretical research value and wide application value.In recent years,with the wide application of electronic devices,network data carries the time attribute.People’s research on complex networks is also shifting to dynamic complex networks with time dimension.The research on link prediction has made a lot of achievements in static networks.However,in dynamic complex networks,it is necessary to re-examine and improve the link prediction methods due to the time attribute.At present,link prediction faces several challenges.Firstly,the concepts and indicators in static networks(such as neighbor nodes,distance,node centrality,etc.)do not take the time factor into consideration,so they can not be directly applied to dynamic complex networks and need to be expanded.Secondly,in dynamic complex networks,the connected edges between nodes are not transitive.If the connection relationship is directly accumulated,the time-dependent information such as time irreversibility,the connection time and frequency are ignored.Therefore,for dynamic complex networks,this paper proposes related methods to solve the problem of temporal link prediction,and studies the application of time layer similarity in node centrality.The main contents of this paper are as follows:1.A temporal link prediction method based on graph regularized non-negative matrix factorization(GC-RNMF)is proposed.The communicability is used to preserve the global information in the dynamic complex network and reflects the time evolution pattern.The graph regularization is used to preserve the local information of each snapshot.Then,we integrate the global and local information of dynamic complex network into the non-negative matrix factorization model,and establish the corresponding optimization model.Furthermore,a Lagrange multiplication updating rule is used to solve this optimization model.Finally,the proposed method is compared with the methods based on similarity and matrix factorization.The experimental results show that the proposed method has obvious improvement in prediction accuracy and robustness.2.The community structure of network can be used to distinguish the proximity of connections between nodes.Considering the community structure information of dynamic complex network,we propose a semi-supervised non-negative matrix factorization for temporal link prediction method,called Seg NMF for short.We define global temporal neighbors by extending the concept of neighbors in multilayer networks.The topological characteristics of dynamic complex network are obtained from the community structure and neighbor information,and the global information is obtained from the communicability of the network.We set the historical networks as the regularization term,and the community information as the constraint condition of the node pairs.Then,we establish a non-negative matrix factorization model to retain the dynamic topology information of the network.An effective Lagrange multiplier method is proposed to solve the model,and the convergence of the Seg NMF is proved.The experimental results show that the Seg NMF can obtain higher accuracy than other algorithms based on similarity and matrix factorization.This is because the Seg NMF can obtain the hidden features from the network time-evolving information and community structure.3.A temporal link prediction method based on non-negative tensor decomposition(NCP4)is proposed.We express the dynamic complex network as a fourth-order tensor.The temporal correlation coefficient is used to measure the relationship between different snapshots.This model can describe the evolution characteristics of complex network effectively.The features of each node are obtained by non-negative tensor CP decomposition,and are applied to temporal link prediction.We explain the rationality of NCP4 by the authority and hub of HITS(Hyperlink–Induced topic search).In addition,the convergence of the NCP4 is proved.The numerical results show that the NCP4 has good prediction ability.4.We propose Co-Rank centrality based on Page Rank to measure the centrality in dynamic complex networks and employ such centrality to solve temporal link prediction.We use the sixth order tensor to model the multi-layer dynamic network,in which the influence of different snapshots and the interaction between layers are described.The traditional Page Rank centrality is extended to multi-layer dynamic networks,and the parameterless tensor equations are established to define the centrality vectors of nodes,layers and snapshots.Besides,we give the existence and uniqueness theorems of CoRank centrality.An iterative algorithm for solving tensor equations is proposed.At the same time,we propose a new node similarity index named Tsalton,which is a temporal link prediction method based on node centrality.According to the Co-Rank centrality of nodes,we distinguish the influence of common neighbors on link generation and obtain the evolution characteristics of node centrality for link prediction.Finally,the results of numerical experiments show that Co-Rank centrality has a good ability to identify important nodes,and can describe the multi-layer and time-evolving of dynamic complex networks reasonably.We also perform temporal link prediction tasks on real dynamic complex networks.The prediction ability of the proposed similarity is higher than that of some existing prediction algorithms.The experimental results show the effectiveness of the proposed similarity.