# Predicting Critical Nodes in Temporal Networks by Dynamic Graph Convolutional Networks
## 4 Method
### Dynamic Graph Convolutional Network  
In this subsection, a framework of DGCN for learning representations from arbitrary temporal networks is proposed. The process of DGCN is shown in Figure 1. In DGCN, we replace a standard snapshot with a weighted snapshot to describe the temporal network in a finer granularity and the weighted degree is used to distinguish neighbors of the same hop in determining the node's neighborhood. The step-weighted snapshot to step the CNN layer can be regarded as a special GCN which implicitly outputs the importance of nodes at time \(t\), essentially, a process of node embedding. Figure 1: An illustration of DGCN. The overall DGCN is shown in Algorithm 1. The input is a temporal network \(TG\) and the output is the influence of nodes in timestamp \(l\). DGCN first calculates the embedding of all nodes at each snapshot and then uses LSTM to predict the importance of nodes in the future. The details of each step are explained below:  
``` Input: temporal network: \(TG=\{G^{1},G^{2},\,\ldots,\,G^{L}\}\), \(G^{t}=\{V^{t},E^{t}\}\); the size of a neighborhood: \(k\); the number of input snapshots: \(s\); the timestamp: \(l,l\in[s+1,L+1]\). Output: the predicted scores for nodes in timestamp \(l\): \(Score_{l}\). 1 Initialize \(E\) randomly; foreach\(i\) in \([l-s,l-1]\)do foreach\(u\) in \(V^{t}\)do
2 the weighted degree of the node \(u\) in time



where \(u_{1},u_{2},...,u_{k}\) are node \(u\) and its \(k-1\) neighbors respectively. \(O_{u_{i}}^{t}\) is the out degree of node \(u_{i}\) in the snapshot \(G^{t}\). In addition, if \(G^{t}\) is disconnected, we might not find enough neighbors for node \(u\), and we need expand \(\textbf{B}_{u}^{t}\) with dummy node to have same shape matrices. For example, in Figure 2b, if \(k=3\), \(G_{A}^{2}\) contains node \(A\), \(D\) and \(B\), \(\textbf{A}_{A}^{2}\) and \(\textbf{B}_{A}^{2}\) are shown as follow:

\[\textbf{A}_{A}^{2}= \begin{bmatrix}0&1&0\\ 1&0&1\\ 0&1&0\end{bmatrix} ,\textbf{B}_{A}^{2}= \begin{bmatrix}1&2&0\\ 2&2&1\\ 0&1&1\end{bmatrix}  \tag{4}\]

If \(k=5\), we need add 2 dummy nodes and \(\textbf{B}_{A}^{2}\) are shown as:

\[\textbf{B}_{A}^{2}= \begin{bmatrix}1&2&0&0&0\\ 2&2&1&0&0\\ 0&1&1&0&0\\ 0&0&0&0&0\\ 0&0&0&0&0\end{bmatrix}  \tag{5}\]

CNN Layer: The CNN in this layer is the same as the CNN in \(RCNN\)[17]. Through the convolution processing of feature matrices, the importance of nodes can be implicitly expressed. There are two reasons why we use the same CNN to train nodes in different snapshots instead of training a separate CNNs for each snapshot: (1) Global training does not change the importance ranking of nodes in the same snapshot, and can effectively reduce training parameters. (2) By increasing the number of input snapshots \(s\), a large number of training nodes can be quickly obtained. LSTM Layer: A standard LSTM [51] is used in this layer, and the input element in time \(t\) is \(x_{t}=CNN(\textbf{B}_{u}^{t})\). In addition, the input size is 1, hidden size is 64 and the number of recurrent layers is 2. Finally, a fully connected layer is used to output the predicted score for nodes. Weighted SIR Model and Label: The influence of nodes over a period of time is usually measured by SIR spreading model. In this paper, we use weighted SIR model to measure the influence of nodes in discrete-time temporal networks. In the SIR model [30], each node has one of three states, i.e., susceptible, infected or recovered. In time interval \([\delta\cdot(t-1),\delta\cdot t]\), infected nodes will infect their susceptible neighbors with a probability \(\beta\) and recover with

Figure 2: Unweighted snapshots and weighted snapshots: (**a**) Unweighted snapshots; (**b**) weighted snapshots, \(\delta=1\). a probability \(\mu\). Particularly, in the weighted SIR model, the susceptible node \(u\) will be infected by the infected neighbor \(v\) with \(1-(1-\beta)^{W^{\prime}(v,u)}\).