Temporal Link Prediction Using Node Centrality and Time Series

Link prediction is an important task in the area of complex networks. Some networks can be better modeled by temporal networks where the patterns of link appearance and disappearance varying with time. However, most of the previous link prediction researches ignore the temporal behaviors of links. The temporal link prediction needs to predict future links via a known network, considering the temporal relationship of node pairs. We propose a method combining the node centrality with time series. We distinguish the contributions of common neighbors to link generation by their centralities. Compared with benchmark approaches in several temporal networks, the proposed method can improve the accuracy of temporal link prediction efficiently.

timestamps. The final link prediction scores are computed according to such model. In [16], the time series for each node pairs is calculated by the frequency of link occurrence between adjacent snapshot. Then, the likelihood of links are estimated based on the time series model. In [17], a collection of time-series to model are adopted to produce similarity scores over time.
Several methods try to utilize the time-evolving patterns of temporal networks. O'Madadhain et al. [18] regarded the historic events and node attributes as the input of a logistic regression classifier and decided the future links according to the output. In [19], the local probabilistic model is extended to include time awareness.
We present a node centrality-based temporal link prediction approach by the extendence of Salton. The main contributions of this paper are as follows: 1) We assess the influence of common neighbors in temporal network by the eigenvector centrality of nodes. In order to describe the influence of the previous timestamps on the later ones, we use time series model to capture the evolution of node centrality over time. Then, the future node centralities are produced. 2) We regard the centrality of common neighbors as their contribution to the connection likelihood. We extend the definition of global neighbors from multilayer networks to temporal networks. 3) We execute experiments on several real temporal networks. The results show that the performance of the proposed approach outperforms other benchmark methods.

A. Similarity-Based Methods
A lot of similarity-based link prediction methods are depicted in the literature. We present several approaches briefly. For a node x , let () x  be the neighborhood set of x and x k be the degree of x .
Common Neighbors (CN) [4] is one of the basic methods for link prediction. The similarity of node x and y is measured by the number of their common neighbors. The definition is written as: For Adamic-Adar (AA) [5], the node pairs that share fewer common nodes are weighted more heavily. The AA score is defined as: Temporal Link Prediction Using Node Centrality and Time Series For node pairs without direct connection, Jaccard Index [6] produces higher score value when they have more common neighbors in proportion to their total number of neighbors. It is defined as: Preferential Attachment (PA) [7] gives the score according to the degrees of node neighbors, and it is defined as: x PA y S k k  = (4) Analogous to AA, Resource-Allocation (RA) [8] assigns more weights to the nodes with lower-degree neighbors. The RA score is defined as follows: Salton index [9] is based on cosine similarity, and it is defined as follows:

B. Eigenvector Centrality
In complex network, eigenvector centrality can measure the influential nodes. The eigenvector centrality is related to the number of node neighbors and the influence of each neighbor. The eigenvector centrality of node x can be calculated as follows: where  is a constant and () x  is the neighbor set of node x .
For the adjacent matrix A , the eigenvector c associated with the largest eigenvalue of A is obtained as follows: The centrality of node x is represented by the x th element of eigenvector c .

C. Time Series
The Auto-Regressive Integrated Moving Average (ARIMA) includes autoregressive and moving average models. It is a combination model for time series data. The ARIMA model is defined as follows: 1 1 Here, t X represents the estimated variable at t th snapshot,

III. THE TSALTON APPROACH
Many activities are closely related to more influential nodes. Node centrality is regarded as the weight that represents the contribution of nodes to link generation. Therefore, the key issue is how to distinguish the nodes in important positions in the future when predicting links. Our proposed approach is referred to as the extension of Salton index [9] for temporal link prediction (TSalton).

A. The Proposed Model
In the TSalton method, we utilize the eigenvector centrality of each node to distinguish their roles to the likelihood of links. We use the ARIMA model to capture the changes of node centrality with time as follows: where t C represents the estimated node centrality at t th snapshot. We calculates the eigenvector centrality at each timestamp. Then, we forecast the future node centrality by ARIMA. Inspired by the node-centrality-based method in [12], we proposed the TSalton which is eigenvector-centrality-based Salton. The proposed model is read: We extend the neighbors to temporal neighbors according to the definition of neighbors in multilayer network [20]. The global neighbors of node represents the unique neighbors over time: where xy e is the connections between node x and y , t E is the link set at the t th snapshot.

B. The Proposed Algorithm
The TSalton algorithm consists of three main components: node centrality calculation, centrality-based score construction and temporal link prediction. Framework of TSalton algorithm is presented as follows:

A. Evaluation Metrics
We adopt two standard metrics, AUC [21] and precision [22] to estimate the accuracy of temporal link prediction algorithms.
The AUC score is defined as The precision is defined as The precision value is the ratio of relevant links to the number of selected links. If we predict L links to be connected and among them Lr links are correct. The temporal networks applied in this paper includes Workplace [23], EnronEmail [24], Manufacture [25] and CollegeMessage [24]. Table I reports the important statistics of the real-world network.

C. Evaluation of Link Prediction
In these experiments, we compare the temporal link prediction approaches on real-world networks. The comparative approaches are similarity-based methods in Section II. Experiments have been performed adopting the networks in Table I The AUC results of these methods are given in Table II and the related ROC (Receiver operator characteristic) curves are depicted in Fig. 1. We can see that the TSalton outperforms all the other approaches. The similarity-based methods ignore the temporal information of network and only use local topological information, so they perform poorly on temporal link prediction.
Meanwhile, TSalton takes the temporal information into account, and the time series model can reflect the influential nodes more accurately. Let's take the example of EnronEmail. TSalton achieves the highest AUC 0.9134 and is about 20% higher than CN which is in second place.
We list the precision results in Table III. TSalton yields higher precision than similarity-based methods. As for EnronEmail, TSalton is about 0.4% higher than PA in second place. This result shows the advantages of time influence in link prediction. In general, we can see that TSalton performs the best among the baseline approaches in term of AUC and precision on real networks. This results verify that TSalton is suitable for temporal link prediction. The possible reasons are from two aspects :(1) TSalton employs the time series model of eigenvector centrality which can represent the influential nodes more accurately in temporal networks. (2) TSalton considers the contributions of each neighbor to link generation via Salton scores to adjust such contribution.

V. CONCLUSION
The paper proposes a novel algorithm named TSalton. It International Journal of Future Computer and Communication, Vol. 9, No. 3, September 2020 can obtain the topology information, which considers the influential nodes over time. The TSalton scores the likelihood of links by taking the eigenvector centralities of common neighbors into account. We have considered link prediction methods in terms of AUC and precision. Experiments in real networks show that, TSalton performs better than the methods without using temporal information. As a future direction, we aim to consider other information on each snapshot included in the model, such as the context and the community.

CONFLICT OF INTEREST
The authors declare no conflict of interest.

AUTHOR CONTRIBUTIONS
Ting Zhang conducted the research and wrote the paper. Kun Zhang analyzed the data. All authors had approved the final version.