Journal of Shandong University(Engineering Science) ›› 2024, Vol. 54 ›› Issue (1): 1-10.doi: 10.6040/j.issn.1672-3961.0.2022.390

• Machine Learning & Data Mining •     Next Articles

Importance identification method based on multi-order neighborhood hierarchical association contribution of nodes

Gang HU1,2(),Lemeng WANG1,Zhiyu LU1,Qin WANG1,Xiang XU3   

  1. 1. School of Management Science and Engineering, Anhui University of Technology, Maanshan 243032, Anhui, China
    2. Key Laboratory of Multidisciplinary Management and Control of Complex Systems of Anhui Higher Education Institutes, Maanshan 243032, Anhui, China
    3. Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, Hunan, China
  • Received:2022-11-25 Online:2024-02-20 Published:2024-02-01

RichHTML

8

PDF (PC)

128

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

CLC Number: 

  • TP391

Fig.1

K-shell exploded schematic diagram"

Fig.2

Diagram of example network"

Table 1

Statistical characteristics of sample network"

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

Fig.3

Simulation experiments based on the edge deletion method (example network)"

Table 2

Structural characteristics of six real networks"

网络名 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

Table 3

Resolution of each algorithm in six real networks"

网络分辨率
文献[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

Fig.4

Change of the ratio of the number of network subgraphs after removing the connecting edges"

Fig.5

Change of the maximum subgraph scale of the network after removing the connecting edges"

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
[1] Fengbo LAI,Bing XU,Ying XU,Lei ZHANG,Yirong SUN. 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.
[2] LIN Xiaowei, CHEN Lifei. Community detection using nonnegative matrix factorization with structure extension [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 57-64.
[3] HUANG Chengkai, YANG Hao, JIANG Bin, CHENG Shuyao. Fault tolerant cooperative control for a class of complex networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 203-209.
[4] ZHANG Yuting, LI Wang, WANG Chenguang, LIU Youquan, SHI Hongjun. Synchronization of time-delayed complex dynamical networks with discontinuous coupling [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(4): 43-49.
[5] HAO Chongqing, WANG Zhihong. Classification and analysis of epileptic EEG based on complex networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 8-15.
[6] LI Wang, MA Zhicai, SHI Hongjun. Finite-time stochastic generalized outer synchronization of time-delayed complex dynamical networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 1-8.
[7] CHU Xiaodong, ZHANG Rongxiang, HUANG Haoyi, TANG Maosen. Synergetic physical-cyber simulation platform for global energy interconnection [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 103-110.
[8] LI Wang1,2, SHI Yong2, MA Ji-wei2. Finite-time outer synchronization of complex dynamical networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(2): 48-53.
[9] ZHAO Yong-qing, JIANG Ming-hui. Adaptive synchronous feedback control of mixed time-varying delayed and double-linked complex networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 61-68.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] WANG Su-yu,<\sup>,AI Xing<\sup>,ZHAO Jun<\sup>,LI Zuo-li<\sup>,LIU Zeng-wen<\sup> . Milling force prediction model for highspeed end milling 3Cr2Mo steel[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 1 -5 .
[2] ZHANG Yong-hua,WANG An-ling,LIU Fu-ping . The reflected phase angle of low frequent inhomogeneous[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 22 -25 .
[3] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[4] SHI Lai-shun,WAN Zhong-yi . Synthesis and performance evaluation of a novel betaine-type asphalt emulsifier[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 112 -115 .
[5] KONG Xiang-zhen,LIU Yan-jun,WANG Yong,ZHAO Xiu-hua . Compensation and simulation for the deadband of the pneumatic proportional valve[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 99 -102 .
[6] LAI Xiang . The global domain of attraction for a kind of MKdV equations[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 87 -92 .
[7] YU Jia yuan1, TIAN Jin ting1, ZHU Qiang zhong2. Computational intelligence and its application in psychology[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 1 -5 .
[8] LI Liang, LUO Qiming, CHEN Enhong. Graph-based ranking model for object-level search
[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 15 -21 .
[9] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[10] WANG Bo,WANG Ning-sheng . Automatic generation and combinatory optimization of disassembly sequence for mechanical-electric assembly[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 52 -57 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd