Please wait a minute...
Journal of ZheJiang University (Engineering Science)  2023, Vol. 57 Issue (5): 930-938    DOI: 10.3785/j.issn.1008-973X.2023.05.009
Identification of critical nodes in temporal networks based on graph convolution union computing
Chuan-hua ZHOU1,2(),Li-chun CAO1,Jia-yi ZHOU3,Feng ZHAN4
1. School of Management Science and Engineering, Anhui University of Technology, Maanshan 243032, China
2. School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China
3. Marketing Service Center of Jiangsu Electric Power Co. Ltd, Nanjing 210019, China
4. Maanshan University, Maanshan 243100, China
Download: HTML     PDF(1108KB) HTML
Export: BibTeX | EndNote (RIS)      


The importance measure of nodes in complex networks is correlated with the time attribute. The classical static network model weakens the effective representation of the time attribute of node interaction. A node importance evaluation model for temporal networks based on the graph convolution union computing was proposed. The model migrated the deep learning to dynamic graph data for end-to-end system modeling. Dynamic evolution process of the temporal network structure was assembled by the supra-adjacency matrix. The graph convolutional neural network framework was used to calculate the fusion characteristics of the neighborhood nodes. The node importance order structure over time was analyzed. A comprehensive ranking of node importance was achieved. The simulation experimental results showed that compared with the existing method, the Kendall’s tau values obtained by the proposed method performed well on all the selected network datasets, reflecting the effectiveness and superiority of the proposed method.

Key wordstemporal network      critical node identification      supra-adjacency matrix      graph convolutional neural network      global time efficiency     
Received: 26 May 2022      Published: 09 May 2023
CLC:  TP 301.6  
Fund:  安徽省自然科学基金资助项目(2108085MG236);安徽省高校自然科学研究项目(KJ2021A0385);国家电网科技项目(5400-202118485A-0-5-ZN)
Cite this article:

Chuan-hua ZHOU,Li-chun CAO,Jia-yi ZHOU,Feng ZHAN. Identification of critical nodes in temporal networks based on graph convolution union computing. Journal of ZheJiang University (Engineering Science), 2023, 57(5): 930-938.

URL:     OR


复杂网络节点的重要性度量与时间属性相关,经典静态网络模型弱化对节点交互时间属性的有效表征.将深度学习模型迁移到动态图数据上进行端到端系统建模,提出基于图卷积融合计算的时效网络节点重要性综合评估模型. 通过超邻接矩阵集结时效网络结构特征的动态演化过程,利用图卷积神经网络框架融合计算节点邻域特征,分析节点时序演化重要性顺序结构,实现节点重要性综合排序.仿真实验结果表明,与基线方法相比,所提方法得到的Kendall’s $ \tau $值在所选网络数据集上均表现优良,体现出基于图卷积融合计算的时效网络节点重要性综合评估方法的有效性和优越性.

关键词: 时效网络,  关键节点识别,  超邻接矩阵,  图卷积神经网络,  全局时序效率 
Fig.1 Structure diagram of ISGC model
Fig.2 Spectral convolutional network structure diagram
Fig.3 Spectral graph convolution operator
网络 Num Inter Static During Win
Workspace 92 9827 755 2013-6-24—2013-7-3 10
Enrons 151 33124 1270 2001 12
SFHH 403 70 261 9889 2009 7
Tab.1 Empirical network data set feature description
方法 Workspace Enrons SFHH
ISGC 0.7096 0.7644 0.6997
RA 0.5498 0.4274 0.1657
TD 0.5396 0.5297 0.8379
TB 0.6931 0.5989 0.6861
TC 0.4992 0.7486 0.6945
TK 0.5184 0.4182 0.2746
TDDC 0.3456 0.2693 0.2310
TPR 0.5078 0.6178 0.3120
TGM 0.6841 0.7088 0.7857
Tab.2 Correlation comparison results of ISGC and existing methods with the benchmark sort
Fig.4 Influence of tunable parameters $ \omega $ of coupling relation between adjacent layers on correlation between ISGC and benchmark sort
[1]   HOLME P, SARAMÄKI J Temporal networks[J]. Physics Reports, 2012, 519 (3): 97- 125
doi: 10.1016/j.physrep.2012.03.001
[2]   WU L R, QI J Y, SHI N, et al Revealing the relationship of topics popularity and bursty human activity patterns in social temporal networks[J]. Physica A: Statistical Mechanics and its Applications, 2022, 588: 126568
doi: 10.1016/j.physa.2021.126568
[3]   黄强娟. 时序网络结构建模与演化分析研究[D]. 长沙: 国防科技大学, 2019: 3-4.
HUANG Qiang-juan. Research on structure modeling and evolution analysis in temporal network [D]. Changsha: National University of Defense Technology, 2019: 3-4.
[4]   IÑIGUEZ G, PINEDA C, GERSHENSON C, et al Dynamics of ranking[J]. Nature Communications, 2022, 13: 1646
doi: 10.1038/s41467-022-29256-x
[5]   TAYLOR D, MYERS S A, CLAUSET A, et al Eigenvector-based centrality measures for temporal networks[J]. Multiscale Modeling and Simulation, 2017, 15 (1): 537- 574
doi: 10.1137/16M1066142
[6]   杨剑楠, 刘建国, 郭强 基于层间相似性的时序网络节点重要性研究[J]. 物理学报, 2018, 67 (4): 279- 286
YANG Jian-nan, LIU Jian-guo, GUO Qiang Node importance identification for temporal network based on inter-layer similarity[J]. Acta Physica Sinica, 2018, 67 (4): 279- 286
doi: 10.7498/aps.67.20172255
[7]   胡钢, 许丽鹏, 徐翔 基于时序网络层间同构率动态演化的重要节点辨识[J]. 物理学报, 2021, 70 (10): 355- 366
HU Gang, XU Li-peng, XU Xiang Evolution of inter-layer isomorphism rate in temporal networks[J]. Acta Physica Sinica, 2021, 70 (10): 355- 366
[8]   JIANG J L, FANG H, LI S Q, et al Identifying important nodes for temporal networks based on the ASAM model[J]. Physica A: Statistical Mechanics and its Applications, 2022, 586: 126455
doi: 10.1016/j.physa.2021.126455
[9]   TANG J, MUSOLESI M, MASCOLO C, et al. Temporal distance metrics for social network analysis [C]// Proceedings of the 2nd ACM Workshop on Online Social Networks. Barcelona: ACM, 2009: 31-36.
[10]   TANG J, SCELLATO S, MUSOLESI M, et al Small-world behavior in time-varying graphs[J]. Physical Review E, 2010, 81 (5): 055101
doi: 10.1103/PhysRevE.81.055101
[11]   KIM H, ANDERSON R Temporal node centrality in complex networks[J]. Physical Review E, 2012, 85 (2): 026107
doi: 10.1103/PhysRevE.85.026107
[12]   刘建国, 任卓明, 郭强, 等 复杂网络中节点重要性排序的研究进展[J]. 物理学报, 2013, 62 (17): 9- 18
LIU Jian-guo, REN Zhuo-ming, GUO Qiang, et al Node importance ranking of complex networks[J]. Acta Physica Sinica, 2013, 62 (17): 9- 18
doi: 10.7498/aps.62.178901
[13]   FREEMAN L C A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40 (1): 35- 41
doi: 10.2307/3033543
[14]   SABIDUSSI G The centrality index of a graph[J]. Psychometrika, 1966, 31 (4): 581- 603
doi: 10.1007/BF02289527
[15]   WANG Z, PEI X, WANG Y, et al. Ranking the key nodes with temporal degree deviation centrality on complex networks [C]// Proceedings of the 29th Chinese Control And Decision Conference (CCDC). Chongqing: IEEE, 2017: 1484-1489.
[16]   TAKAGUCHI T, YANO Y, YOSHIDA Y Coverage centralities for temporal networks[J]. The European Physical Journal B, 2016, 89 (2): 1- 11
[17]   YE Z H, ZHAN X X, ZHOU Y Z, et al. Identifying vital nodes on temporal networks: An edge-based k-shell decomposition [C]// Proceedings of the 36th Chinese Control Conference. Dalian: IEEE, 2017: 1402-1407.
[18]   KITSAK M, GALLOS L K, HAVLIN S, et al Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6 (11): 888- 893
doi: 10.1038/nphys1746
[19]   QU C Q, ZHAN X X, WANG G H, et al Temporal information gathering process for node ranking in time-varying networks[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2019, 29 (3): 033116
doi: 10.1063/1.5086059
[20]   梁耀洲, 郭强, 殷冉冉, 等 基于排名聚合的时序网络节点重要性研究[J]. 电子科技大学学报, 2020, 49 (4): 519- 523
LIANG Yao-zhou, GUO Qiang, YIN Ran-ran, et al Node importance identification for temporal network based on ranking aggregation[J]. Journal of University of Electronic Science and Technology of China, 2020, 49 (4): 519- 523
doi: 10.12178/1001-0548.2019087
[21]   KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks [EB/OL]. [2017-02-22].
[22]   徐冰冰, 岑科廷, 黄俊杰, 等. 图卷积神经网络综述[J]. 计算机学报, 2020, 43(5): 755-780.
XU Bing-bing, CEN Ke-ting, HUANG Jun-jie, et al. A survey on graph convolutional neural network[ J]. Chinese Journal of Computers, 2020, 43(5): 755-780.
[23]   LECUN Y, BOTTOU L, BENGIO Y Gradient-based learning applied to document recognition[J]. Proceedings of the IEEE, 1998, 86 (11): 2278- 2324
doi: 10.1109/5.726791
[24]   张林, 程华, 房一泉 基于卷积神经网络的链接表示及预测方法[J]. 浙江大学学报: 工学版, 2018, 52 (3): 552- 559
ZHANG Lin, CHENG Hua, FANG Yi-quan CNN-based link representation and prediction method[J]. Journal of Zhejiang University: Engineering Science, 2018, 52 (3): 552- 559
[25]   BRUNA J, ZAREMBA W, SZLAM A, et al. Spectral networks and locally connected networks on graphs [EB/OL]. [2014-05-21].
[26]   HE K M, ZHANG X, REN S, et al. Deep residual learning for image recognition [C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition(CVPR). Las Vegas: IEEE, 2016: 770-778.
[27]   ROZENSHTEIN P, GIONIS A. Temporal pagerank [C]// Proceedings of the Machine Learning and Knowledge Discovery in Databases. Riva del Garda: Springer, 2016: 674-689.
[28]   BI J L, JIN J, QU C Q, et al Temporal gravity model for important node identification in temporal networks[J]. Chaos, Solitons and Fractals, 2021, 147: 110934
doi: 10.1016/j.chaos.2021.110934
[29]   GÉNOIS M, VESTERGAARD C L, FOURNET J, et al Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers[J]. Network Science, 2015, 3 (3): 326- 347
doi: 10.1017/nws.2015.10
[30]   KLIMT B, YANG Y M. The enron corpus: a new dataset for email classification research [C]// Proceedings of the European Conference on Machine Learning. Pisa: Springer, 2004: 217-226.
[31]   GÉNOIS M, BARRAT A Can co-location be used as a proxy for face-to-face contacts?[J]. EPJ Data Science, 2018, 7 (1): 11
doi: 10.1140/epjds/s13688-018-0140-1
[32]   LATORA V, MARCHIORI M Efficient behavior of small-world networks[J]. Physical Review Letters, 2001, 87 (19): 198701
doi: 10.1103/PhysRevLett.87.198701
[33]   IYER S, KILLINGBACK T, SUNDARAM B, et al Attack robustness and centrality of complex networks[J]. PloS One, 2013, 8 (4): e59613
doi: 10.1371/journal.pone.0059613
[34]   KENDALL M G A new measure of rank correlation[J]. Biometrika, 1938, 30 (1-2): 81- 93
doi: 10.1093/biomet/30.1-2.81
[1] Gang HU,Qiong NIU,Qin WANG,Li-peng XU,Yong-jun REN. Modeling of node importance in entropy-value structured hole of temporal multilayer network[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(4): 719-725.