Critical Nodes in Temporal Networks: History
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor: , , , ,

Many real-world systems can be expressed in temporal networks with nodes playing different roles in structure and function, and edges representing the relationships between nodes. Identifying critical nodes can help us control the spread of public opinions or epidemics, predict leading figures in academia, conduct advertisements for various commodities and so on. 

  • temporal networks
  • critical nodes
  • node embedding
  • deep learning

1. Introduction

Nowadays, people’s lives are closely related to various complex networks, such as social [1], traffic [2] and email [3] networks. Network science is a vast and interdisciplinary research field and is a hot topic in many branches of sciences. Rich-club [4] shows that only a few critical nodes are needed to effectively affect and control the structure and function of the network. Therefore, to identify important nodes is thus significant, allowing us to find influential spreaders [5], control propagation of rumors [6] or epidemics, predict leading figures in academia, conduct advertisements for various commodities [7] and so on. For a variety of specific networks, key node mining can be targeted. In the power network, the protection of important circuit breakers and generating units can effectively prevent the large-scale blackout caused by successive failures [8]. In the application of a search engine, the search results can be sorted according to their matching and importance and returned to the user [9]. When an infectious disease occurs, the source of infection can be treated and isolated in a targeted way to effectively prevent the spread of the infectious agent [10].
In recent years, many critical nodes identification methods in static networks have been proposed [11,12,13]. Researchers have aimed to find critical nodes by some heuristic algorithms, such as degree centrality [14], betweenness centrality [15] and k-shell [5]. With the development of deep learning, many researchers are beginning to solve problems in their own fields with the help of deep learning. Representation learning-based [16] methods embed a node as vectors or matrices, then design suitable learning frameworks to learn features of critical nodes, such as RCNN [17], InfGCN [18] and FINDER [19]. All these methods have good performances on various static networks.

2. Temporal Networks and Graph Neural Networks

2.1. Temporal Networks

Temporal networks can be divided into continuous-time representation and discrete-time representation networks. There is a big difference between the discrete-time and continuous-time temporal networks in modeling methods, and the method of identifying key nodes is not universal. In this research, it only consider the discrete-time temporal networks. A discrete-time temporal network 𝑇𝐺 with time range [0,𝑇] can be defined as a set of ordered static networks (snapshots). That is, 𝑇𝐺={𝐺1,𝐺2,,𝐺𝐿} where 𝐿=𝑇/𝛿 represents the number of snapshots, which is determined by the time span T and the time interval 𝛿 of each snapshot. 𝐺𝑡={𝑉𝑡,𝐸𝑡} represents the spanning subgraph 𝐺𝑡 which consists of nodes 𝑉𝑡 and edges 𝐸𝑡 appearing in [𝛿·(𝑡1),𝛿·𝑡].

2.2. Recurrent Neural Network

A recurrent neural network (RNN) [49] is a special type of neural networks with a hidden layer that recur over time and often used to process sequence data such as stock data. Unlike other neural networks, RNN implement the structure which retains a certain memory of past information. Among of all RNNs, Bidirectional RNNs (Bi-RNNs) [50] and long short-term memory networks (LSTM) [51] are widely used. The standard RNN is based on a simple repeating cell. LSTM extends the repeating cell by combining four interacting units.

2.3. Graph Neural Network

A graph neural network (GNN) [52] combines graph data with neural networks, and performs calculations on graph data. A graph convolutional network (GCN) is usually used to extract all levels of graph representation and perform graph classification tasks. A GCN follows the framework of exchanging information with neighbors and the key issue is to aggregate the node features from its neighborhood.

3. Critical Nodes in Temporal Networks

To deal with the problems of identifying critical nodes in temporal networks, many methods based on structure and propagation dynamics have been proposed, and an intuitive idea is to extend methods in static networks such as degree, closeness and betweenness centrality to temporal networks. By this idea, Kim et al. [31] proposed the time-ordered graph, embedding dynamic networks into directed and static networks. This enables us to extend network properties in a very natural way to the dynamic case. Huang et al. [28] proposed the temporal version of dynamic-sensitive centrality, which extends dynamic-sensitive centrality [32] to temporal networks by the Markov chain for the epidemic model, and the numerical simulation shows that the new centrality performs much better than some topological structural centralities. By coupling centrality matrices in each snapshot into a supracentrality matrix, Taylor et al. [33] proposed an extension framework for static centrality measures such as eigenvector-based centrality and introduced the concepts of marginal and conditional centralities, which facilitate the study of centrality trajectories over time. Huang et al. [34] defined a supra-evolution matrix to describe the structure of temporal networks. with using of the time series analysis, the relationships between different time layers can be learned automatically. Based on the special form of the supra-evolution matrix, the eigenvector centrality calculating problem is turned into the calculation of eigenvectors of several low-dimensional matrices through iteration, which effectively reduces the computational complexity. This type of method can find critical nodes in the current temporal network but can not predict the importance of nodes in the future. To find the most influential nodes, Chandran et al. proposed a method [35] which measures the impact of each node by the triangle property based on 2-hop neighbors. Jiang et al. proposed an attenuation-based supra-adjacency matrix (ASAM) [36] to model temporal networks and evaluated the importance of nodes in temporal network by calculating the eigenvector centrality of the nodes in each time layer. Bi et al. proposed a temporal gravity model [37] which treats basic node properties as the mass and temporal characteristics as the distance to identify important nodes in temporal networks.
In recent years, graph neural networks (GNNs) have become research hotspots and have been used to solve graph-related problems, such as graph [38,39] and node [26,27] classification. Among them, DGNN [40] has recently prevailed deep learning models used to deal with temporal graphs, which often make use of a graph neural network (GNN) [41] and recurrent neural network (RNN) [42]. GCRN-M [43] stacks a spectral GCN [44] and a standard LSTM to predict structured sequences of data. DyGGNN [45] uses a gated graph neural network (GGNN) [46] combined with a standard LSTM to learn the evolution of dynamic graphs. Chen et al. [47] present GC-LSTM, which performs a spectral GCN on the hidden layer of the standard LSTM for dynamic link prediction. At present, DGNNs are mainly aimed at learning representations of entire dynamic graphs, such as DGNN, GCRN-M and DyGGN. The learning framework specific to nodes in temporal networks is still lacking. A novel framework which defined a GNN based model that learns the implicit features of nodes on a representative set is proposed by Munikoti et al. [48], but this representation does not apply to temporal networks. The above works cannot embed the nodes of temporal networks well.

This entry is adapted from the peer-reviewed paper 10.3390/app13127272

This entry is offline, you can click here to edit this entry!