基于节点多阶邻居递阶关联贡献度的重要性辨识

doi:10.6040/j.issn.1672-3961.0.2022.390

摘要/Abstract

摘要：

为更精细化地辨识节点重要性, 扩展节点有效信息集聚范围和类别, 对网络节点的空间位置属性信息与其直接及间接邻居节点间关联结构信息进行融合、集结, 提出复杂网络多阶邻居递阶关联贡献度的节点重要性辨识方法。依据网络节点空间位置层级差异及层间交互信息给出节点层级位置属性贡献度定义; 构建复杂网络目标节点多阶邻居递阶关联贡献度矩阵, 表征直接邻居节点、间接邻居节点与目标节点间关联度对其影响力的递阶贡献; 提出节点跨层跨级空间拓扑位置贡献度与多阶邻居递阶关联贡献度融合的节点重要性辨识方法。仿真试验表明: 在6个真实网络上所提方法有效提升节点重要性辨识的精细性和准确性。本研究通过探究网络节点间多阶递阶交互行为, 为深入探索网络背后的动态演化机理, 进而做出预测和调控提供科学的理论基础。

关键词: 复杂网络, 节点重要性辨识, 多阶邻居相似度, 多阶邻居紧密度, 多阶邻居递阶关联贡献度

Abstract:

In order to identify the node importance more finely and extend the scope and category of effective information gathering of nodes, the spatial location attribute information of network nodes and their direct and indirect neighbor nodes were fused and clustered, a node importance identification method of multi-order neighbor hierarchical association contribution of complex networks was proposed. The definition of the contribution of node level location attributes was given based on the network node spatial location hierarchical differences and inter-layer association information. A complex network target node multi-order neighbor hierarchical association contributions matrix was constructed to characterize the hierarchical contribution of the associations between direct neighbor nodes, indirect neighbor nodes and target nodes to their influence. A node importance identification method that fused node topological location contribution across layers and levels of space with multi-order neighborhood hierarchical association contribution was proposed. The simulation experiments showed that the proposed method could effectively improve the precision and accuracy of node importance identification on six real networks. This study provided a scientific theoretical basis for in-depth exploration of the dynamic evolution mechanism behind the network, and then made prediction and regulation by exploring the multi-order hierarchical interaction behaviors among the network nodes.

Key words: complex network, identification of node importance, multi-order neighbor similarity, multi-order neighbor closeness, multi-order neighbor hierarchical association contribution

中图分类号:

TP391

胡钢, 王乐萌, 卢志宇, 王琴, 徐翔. 基于节点多阶邻居递阶关联贡献度的重要性辨识[J]. 山东大学学报 (工学版), 2024, 54(1): 1-10.

Gang HU, Lemeng WANG, Zhiyu LU, Qin WANG, Xiang XU. Importance identification method based on multi-order neighborhood hierarchical association contribution of nodes[J]. Journal of Shandong University(Engineering Science), 2024, 54(1): 1-10.

图/表 8

图1

图2

表1

图3

表2

表3

图4

图5

参考文献 32

1	YAO S Y , FAN N , HU J , et al. Modeling the spread of infectious diseases through influence maximization[J]. Optimization Letters, 2022, 16 (5): 1- 24.
2	YI Z N , XIN L , HUI M C , et al. Effects of social network structures and behavioral responses on the spread of infectious diseases[J]. Physica A: Statistical Mechanics and Its Applications, 2020, 539, 122907. doi: 10.1016/j.physa.2019.122907
3	KINNE R , CRUCITTI P , ALBERT R , et al. Modeling cascading failures in the North American power grid[J]. The European Physcial Journal B, 2005, 46, 101- 107. doi: 10.1140/epjb/e2005-00237-9
4	陈思谕, 邹艳丽, 王瑞瑞, 等. 电网输电线路耦合强度分配策略研究[J]. 复杂系统与复杂性科学, 2018, 15 (2): 45- 53.
	CHEN Siyu , ZOU Yanli , WANG Ruirui , et al. On the coupling strength distribution strategy of power transmission lines[J]. Complex Systems and Complexity Science, 2018, 15 (2): 45- 53.
5	LIU P . Information dissemination mechanism based on cloud computing cross-media public opinion network environment[J]. International Journal of Information Technologies and Systems Approach (IJITSA), 2021, 14 (2): 70- 83. doi: 10.4018/IJITSA.2021070105
6	YANG L , LI Z W , ALESSANDRO G , et al. Containment of rumor spread in complex social networks[J]. Information Sciences, 2020, 506, 113- 130. doi: 10.1016/j.ins.2019.07.055
7	ALBERT R , JEONG H , ALBERT-LASZLO B . The diameter of the world wide web[J]. Nature, 1999, 401 (6): 130- 131.
8	FREEMAN L C . Aset of measures of centrality based on betweenness[J]. Sociometry, 1977, 40 (1): 35- 41. doi: 10.2307/3033543
9	BORGATTI S P , EVERETT M G . A graph-theoretic perspective on centrality[J]. Social Networks, 2006, 28 (4): 466- 484. doi: 10.1016/j.socnet.2005.11.005
10	PHILLIP B . Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972, 2 (1): 113- 120. doi: 10.1080/0022250X.1972.9989806
11	KATZ L . A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18, 39- 43. doi: 10.1007/BF02289026
12	KITSAK M , GALLOS L , HAVLIN S , et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6 (11): 888- 893. doi: 10.1038/nphys1746
13	ZENG A , ZHANG C J . Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013, 377 (14): 1031- 1035. doi: 10.1016/j.physleta.2013.02.039
14	谢丽霞, 孙红红, 杨宏宇, 等. 基于K-shell的复杂网络关键节点识别方法[J]. 清华大学学报(自然科学版), 2022, 62 (5): 849- 861.
	XIE Lixia , SUN Honghong , YANG Hongyu , et al. Key node recognition in complex networks based on the K-shell method[J]. Journal of Tsinghua University (Science and Technology), 2022, 62 (5): 849- 861.
15	WANG M , LI W C , GUO Y N , et al. Identifying influential spreaders in complex networks based on improved K-shell method[J]. Physica A: Statistical Mechanics and its Applications, 2020, 554, 124229. doi: 10.1016/j.physa.2020.124229
16	ULLAH A , WANG B , SHENG J F , et al. Identification of nodes influence based on global structure model in complex networks[J]. Scientific Reports, 2021, 11 (1): 6173- 6173. doi: 10.1038/s41598-021-84684-x
17	汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法[J]. 物理学报, 2023, 72 (4): 337- 347.
	WANG Tingting , LIANG Zongwen , ZHANG Ruoxi . Importance evaluation method of complex network nodes based on information entropy and iteration factor[J]. Acta Physica Sinica, 2023, 72 (4): 337- 347.
18	尹荣荣, 尹学良, 崔梦頔, 等. 基于重要度贡献的无标度网络节点评估方法[J]. 软件学报, 2019, 30 (6): 1875- 1885.
	YIN Rongrong , YIN Xueliang , CUI Mengdi , et al. Node evaluation method based on importance contribution in scale-free networks[J]. Journal of Software, 2019, 30 (6): 1875- 1885.
19	CHEN D B , LV L Y , SHANG M S , et al. Identifying influential nodes in complex networks[J]. Fuel and Energy Abstracts, 2012, 391 (4): 1777- 1787.
20	阮逸润, 老松杨, 王竣德, 等. 基于领域相似度的复杂网络节点重要度评估算法[J]. 物理学报, 2017, 66 (3): 038902.
	RUAN Yirun , LAO Songyang , WANG Junde , et al. Node importance measurement based on neighborhood similarity in complex network[J]. Acta Physica Sinica, 2017, 66 (3): 038902.
21	马媛媛, 韩华, 瞿倩倩. 基于节点亲密度的重要性评估算法[J]. 计算机科学, 2021, 48 (5): 140- 146.
	MA Yuanyuan , HAN Hua , QU Qianqian . Importance evaluation algorithm based on node intimate degree[J]. Computer Science, 2021, 48 (5): 140- 146.
22	ZHONG S , ZHANG H T , DENG Y , et al. Identification of influential nodes in complex networks: a local degree dimension approach[J]. Information Sciences, 2022, 610, 994- 1009. doi: 10.1016/j.ins.2022.07.172
23	熊才权, 古小惠, 吴歆韵. 基于K-shell位置和两阶邻居的复杂网络节点重要性评估方法[J]. 计算机应用研究, 2023, 40 (3): 738- 742.
	XIONG Caiquan , GU Xiaohui , WU Xinyun . Evaluation method of node importance in complex networks based on K-shell position and neighborhood with in two steps[J]. Application Research of Computers, 2023, 40 (3): 738- 742.
24	胡钢, 高浩, 徐翔, 等. 基于重要度传输矩阵的复杂网络节点重要性辨识方法[J]. 电子学报, 2020, 48 (12): 2402- 2408.
	HU Gang , GAO Hao , XU Xiang , et al. Importance identification method of complex network nodes based on importance transfer matrix[J]. Acta Electronica Sinica, 2020, 48 (12): 2402- 2408.
25	胡钢, 牛琼, 王琴, 等. 时序多层网络熵值结构洞节点重要性建模[J]. 浙江大学学报(工学版), 2023, 57 (4): 719- 725.
	HU Gang , NIU Qiong , WANG Qin , et al. 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.
26	JIANG S Y , ZHOU J , MICHAEL S , et al. Searching for key cycles in a complex network[J]. Physical Review Letters, 2023, 130, 187402. doi: 10.1103/PhysRevLett.130.187402
27	来逢波, 许冰, 续颖, 等. 高铁复杂网络拓扑特征及节点中心性研究[J]. 山东大学学报(工学版), 2022, 52 (6): 14- 22.
	LAI Fengbo , XU Bing , XU Ying , et al. Study on topological characteristics and node centrality of high-speed railway complex network[J]. Journal of Shandong University (Engineering Science), 2022, 52 (6): 14- 22.
28	WANG F F , SUN Z J , GAN Q , et al. Influential node identification by aggregating local structure information[J]. Physica A: Statistical Mechanics and its Applications, 2022, 593, 126885. doi: 10.1016/j.physa.2022.126885
29	QIU L Q , ZHANG J Y , TIAN X B , et al. Ranking influential nodes in complex networks based on local and global structures[J]. Applied Intelligence, 2021, 51 (7): 1- 14.
30	郭茂林, 包崇明, 周丽华, 等. 基于TOPSIS的异质网络影响力最大化[J]. 山东大学学报(工学版), 2022, 52 (2): 31- 40.
	GUO Maolin , BAO Chongming , ZHOU Lihua , et al. Influence maximization of heterogeneous networks based on TOPSIS[J]. Journal of Shandong University (Engineering Science), 2022, 52 (2): 31- 40.
31	BAE J , KIM S . Identifying and ranking influential spreaders in complex networks by neighborhood coreness[J]. Physica A: Statistical Mechanics &. Its Applications, 2014, 395 (4): 549- 559.
32	任卓明, 邵凤, 刘建国, 等. 基于度与集聚系数的网络节点重要性度量方法研究[J]. 物理学报, 2013, 62 (12): 128901. doi: 10.7498/aps.62.128901
	REN Zhuoming , SHAO Feng , LIU Jianguo , et al. Node importance measurement based on the degree and clustering coefficient information[J]. Acta Physica Sinica, 2013, 62 (12): 128901. doi: 10.7498/aps.62.128901

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

n	m	〈k〉	〈l〉	〈c〉
16	58	7.250	1.454	0.527

网络名	n	m	〈k〉	〈l〉	〈c〉
High-school	70	274	10.457 1	2.664 1	0.404 3
Jazz	198	2 742	27.697 0	2.206 0	0.520 2
C-elegans(neural)	297	2 148	28.929 3	2.469 8	0.180 7
Proteins	1 706	3 233	7.276 7	5.093 1	0.005 8
Adolescent health	2 539	10 455	10.215 8	4.516 4	0.141 9
Blogs	3 982	16 716	3.426 2	2.746 7	0.225 9

网络	分辨率
网络	文献[7]	文献[12]	文献[14]	文献[19]	文献[24]	文献[32]	DTR方法
High-school	0.823 1	0.546 9	0.998 7	0.999 1	0.971 4	0.999 1	0.999 2
Jazz	0.965 9	0.794 4	0.996 5	0.985 7	0.919 1	0.985 7	0.999 3
C-elegans(neural)	0.921 6	0.609 4	0.866 6	0.964 6	0.997 4	0.964 6	0.997 7
Proteins	0.532 4	0.426 0	0.897 2	0.959 5	0.521 6	0.959 5	0.995 3
Adolescent health	0.867 6	0.524 5	0.779 5	0.637 1	0.964 5	0.637 1	0.999 9
Blogs	0.253 8	0.247 9	0.991 3	0.928 3	0.836 6	0.928 3	0.995 2

[1]	来逢波,许冰,续颖,张蕾,孙义荣. 高铁复杂网络拓扑特征及节点中心性研究[J]. 山东大学学报 (工学版), 2022, 52(6): 14-22.
[2]	赵康,田浩,马欢,杨冬. 基于复杂网络理论的多直流馈入受端电网优化分区方法[J]. 山东大学学报 (工学版), 2022, 52(1): 128-134.
[3]	林晓炜,陈黎飞. 结构扩展的非负矩阵分解社区发现算法[J]. 山东大学学报 (工学版), 2021, 51(2): 57-64.
[4]	黄成凯,杨浩,姜斌,程舒瑶. 一类复杂网络的协同容错控制[J]. 山东大学学报(工学版), 2017, 47(5): 203-209.
[5]	张玉婷,李望,王晨光,刘友权,侍红军. 不连续耦合的时滞复杂动态网络的同步[J]. 山东大学学报(工学版), 2017, 47(4): 43-49.
[6]	郝崇清,王志宏. 基于复杂网络的癫痫脑电分类与分析[J]. 山东大学学报(工学版), 2017, 47(3): 8-15.
[7]	李望,马志才,侍红军. 时滞复杂动态网络的有限时间随机广义外部同步[J]. 山东大学学报(工学版), 2017, 47(3): 1-8.
[8]	褚晓东,张荣祥,黄昊怡,唐茂森. 全球能源互联网物理-信息系统协同仿真平台[J]. 山东大学学报(工学版), 2016, 46(4): 103-110.
[9]	李望1,2,石咏2,马继伟2. 复杂动力学网络的有限时间外部同步[J]. 山东大学学报(工学版), 2013, 43(2): 48-53.
[10]	赵永清, 江明辉. 混合变时滞二重边复杂网络自适应同步反馈控制[J]. 山东大学学报(工学版), 2010, 40(3): 61-68.