Identification of critical nodes in temporal networks based on graph convolution union computing

doi:10.3785/j.issn.1008-973X.2023.05.009

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)

Abstract

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 words： temporal 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）

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Chuan-hua ZHOU
	Li-chun CAO
	Jia-yi ZHOU
	Feng ZHAN

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:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2023.05.009 OR https://www.zjujournals.com/eng/Y2023/V57/I5/930

图卷积融合计算时效网络节点重要性评估分析

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

关键词： 时效网络, 关键节点识别, 超邻接矩阵, 图卷积神经网络, 全局时序效率

Fig.1 Structure diagram of ISGC model

Fig.2 Spectral convolutional network structure diagram

Fig.3 Spectral graph convolution operator

Tab.1 Empirical network data set feature description

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]. https://arxiv.org/abs/1609.02907.

[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]. https://arxiv.org/abs/1312.6203.

[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.

Viewed

Full text

Abstract

Cited

Shared

Discussed