Critical Nodes in Temporal Networks: History
View Latest Version
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor:
Enyu Yu
,
Yan Fu
,
Junlin Zhou
,
Hongliang Sun
,
Duanbing Chen

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) [20] 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) [21] and long short-term memory networks (LSTM) [22] 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) [23] 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. [24] 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. [25] proposed the temporal version of dynamic-sensitive centrality, which extends dynamic-sensitive centrality [26] 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. [27] 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. [28] 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 [29] 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) [30] 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 [31] 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 [32][33] and node [34][35] classification. Among them, DGNN [36] has recently prevailed deep learning models used to deal with temporal graphs, which often make use of a graph neural network (GNN) [37] and recurrent neural network (RNN) [38]. GCRN-M [39] stacks a spectral GCN [40] and a standard LSTM to predict structured sequences of data. DyGGNN [41] uses a gated graph neural network (GGNN) [42] combined with a standard LSTM to learn the evolution of dynamic graphs. Chen et al. [43] 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. [44], 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

References

  1. Weng, J.; Lim, E.P.; Jiang, J.; He, Q. TwitterRank: Finding topic-sensitive influential twitterers. In Proceedings of the WSDM 2010-Proceedings of the 3rd ACM International Conference on Web Search and Data Mining, New York, NY, USA, 3–6 February 2010; pp. 261–270.
  2. Ghosh, S.; Banerjee, A.; Sharma, N.; Agarwal, S.; Ganguly, N.; Bhattacharya, S.; Mukherjee, A. Statistical analysis of the Indian Railway Network: A complex network approach. Acta Phys. Pol. B Proc. Suppl. 2011, 4, 123–137.
  3. GuimerΓ , R.; Danon, L.; DΓ­az-Guilera, A.; Giralt, F.; Arenas, A. Self-similar community structure in a network of human interactions. Phys. Rev. E-Stat. Phys. Plasmas Fluids Relat. Interdiscip. Top. 2003, 68, 065103.
  4. Colizza, V.; Flammini, A.; Serrano, M.A.; Vespignani, A. Detecting rich-club ordering in complex networks. Nat. Phys. 2006, 2, 110–115.
  5. Gallos, L.; Havlin, S.; Kitsak, M.; Liljeros, F.; Makse, H.; Muchnik, L.; Stanley, H. Identification of influential spreaders in complex networks. Nat. Phys. 2010, 6, 888–893.
  6. Zhou, F.; LΓΌ, L.; Mariani, M.S. Fast influencers in complex networks. Commun. Nonlinear Sci. Numer. Simul. 2019, 74, 69–83.
  7. Zhang, T.; Li, P.; Yang, L.X.; Yang, X.; Tang, Y.Y.; Wu, Y. A discount strategy in word-of-mouth marketing. Commun. Nonlinear Sci. Numer. Simul. 2019, 74, 167–179.
  8. Wang, S.; Lv, W.; Zhang, J.; Luan, S.; Chen, C.; Gu, X. Method of power network critical nodes identification and robustness enhancement based on a cooperative framework. Reliab. Eng. Syst. Saf. 2021, 207, 107313.
  9. Joodaki, M.; Dowlatshahi, M.B.; Joodaki, N.Z. An ensemble feature selection algorithm based on PageRank centrality and fuzzy logic. Knowl.-Based Syst. 2021, 233, 107538.
  10. Wei, X.; Zhao, J.; Liu, S.; Wang, Y. Identifying influential spreaders in complex networks for disease spread and control. Sci. Rep. 2022, 12, 5550.
  11. LΓΌ, L.; Chen, D.; Ren, X.L.; Zhang, Q.M.; Zhang, Y.C.; Zhou, T. Vital nodes identification in complex networks. Phys. Rep. 2016, 650, 1–63.
  12. Guo, C.; Yang, L.; Chen, X.; Chen, D.; Gao, H.; Ma, J. Influential nodes identification in complex networks via information entropy. Entropy 2020, 22, 242.
  13. Chen, D.B.; Sun, H.L.; Tang, Q.; Tian, S.Z.; Xie, M. Identifying influential spreaders in complex networks by propagation probability dynamics. Chaos 2019, 29, 030120.
  14. Bonacich, P. Factoring and weighting approaches to status scores and clique identification. J. Math. Sociol. 1972, 2, 113–130.
  15. Freeman, L.C. A set of measures of centrality based on betweenness. Sociometry 1977, 40, 35–41.
  16. Cui, P.; Wang, X.; Pei, J.; Zhu, W. A Survey on Network Embedding. IEEE Trans. Knowl. Data Eng. 2019, 31, 833–852.
  17. Yu, E.Y.; Wang, Y.P.; Fu, Y.; Chen, D.B.; Xie, M. Identifying critical nodes in complex networks via graph convolutional networks. Knowl.-Based Syst. 2020, 198, 105893.
  18. Zhao, G.; Jia, P.; Zhou, A.; Zhang, B. InfGCN: Identifying influential nodes in complex networks with graph convolutional networks. Neurocomputing 2020, 414, 18–26.
  19. Fan, C.; Zeng, L.; Sun, Y.; Liu, Y.Y. Finding key players in complex networks through deep reinforcement learning. Nat. Mach. Intell. 2020, 2, 317–324.
  20. Schmidhuber, J. Deep Learning in neural networks: An overview. Neural Netw. 2015, 61, 85–117.
  21. Schuster, M.; Paliwal, K.K. Bidirectional recurrent neural networks. IEEE Trans. Signal Process. 1997, 45, 2673–2681.
  22. Hochreiter, S.; Urgen Schmidhuber, J. Long Shortterm Memory. Neural Comput. 1997, 9, 1735–1780.
  23. Zhang, Z.; Cui, P.; Zhu, W. Deep Learning on Graphs: A Survey. IEEE Trans. Knowl. Data Eng. 2020, 34, 249–270.
  24. Kim, H.; Anderson, R. Temporal node centrality in complex networks. Phys. Rev. E-Stat. Nonlinear Soft Matter Phys. 2012, 85, 026107.
  25. Huang, D.W.; Yu, Z.G. Dynamic-Sensitive centrality of nodes in temporal networks. Sci. Rep. 2017, 7, 41454.
  26. Liu, J.G.; Lin, J.H.; Guo, Q.; Zhou, T. Locating influential nodes via dynamics-sensitive centrality. Sci. Rep. 2016, 6, 21380.
  27. Taylor, D.; Myers, S.A.; Clauset, A.; Porter, M.A.; Mucha, P.J. Eigenvector-based centrality measures for temporal networks. Multiscale Model. Simul. 2017, 15, 537–574.
  28. Huang, Q.; Zhao, C.; Zhang, X.; Wang, X.; Yi, D. Centrality measures in temporal networks with time series analysis. Epl 2017, 118, 36001.
  29. Chandran, J.; Viswanatham, V.M. Dynamic node influence tracking based influence maximization on dynamic social networks. Microprocess. Microsyst. 2022, 95, 104689.
  30. Jiang, J.L.; Fang, H.; Li, S.Q.; Li, W.M. Identifying important nodes for temporal networks based on the ASAM model. Phys. A Stat. Mech. Its Appl. 2022, 586, 126455.
  31. Bi, J.; Jin, J.; Qu, C.; Zhan, X.; Wang, G.; Yan, G. Temporal gravity model for important node identification in temporal networks. Chaos Solitons Fractals 2021, 147, 110934.
  32. Niepert, M.; Ahmad, M.; Kutzkov, K. Learning convolutional neural networks for graphs. In Proceedings of the 33rd International Conference on Machine Learning, ICML 2016, New York, NY, USA, 19–24 June 2016; Volume 4, pp. 2958–2967.
  33. Kipf, T.N.; Welling, M. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations, ICLR 2017-Conference Track Proceedings, Toulon, France, 24–26 April 2017.
  34. Grover, A.; Leskovec, J. Node2vec: Scalable feature learning for networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, 13–17 August 2016; pp. 855–864.
  35. Ribeiro, L.F.; Saverese, P.H.; Figueiredo, D.R. Struc2vec: Learning Node Representations from Structural Identity. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, 13–17 August 2017; pp. 13–17.
  36. Kazemi, S.M.; Kobyzev, I.; Forsyth, P.; Goel, R.; Jain, K.; Kobyzev, I.; Sethi, A.; Forsyth, P.; Poupart, P.; Goel, R.; et al. Representation Learning for Dynamic Graphs: A Survey. J. Mach. Learn. Res. 2020, 21, 2648–2720.
  37. Wu, Z.; Pan, S.; Chen, F.; Long, G.; Zhang, C.; Yu, P.S. A Comprehensive Survey on Graph Neural Networks. IEEE Trans. Neural Netw. Learn. Syst. 2021, 32, 4–24.
  38. Medsker, L.R.; Jain, L.C. Recurrent Neural Networks Design and Applications. J. Chem. Inf. Model. 2013, 53, 1689–1699.
  39. Seo, Y.; Defferrard, M.; Vandergheynst, P.; Bresson, X. Structured sequence modeling with graph convolutional recurrent networks. In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); LNCS; Springer: Berlin/Heidelberg, Germany, 2018; Volume 11301, pp. 362–373.
  40. Defferrard, M.; Bresson, X.; Vandergheynst, P. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. Adv. Neural Inf. Process. Syst. 2016, 59, 395–398.
  41. Taheri, A.; Gimpel, K.; Berger-Wolf, T. Learning to represent the evolution of dynamic graphs with recurrent models. In Proceedings of the Web Conference 2019-Companion of the World Wide Web Conference, WWW 2019, San Francisco, CA, USA, 13–17 May 2019; pp. 301–307.
  42. Li, Y.; Tarlow, D.; Brockschmidt, M.; Zemel, R. Gated Graph Sequence Neural Networks. arXiv 2015, arXiv:1511.05493.
  43. Chen, J.; Xu, X.; Wu, Y.; Zheng, H. GC-LSTM: Graph convolution embedded LSTM for dynamic link prediction. arXiv 2018, arXiv:1812.04206.
  44. Munikoti, S.; Das, L.; Natarajan, B. Scalable graph neural network-based framework for identifying critical nodes and links in complex networks. Neurocomputing 2022, 468, 211–221.
More
Β© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
This entry is offline, you can click here to edit this entry!
Video Production Service
Feedback