基于证据理论的多层超网络影响力节点识别方法

doi:10.11772/j.issn.1001-9081.2023010021

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (1): 182-189.DOI: 10.11772/j.issn.1001-9081.2023010021

所属专题：数据科学与技术

基于证据理论的多层超网络影响力节点识别方法

田阔¹^,²^,³, 吴英晗¹^,²^,³, 胡枫¹^,²^,³()

^1.青海师范大学计算机学院, 西宁 810008
^2.藏语智能信息处理及应用国家重点实验室, 西宁 810008
^3.高原科学与可持续发展研究院, 西宁 810016

收稿日期:2023-01-09 修回日期:2023-04-07 接受日期:2023-04-21 发布日期:2023-06-06 出版日期:2024-01-10
通讯作者: 胡枫
作者简介:田阔（1998—），男，河北保定人，硕士研究生，主要研究方向：超网络；
吴英晗（1996—），女，山东菏泽人，硕士研究生，主要研究方向：超网络；
第一联系人：胡枫（1970—），女，青海西宁人，教授，博士，CCF会员，主要研究方向：复杂网络、超网络。
基金资助:
国家自然科学基金资助项目(61663041);青海省自然科学基金资助项目(2023-ZJ-916M)

Identification method of influence nodes in multilayer hypernetwork based on evidence theory

Kuo TIAN¹^,²^,³, Yinghan WU¹^,²^,³, Feng HU¹^,²^,³()

^1.College of Computer，Qinghai Normal University，Xining Qinghai 810008，China
^2.State Key Laboratory of Tibetan Intelligent Information Processing and Application，Xining Qinghai 810008，China
^3.Academy of Plateau Science and Sustainability，Xining Qinghai 810016，China

Received:2023-01-09 Revised:2023-04-07 Accepted:2023-04-21 Online:2023-06-06 Published:2024-01-10
Contact: Feng HU
About author:TIAN Kuo， born in 1998， M. S. candidate. His research interests include hypernetwork.
WU Yinghan， born in 1996， M. S. candidate. Her research interests include hypernetwork.
Supported by:
National Natural Science Foundation of China(61663041);Natural Science Foundation of Qinghai Province(2023-ZJ-916M)

摘要/Abstract

摘要：

针对多层超网络研究多集中于拓扑结构，且影响力节点识别方法中涉及指标较为单一，无法全面准确识别影响力节点的情况，提出一种基于证据理论的多层超网络影响力节点识别方法。首先，在多层超网络拓扑结构基础上，根据聚合网络思想构建多层聚合超网络；其次，基于证据理论定义问题的辨识框架；最后，利用D-S（Dempster-Shafer）证据组合方法，融合网络的局部、位置和全局指标以识别网络影响力节点。将该方法应用于arXiv数据集构建的物理-计算机科学双层科研合作超网络（MAH），在基于RP（Reactive Process）和CP（Contact Process）策略的易感-感染-易感（SIS）超网络传播模型中，与超度中心性、K-shell、接近中心性方法等相比，传播速度最快，且最先达到稳态；隔离影响力排名前6%节点后，网络平均超度、聚类系数以及网络效率均减小；随着隔离影响力节点比例的增大，网络子图数量增速与接近中心性方法相近；通过单调性指标值度量识别结果粗粒度，达到0.999 8，识别结果具有较高区分度。综合多个实验结果，表明该多层超网络影响力节点识别方法准确有效。

关键词: 证据理论, 多层超网络, 辨识框架, 证据组合, 影响力节点, 超网络传播

Abstract:

In view of the fact that most researches on multilayer hypernetwork mainly focus on the topology structure， and influence node identification methods involve relatively single indicators， which cannot comprehensively and accurately identify influence nodes， an identification method of influence nodes in multilayer hypernetwork based on evidence theory was proposed. Firstly， based on the topology structure of multilayer hypernetwork， Multilayer Aggregation Hypernetwork （MAH） was constructed according to the idea of aggregation network. Secondly， the discernment framework of problem was defined based on evidence theory. Finally， Dempster-Shafer （D-S） evidence combination method was used to fuse local， location and global indicators of network to identify influence nodes. The proposed method was applied to physics-computer science double-layer scientific research cooperation hypernetwork constructed by arXiv dataset. Compared with hyperdegree centrality， K-shell， closeness centrality methods， etc.， the proposed method has the fastest propagation speed and reaches steady state first in the Susceptible-Infected-Susceptible （SIS） hypernetwork propagation model based on Reactive Process （RP） and Contact Process （CP） strategies. After isolating top 6% of influence nodes， the average network hyperdegree， clustering coefficient and network efficiency decreased. With the increase of proportion of isolated influence nodes， the growth rate of number of network subgraphs was similar to that of the closeness centrality method. The coarse granularity of identification result was measured by monotonicity index value， which reached 0.999 8， and recognition result had a high discrimination degree. The results of several experiments show that the proposed identification method of influence nodes in multilayer hypernetwork is accurate and effective.

Key words: evidence theory, multilayer hypernetwork, discernment framework, evidence combination, influence node, hypernetwork propagation

中图分类号:

TP301.5

田阔, 吴英晗, 胡枫. 基于证据理论的多层超网络影响力节点识别方法[J]. 计算机应用, 2024, 44(1): 182-189.

Kuo TIAN, Yinghan WU, Feng HU. Identification method of influence nodes in multilayer hypernetwork based on evidence theory[J]. Journal of Computer Applications, 2024, 44(1): 182-189.

图/表 10

图1 双层超网络拓扑结构示意图

Fig. 1 Schematic diagram of two-layer hypernetwork topology

图2 多层聚合超网络示意图

Fig. 2 Schematic diagram of multilayer aggregation hypernetwork

表1 arXiv物理-计算机科学双层超网络拓扑特征

Tab. 1 Topological characteristics of arXiv Physics-Computer Science two-layer hypernetwork

网络	节点数	超边数	平均超度	聚类系数	平均路径长度
物理超网络	4 091	2 759	3.35	0.76	5.82
计算机科学超网络	4 091	2 750	3.08	0.75	6.99
聚合超网络	4 091	3 357	4.52	0.78	4.68

表2 4种方法识别的节点影响力排名前10节点

Tab. 2 Top 10 nodes ranked by node influence by four methods

Rank	DC	Ks	CC	MHEC
1	v601	v1164，v1165	v132	v601
2	v602	v602，v1009，v1068，v1069， v1163	v35	v867
3	v587	v495，v496，v587	v108	v461
4	v74，v703，v867	—	v144	v703
5	v1164，v1165	—	v601	v602
6	v402	—	v154	v402
7	v73	—	v147，v161	v135
8	—	—	v135	v587
9	—	—	v399	v108
10	—	—	—	v73

图3 基于RP策略的节点传播影响力比较

Fig. 3 Comparison of node propagation influence based on RP strategy

图4 基于CP策略的节点传播影响力比较

Fig. 4 Comparison of node propagation influence based on CP strategy

表3 隔离节点影响力前6%节点后网络统计特性

Tab. 3 Statistical properties of network after isolating top 6% influence nodes

指标	平均超度	聚类系数	超网络效率
隔离节点前	3.23	0.76	0.20
隔离节点后	2.99	0.73	0.16

图5 不同方法剔除节点比例和子图个数的关系

Fig. 5 Relationship between proportion of eliminated nodes and number of subgraphs for different methods

图6 不同方法识别结果

Fig. 6 Identification results of different methods

表4 不同方法的单调性指标计算结果

Tab. 4 Results of monotonicity index calculation for different methods

指标	$M (R)$	指标	$M (R)$
DC	0.784 8	CC	0.999 3
Ks	0.773 6	MHEC	0.999 8

表4 不同方法的单调性指标计算结果

Tab. 4 Results of monotonicity index calculation for different methods

指标	$M (R)$	指标	$M (R)$
DC	0.784 8	CC	0.999 3
Ks	0.773 6	MHEC	0.999 8

参考文献 32

1	KIM C H， JO M， LEE J S， et al. Link overlap influences opinion dynamics on multiplex networks of Ashkin-Teller spins ［J］. Physical Review E， 2021， 104： 064304. 10.1103/physreve.104.064304
2	ULLAH A， WANG B， SHENG J F， et al. Identifying vital nodes from local and global perspectives in complex networks ［J］. Expert Systems with Applications， 2021， 186： 115778. 10.1016/j.eswa.2021.115778
3	DANZIGER M M， A-L BARABÁSI. Recovery coupling in multilayer networks ［J］. Nature Communications， 2022， 13： 955. 10.1038/s41467-022-28379-5
4	QIU Z， FAN T， LI M， et al. Identifying vital nodes by Achlioptas process ［J］. New Journal of Physics， 2021， 23： 033036. 10.1088/1367-2630/abe971
5	WEN S， JIANG J， LIU B， et al. Using epidemic betweenness to measures the influence of users in complex networks ［J］. Journal of Network and Computer Applications， 2017， 78： 288-299. 10.1016/j.jnca.2016.10.018
6	王曰芬，王一山，杨洁.基于社区发现和关键节点识别的网络舆情主题发现与实证分析［J］.图书与情报， 2020（5）： 48-58.
	WANG Y F， WANG Y S， YANG J. Topic discovery and empirical analysis of network public opinion based on community detection and key node identification ［J］. Library and Information， 2020（5）： 48-58.
7	SCHOUTEN A P， JANSSEN L， VERSPAGET M. Celebrity vs. Influencer endorsements in advertising： The role of identification， credibility， and Product-Endorser fit ［J］. International Journal of Advertising， 2020， 39（2）： 258-281. 10.1080/02650487.2019.1634898
8	郝志刚，秦丽.基于多属性综合评价的食品安全标准引用网络重要节点发现方法［J］.计算机应用， 2022， 42（4）： 1178-1185.
	HAO Z G， QIN L. Method for discovering important nodes in food safety standard reference network based on multi-attribute comprehensive evaluation ［J］. Journal of Computer Applications， 2022， 42（4）： 1178-1185.
9	CHEN H， DUAN J， DAI Y， et al. A novel type-sensitive PageRank algorithm for importance ranking of heterogeneous network nodes ［C］// Advances in Precision Instruments and Optical Engineering. Singapore： Springe， 2022： 491-500. 10.1007/978-981-16-7258-3_46
10	XU Y， FENG Z， QI X. Signless-Laplacian eigenvector centrality： A novel vital nodes identification method for complex networks ［J］. Pattern Recognition Letters， 2021， 148： 7-14. 10.1016/j.patrec.2021.04.018
11	YANG X， XIAO F. An improved gravity model to identify influential nodes in complex networks based on k-shell method ［J］. Knowledge-Based Systems， 2021， 227： 107198. 10.1016/j.knosys.2021.107198
12	BOCCALETTI S， BIANCONI G， CRIADO R， et al. The structure and dynamics of multilayer networks ［J］. Physics Reports， 2014， 544（1）： 1-122. 10.1016/j.physrep.2014.07.001
13	MAJHI S， PERC M， GHOSH D. Dynamics on higher-order networks： A review ［J］. Journal of the Royal Society Interface， 2022， 19（188）： 20220043. 10.1098/rsif.2022.0043
14	王宇昂.多层复杂网络建模及其重要节点识别方法研究［D］.长沙：国防科技大学， 2018： 43-55.
	WANG Y A. Research on modeling of multiplex complex networks and identification of important nodes ［D］. Hunan： National University of Defense Technology， 2018： 43-55.
15	LI X， ZHANG X， ZHAO C， et al. Identifying highly influential nodes in multilayer networks based on global propagation ［J］. Chaos： An Interdisciplinary Journal of Nonlinear Science， 2020， 30（6）： 061107. 10.1063/5.0005602
16	TUDISCO F， HIGHAM D J. Node and edge nonlinear eigenvector centrality for hypergraphs ［J］. Communications Physics， 2021， 4： 201. 10.1038/s42005-021-00704-2
17	XIE X， ZHAN X， ZHANG Z， et al. Vital node identification in hypergraphs via gravity model ［J］. Chaos： An Interdisciplinary Journal of Nonlinear Science， 2023， 33（1）： 013104. 10.1063/5.0127434
18	卢文，赵海兴，孟磊，等.具有双峰特性的双层超网络模型［J］.物理学报， 2021， 70（1）： 018901. 10.7498/aps.70.20201065
	LU W， ZHAO H X， MENG L， et al. Double-layer hypernetwork model with bimodal peak characteristics ［J］. Acta Physica Sinica， 2021， 70（1）： 018901. 10.7498/aps.70.20201065
19	刘强，方锦清，李永.三层超网络演化模型特性研究［J］.复杂系统与复杂性科学， 2015， 12（2）： 64-71. 10.13306/j.1672-3813.2015.02.010
	LIU Q， FANG J Q， LI Y. Some characteristics of three-layer supernetwork evolution model ［J］. Complex Systems and Complexity Science， 2015， 12（2）： 64-71. 10.13306/j.1672-3813.2015.02.010
20	ANWAR M S， RAKSHIT S， GHOSH D， et al. Stability analysis of intralayer synchronization in time-varying multilayer networks with generic coupling functions ［J］. Physical Review E， 2022， 105（2）： 024303. 10.1103/physreve.105.024303
21	VASILYEVA E， KOZLOV A， ALFARO-BITTNER K， et al. Multilayer representation of collaboration networks with higher-order interactions ［J］. Scientific Reports， 2021， 11： 5666. 10.1038/s41598-021-85133-5
22	BERGE C. Graphs and Hypergraphs ［M］. New York： American Elsevier Publishing Company， 1973： 389. 10.1016/s0924-6509(09)70330-7
23	RAKSHIT S， BERA B K， BOLLT E M， et al. Intralayer synchronization in evolving multiplex hypernetworks： Analytical approach ［J］. SIAM Journal on Applied Dynamical Systems， 2020， 19（2）： 918-963. 10.1137/18m1224441
24	周丽娜，李发旭，巩云超，等.基于K-shell的超网络关键节点识别方法［J］.复杂系统与复杂性科学， 2021， 18（3）： 15-22.
	ZHOU L N， LI F X， GONG Y C， et al. Identification methods of vital nodes based on K-shell in hypernetworks ［J］. Complex Systems and Complexity Science， 2021， 18（3）： 15-22.
25	DEMPSTER A P. A generalization of Bayesian inference ［J］. Journal of the Royal Statistical Society： Series B （Methodological）， 1968， 30（2）： 205-232. 10.1111/j.2517-6161.1968.tb00722.x
26	SHAFER G. A Mathematical Theory of Evidence ［M］. Princeton： Princeton University Press， 1976： 75-86.
27	BIANCONI G. Multilayer Networks： Structure and Function ［M］. New York： Oxford University Press， 2018： 106. 10.1093/oso/9780198753919.003.0011
28	DE DOMENICO M， LANCICHINETTI A， ARENAS A， et al. Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems ［J］. Physical Review X， 2015， 5： 011027. 10.1103/physrevx.5.011027
29	JUUL J L， BENSON A R， KLEINBERG J. Hypergraph patterns and collaboration structure ［EB/OL］. ［2022-11-05］. . 10.3389/fphy.2023.1301994
30	SUO Q， GUO J-L， SHEN A-Z. Information spreading dynamics in hypernetworks ［J］. Physica A： Statistical Mechanics and its Applications， 2018， 495： 475-487. 10.1016/j.physa.2017.12.108
31	DE ARRUDA G F， COZZO E， PEIXOTO T P， et al. Disease localization in multilayer networks ［J］. Physical Review X， 2017， 7： 011014. 10.1103/physrevx.7.011014
32	CRIADO R， ROMANCE M， VELA-PÉREZ M. Hyperstructures， a new approach to complex systems ［J］. International Journal of Bifurcation and Chaos， 2010， 20（3）： 877-883. 10.1142/s0218127410026162

[1]	王思蕊, 程世娟, 袁非梦. 基于改进证据融合的高可靠产品可靠性评估方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2140-2146.
[2]	杨磊, 赵红东. 基于轻量级深度神经网络的环境声音识别[J]. 计算机应用, 2020, 40(11): 3172-3177.
[3]	李旭峰, 宋亚飞, 李晓楠. 考虑决策者时序偏好的时域证据融合方法[J]. 计算机应用, 2019, 39(6): 1626-1631.
[4]	张利, 孙军, 李大伟, 牛明航, 高一丹. 基于融合型深度学习的滚动轴承亚健康识别算法[J]. 计算机应用, 2018, 38(8): 2224-2229.
[5]	王莎莎, 冯子亮, 傅可人. 基于图节点中心性和空间自相关的显著性检测方法[J]. 计算机应用, 2018, 38(12): 3547-3556.
[6]	邰滢滢, 庞影, 段苛苛, 付云鹏. 基于改进权重的D-S证据理论的动态负载平衡算法[J]. 计算机应用, 2018, 38(10): 2976-2981.
[7]	王剑, 张志勇, 乔阔远. 降低相似度碰撞的证据融合方法[J]. 计算机应用, 2018, 38(10): 2794-2800.
[8]	邓达平, 谢小云, 郭子璇. 直觉模糊环境下考虑有限理性特征的决策方法[J]. 计算机应用, 2017, 37(5): 1376-1381.
[9]	王续乔, 王瑾琨. 基于D-S证据理论的室内组合定位算法[J]. 计算机应用, 2017, 37(4): 1198-1201.
[10]	朱轮. 基于后悔理论和证据理论的犹豫模糊决策方法[J]. 计算机应用, 2017, 37(2): 540-545.
[11]	高明霞, 陈福荣. 基于信息融合的中文微博可信度评估方法[J]. 计算机应用, 2016, 36(8): 2071-2075.
[12]	阮闪闪, 王小平, 薛小平. 基于证据理论信任模型的众包质量监控[J]. 计算机应用, 2015, 35(8): 2380-2385.
[13]	夏海英, 徐鲁辉. 基于主动形状模型差分纹理和局部方向模式特征融合的人脸表情识别[J]. 计算机应用, 2015, 35(3): 783-786.
[14]	刘哲席, 阳建宏, 杨德斌, 黎敏, 民现春. 非单点证据体数据融合的Dempster组合规则适用性评价方法[J]. 计算机应用, 2015, 35(2): 461-465.
[15]	杜元伟, 石方园, 杨娜. 基于证据理论/层次分析法的贝叶斯网络建模方法[J]. 计算机应用, 2015, 35(1): 140-146.

基于证据理论的多层超网络影响力节点识别方法

Identification method of influence nodes in multilayer hypernetwork based on evidence theory

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 32

相关文章 15

编辑推荐

Metrics