# Predicting Critical Nodes in Temporal Networks by Dynamic Graph Convolutional Networks
## 4 Method
### Dynamic Graph Convolutional Network
\(N_{u}^{t}(x)\) is defined as the number of recovered and infected nodes after \(x\) intervals under weighted SIR model from the initial infected node \(u\) in snapshot \(G^{t}\). \(N_{u}^{t}(x)\) can be used to represent the importance of \(u\) in snapshot \(G^{t}\) in this paper. As shown in Figure 3, for a temporal network \(TG=\{G^{1},G^{2},\,\ldots,\,G^{L}\}\), the task is to predict the importance of nodes in snapshot \(G^{t}(t\leq L-10)\) with training data being \(\{G^{1},G^{2},\,\ldots,\,G^{t-1}\}\). Because ten snapshots are used to generate the label, \(\{G^{t-11-s},\,\ldots,\,G^{t-11}\}\) is used as the training set and \(N^{t-10}(10)\) as the label in the model, and the number of input snapshots \(s\) is also needed to determine by traversing \(L\). The loss function is a squared loss function. ### Complexity Analysis

Let the temporal network be \(TG=\{G^{1},G^{2},\,\ldots,\,G^{L}\}\), the size of the neighborhood be \(k(k<<N)\) and use \(s\) snapshots to train DGCN. For each snapshot and node, the time complexity of generating the feature matrix is \(O(k^{2})\), the time complexity of CNN is \(O(k^{2})\)[17] and the time complexity of LSTM is \(O(N)\). So the time complexity of DGCN is \(O(s^{2}\cdot I\cdot k^{2}\cdot N)\), where \(I\) is the number of training iterations. Actually, when all parameters are fixed, the complexity of DGCN is linearly related to the number of nodes in the temporal network. ## 5 Experiments

In this section, datasets, experimental settings and results achieved by DGCN are described in detail. ### Datasets

Four real-world temporal networks are selected to evaluate the proposed method. Some basic properties of these networks are listed in Table 1.

* Email [53]. The directed temporal network is generated by the mail data from a research institution in Europe. * Contact [54]. An undirected temporal network contains connections between users using mobile wireless devices. An edge is generated if two people are in contact. * DNC [55]. A directed temporal network of emails in the 2016 Democratic National Committee email leak. * UCI [56]. A directed temporal network contains sent messages between students at the University of California, Irvine. Figure 3: A schematic diagram of training and predicting by DGCNs. ### Experimental Settings

In this paper, for each dataset, the training set is \(\{G^{31-s},G^{31-s+1},\,\ldots,\,G^{30}\},s\in[1,30]\) with label \(N^{31}(10)\) (training infection rate \(\beta_{t}=0.05\)) and testing set is \(\{G^{41-s},G^{41-s+1},\,\ldots,\,G^{40}\}\) with label \(N^{41}(10)\). That is, for DGCN and all benchmark methods, the snapshot \(G^{t}(t>40)\) is unknown, only \(G^{t},t\leq 40\) can be used to predict the importance of nodes in \(G^{41}\). Finally, compare the prediction results with \(N^{41}(10)\) to verify the performance of the methods. In addition, the GPU for all experiments is 1600 MHz with 8G memory. In the field of deep learning, GPU is often used to train models, and subsequent experiments are compared on the same GPU. ### Benchmark Methods

In order to effectively evaluate the performance of DGCN, benchmark methods include two types; one is based on network structure and propagation dynamics, and the other is based on graph neural networks. The temporal k-shell (TK) [29] is defined as

\[TK(v)=\sum_{u\in\Gamma_{v}}\sum_{t=1}^{L}min\big{\{}k_{s}^{t}(v),k_{s}^{t}(u) \big{\}} \tag{6}\]

where \(k_{s}^{t}(v)\) is the k-shell of node \(v\) and \(\Gamma_{v}\) is the neighbors of node \(v\) in snapshot \(t\). Temporal dynamics-sensitive centrality (TDC) [28] is defined as

\[S=\sum_{r=0}^{L-1}\beta H_{*}^{r}\mathbf{A}^{r+1}X \tag{7}\]

\[H_{*}^{t}=\prod_{a=t}^{1}[\beta\mathbf{A}^{a}+(1-\mu)I],H_{*}^{0}=1 \tag{8}\]

where \(S_{i}\) is the score of node \(i\) and \(X=(1,1,\cdots,1)^{T}\), \(\mu\) and \(\beta\) are parameters of the SIR Model. The core of DGCN is how to embed nodes in no-attribute graphs, and can be replaced by other well-known node-embedding methods, such as node2 vec [26] and struc2 vec [27].