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

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

浙江大学学报(工学版)

2023, Vol. 57

Issue (5): 930-938 DOI: 10.3785/j.issn.1008-973X.2023.05.009

计算机技术与控制工程

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

周传华1,2(

),操礼春1,周家亿3,詹凤4

1. 安徽工业大学管理科学与工程学院，安徽马鞍山 243032
2. 中国科学技术大学计算机科学与技术学院，安徽合肥 230027
3. 国家电网江苏电力营销服务中心，江苏南京 210019
4. 马鞍山学院，安徽马鞍山 243100

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

全文: PDF(1108 KB) HTML

摘要：

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

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

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

收稿日期: 2022-05-26 出版日期: 2023-05-09

CLC:

TP 301.6

基金资助: 安徽省自然科学基金资助项目（2108085MG236）；安徽省高校自然科学研究项目（KJ2021A0385）；国家电网科技项目（5400-202118485A-0-5-ZN）

作者简介: 周传华（1964—），男，教授，从事智能算法和数据挖掘研究. orcid.org/0000-0002-8057-4797. E-mail: chzhou@ahut.edu.cn

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	作者相关文章
	周传华
	操礼春
	周家亿
	詹凤

引用本文:

周传华,操礼春,周家亿,詹凤. 图卷积融合计算时效网络节点重要性评估分析[J]. 浙江大学学报(工学版), 2023, 57(5): 930-938.

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.

链接本文:

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

图 1 ISGC 模型结构示意图

图 2 谱域图卷积网络结构图

图 3 谱域图卷积算子

表 1 实证网络数据集的特征描述

表 2 ISGC和现有方法排序与基准排序的相关性对比结果

图 4 相邻层间耦合关系可调参数 $ \omega $ 对ISGC与基准排序的相关性影响

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]	闫旭,范晓亮,郑传潘,臧彧,王程,程明,陈龙彪. 基于图卷积神经网络的城市交通态势预测算法[J]. 浙江大学学报(工学版), 2020, 54(6): 1147-1155.

Viewed

Full text

Abstract

Cited

Shared

Discussed