搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于加权圈比的复杂网络关键节点识别方法

谢涵臣 吴明功 温祥西 张洺瑜

引用本文:
Citation:

基于加权圈比的复杂网络关键节点识别方法

谢涵臣, 吴明功, 温祥西, 张洺瑜

A method of identifying key nodes in complex networks based on weighted cycle ratio

XIE Hanchen, WU Minggong, WEN Xiangxi, ZHANG Mingyu
Article Text (iFLYTEK Translation)
PDF
HTML
导出引用
  • 圈比作为一种基于圈结构的量化指标, 已在无权无向网络中展现出其在识别关键节点方面的显著优势. 传统的圈比未能充分考虑边权信息对网络结构的影响, 限制了其在更广泛网络分析中的应用. 为了解决这一问题, 本文提出了一种加权网络中新的网络分析指标——加权圈比, 旨在提升识别加权网络中关键节点的准确性. 通过对示例网络的分析, 验证了加权圈比的可行性; 进一步的实验在多个真实世界的网络中表明, 加权圈比不仅与现有的基准指标存在显著差异, 而且在评估网络连通性及早期传播覆盖范围方面, 总体表现优于包括传统圈比在内的其他基准指标. 这些发现强调了加权圈比在网络分析中的潜在价值, 尤其是在处理加权网络时的有效性 .
    In the face of the surge of air transport demand and the increasing risk of flight conflicts, it is very important to effectively manage flight conflicts and accurately identify key conflict aircraft. This paper presents a novel method for identifying critical nodes in flight conflict networks by integrating complex network theory with a weighted cycle ratio (WCR). By modeling aircraft as nodes and conflict relationships as edges, we construct a flight conflict network where the urgency of conflicts is reflected in edge weights. We extend the traditional cycle ratio (CR) concept to propose the WCR, which accounts for both the topological structure of the network and the urgency of conflicts. Furthermore, we combine the WCR with node strength (NS) to form an adjustable mixed indicator (MI) that adaptively balances the importance of nodes based on their involvement in cyclic conflict structure and their individual conflict strength. Through extensive simulations, including node deletion experiments and network robustness analyses, we demonstrate that our method can precisely pinpoint critical nodes in flight conflict networks. The results indicate that regulating these critical nodes can significantly reduce network complexity and conflict risks. Importantly, the effectiveness of our method increases with the complexity of the flight conflict network, making it particularly suitable for scenarios with high aircraft density and complex conflict patterns. Overall, this study not only deepens the theoretical understanding of complex aviation network analysis but also provides a practical tool for improving air traffic control efficiency and safety, thereby contributing to achieving more environmentally friendly and sustainable air transportation.
  • 图 1  树状网络脆弱性示例

    Fig. 1.  Examples of tree network vulnerabilities.

    图 2  树状网络节点删除示例

    Fig. 2.  Example of node removal in a tree-like network.

    图 3  示例网络及圈矩阵 (a)示例网络拓扑结构; (b)圈矩阵及节点1圈比的计算过程

    Fig. 3.  Example network and cycle ratio matrix: (a) Example network topology; (b) cycle matrix and node 1 cycle ratio procedure.

    图 4  加权示例网络及加权圈比矩阵 (a)加权示例网络拓扑结构; (b)加权圈矩阵及节点1加权圈比计算过程

    Fig. 4.  Weighted example network and weighted cycle ratio matrix: (a) Weighted example network topology; (b) weighted cycle matrix and node 1 weighted cycle ratio calculation procedure.

    图 5  示例网络2拓扑结构

    Fig. 5.  Example network 2 topology.

    图 6  改进后的加权圈矩阵及节点1加权圈比的计算过程

    Fig. 6.  Improved weighted cycle matrix and calculation procedure for node 1 weighted cycle ratio.

    图 7  网络中节点重要性6个指标的平均相关性矩

    Fig. 7.  Average correlation moments for six indicators of node importance in the network.

    图 8  邮件网络节点排名可视图

    Fig. 8.  E-mail network node ranking viewable.

    图 9  海豚社交网络节点排名可视图

    Fig. 9.  Dolphin network node ranking viewable.

    图 10  6种节点重要性指标对6种真实网络节点移除的网络效率变化

    Fig. 10.  Changes in network efficiency of six node importance metrics for six real network node removals.

    图 11  不同时刻节点累积数量

    Fig. 11.  Cumulative number of nodes at different moments.

    图 12  不同时刻指标排名

    Fig. 12.  Ranking of indicators at different moments.

    图 A1  网络拓扑结构 (a) Dolphinq网络; (b) Email网络

    Fig. A1.  Network topology (a) Dolphinq network; (b) Email network.

    表 1  每个节点的基本圈以及其他指标的值

    Table 1.  Value of the base cycle for each node as well as other metrics.

    节点基本圈WCRWCR1CRNSBCCCEC
    1{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2, 5}2.723.763.921.9350.1010.158
    2{2, 3, 1}, {2, 4, 1}, {2, 5, 1}, {2, 4, 3}2.983.803.921.4725.750.1170.099
    3{3, 1, 4}, {3, 2, 4}, {3, 2, 1}, {3, 10, 11, 9}3.634.785.672.60220.1090.170
    4{4, 1, 2}, {4, 1, 3}, {4, 2, 3}1.902.332.501.472.250.1000.080
    5{5, 1, 2}1.321.571.502.13210.1050.143
    60000.6000.0510.031
    70002.07170.0700.092
    80000.5300.0530.027
    9{9, 11, 10, 3}2.1562.383.250.6080.0990.027
    10{9, 11, 10, 3}1.902.383.251.7300.0580.117
    11{9, 11, 10, 3}2.4733.251.2000.0740.055
    下载: 导出CSV

    表 2  6个真实网络的基本拓扑特征

    Table 2.  Six basic topological characteristics of real networks.

    节点 连边 平均度 同配性 平均聚类系数
    Usa 332 2.1 k 12 –0.20788 0.625
    Dolphin 291 3.2 k 21 0.177476 0.68233
    Email 906 12.1 k 26 –0.0878 0.6139
    Rw496 496 2 k 7 0.045056 0.395
    Road 1.2 k 1.4 k 2 0.126684 0.0167
    Advogato 5.2 k 47.3 k 18 –0.0834 0.2868
    下载: 导出CSV

    表 3  邮件网络部分节点排序

    Table 3.  Email network partial node ordering.


    排名
    指标
    CRWCRNSBCCCEC
    118741874187416695991874
    2125812581258187416691258
    34539999995991731999
    4999453158645318741963
    516691963196371318541586
    615861669157619522721576
    71963158619877023391987
    82031159112012583441792
    919871768179251114531120
    101159203166911591782465
    115111377419272741323
    1217681440144058592419
    13412511132315631081669
    141440198746519871361440
    ·····················
    n20292029202820292028984
    下载: 导出CSV

    表 4  海豚社交网络部分节点排序

    Table 4.  Dolphin network partial node ordering.


    排名
    指标
    CRWCRNSBCCCEC
    1202202438911843
    23211811879202118
    3118323232129232
    4185185173271173243
    517317320220217449
    64432321334185
    7271410717432107
    8222232243435202
    917410718522242173
    1043174493513332
    112012222047135164
    1223227116411821820
    13862014291222266
    144724386201243225
    ·····················
    n156156156285156274
    下载: 导出CSV

    表 5  不同指标下各网络的鲁棒性R

    Table 5.  The robustness of each network under different metrics R.

    NetworksCRWCRNSBCCCEC
    USAair0.07400.07380.10470.08170.25200.1147
    Dolphin0.38010.37130.42930.35770.37930.3889
    Email0.01730.01410.02050.01460.02870.1003
    Rw4960.21770.15480.2000.19190.25080.2150
    Road0.13410.10310.12210.09790.18380.3152
    Advogato0.27460.25750.28000.26320.7060.3006
    下载: 导出CSV

    表 6  各指标下的平均排名和R平均值

    Table 6.  Average ranking and R-mean under each indicator.

    CRWCRNSBCCCEC
    平均排名3.671.54.1671.674.675.3
    R平均值0.18300.16260.19280.16780.22750.2391
    下载: 导出CSV

    表 7  各指标下累积节点排名

    Table 7.  Cumulative node rankings under each indicator.

    t =1t = 2t = 4t = 6t = 8t = 10平均排名
    CR2.672. 832.832.672.672.672.72
    WCR1.671. 501.331.331.331.331.42
    NS3.504.004.504.504.504.504.25
    BC3.332.832.502.502.502.502.69
    CC4.674.674.674.834.834.834.75
    EC5.175.175.175.175.175.175.17
    下载: 导出CSV

    表 A1  Email和Advogato网络中CR与WCR指标下节点排名

    Table A1.  Ranking of nodes under CR and WCR metrics in E-mail and Advogato networks.


    排名
    Email Advogato
    CR WCR CR WCR
    1 1874 1874 157 157
    2 1258 1258 46 46
    3 453 999 597 597
    4 999 453 30 30
    5 1669 1963 232 126
    6 1586 1669 328 328
    7 1963 1586 126 232
    8 203 1159 438 438
    9 1987 1768 286 286
    10 1159 203 1223 610
    11 511 1377 610 1223
    12 1768 1440 429 62
    13 412 511 9 1378
    14 1440 1987 736 429
    15 1792 412 62 736
    16 1377 457 22 22
    17 457 1792 1378 780
    18 1706 1576 780 9
    19 585 1587 19 604
    20 1751 585 326 326
    21 1587 852 604 19
    22 1952 1144 194 175
    23 1144 1833 329 739
    24 852 1751 214 329
    25 1278 1323 739 214
    26 713 1278 1775 1992
    27 1277 1277 1992 172
    28 1576 1510 801 45
    29 155 155 172 719
    30 1287 1952 175 1775
    31 350 329 45 801
    32 1998 419 399 194
    33 1833 1287 719 584
    34 1550 1894 584 764
    ··· ··· ··· ··· ···
    n 2029 2029 6550 6550
    下载: 导出CSV
  • [1]

    Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175Google Scholar

    [2]

    Lü L, Chen D, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1Google Scholar

    [3]

    Yang M, Seklouli A S, Zhang H, Ren L, Yu X, Ouzrout Y 2023 Proceedings of the 2023 International Conference on Computer Applications Technology Guiyang, China, September 15-17, 2023 p97

    [4]

    Albert R, Albert I, Nakarado G L 2004 Phys. Rev. E 69 025103Google Scholar

    [5]

    Easley D, Kleinberg J 2010 IEEE Technol. Soc. Mag. 32 3

    [6]

    Freeman L C 1978 Soc. Networks 1 215Google Scholar

    [7]

    Bonacich P 1972 J. Math. Sociol. 2 113Google Scholar

    [8]

    Freeman L C 1977 Sociometry 40 35Google Scholar

    [9]

    刘臣, 李丹丹, 韩林, 安永雪 2019 计算机应用研究 1 4

    Liu C, Li D D, Han L, An Y X 2019 Appl. Res. Comput. 1 4

    [10]

    J Hu, B Wang, D Lee 2010 IEEE/ACM Int'l Conference on Green Computing and Communications & Int'l Conference on Cyber, Physical and Social Computing Hangzhou, China, December 18-20, 2010 p792

    [11]

    张格豪, 刘伟, 王睿鑫垚, 厉鑫鹏, 龚子忱, 陈一源, 陈海洋 2023 无线互联科技 6 116Google Scholar

    Zhang G H, Liu W, Wang R X Y, Li X P, Gong Z C, Chen Y Y, Chen H Y 2023 Wireless Int. Technol. 6 116Google Scholar

    [12]

    Lambiotte R, Rosvall M 2019 Nat. Phys. 15 313Google Scholar

    [13]

    Perera S, Bell M G, Bliemer M C 2017 Appl. Netw. Sci. 2 33Google Scholar

    [14]

    Battiston F, Cencetti G, Iacopini I, Latora V, Lucas M, Patania A, Young J G, Petri G 2020 Phys. Rep. 874 1Google Scholar

    [15]

    Song J, Wang Y, Xu G 2024 Comput. Netw. 220 108969

    [16]

    Shi D H, Lu L Y, Chen G R 2019 Natl. Sci. Rev. 6 962Google Scholar

    [17]

    Shi D H, Chen R, Thong W W K, Yan X Y 2013 IEEE Circuits Syst. Mag. 13 66Google Scholar

    [18]

    Lou Y, Wang L, Chen G 2018 IEEE Trans. Circuits Syst. I Regul. Pap. 65 983

    [19]

    Sizemore A E, Giusti C, Kahn A, Vettel J M, Betzel R F, Bassett D S 2017 J. Comput. Neurosci. 44 115

    [20]

    Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar

    [21]

    Fronczak A, Hołst J A, Jedynak M, Sienkiewicz J 2002 Physica A 316 688Google Scholar

    [22]

    Caldarelli G, Pastor-Satorras R, Vespignani A 2004 Eur. Phys. J. B 38 183Google Scholar

    [23]

    Kim H J, Kim J M 2005 Phys. Rev. E 72 036109Google Scholar

    [24]

    Fan T L, Lü L Y, Shi D H, Zhou T 2021 Commun. Phys. 4 272Google Scholar

    [25]

    Croft D P, James R, Krause J 2008 Exploring Animal Social Networks (Princeton: Princeton University Press)pp1-18

    [26]

    Cha M, Haddadi H, Benevenuto F, Gummadi K P 2010 Proceedings of the Fourth International AAAI Conference on Weblogs and Social Media Washington, DC, USA, May 23-26, 2010 p10

    [27]

    Guimerà R, Mossa S, Turtschi A, Amaral L A N 2005 Proc. Natl. Acad. Sci. U. S. A. 102 7794Google Scholar

    [28]

    Kossinets G, Watts D J 2006 Science 311 88Google Scholar

    [29]

    Yang H, Bell M G H 1998 Transp. Rev. 18 257Google Scholar

    [30]

    Lü J, Zhang B, Zhou T 2015 Physica A 418 65Google Scholar

    [31]

    Helander M, Kertész J 2021 EPJ Data Sci. 11 1Google Scholar

    [32]

    Noschese S, Reichel L 2024 Numer. Algor. 95 451Google Scholar

    [33]

    Zhang J, Liu X 2022 J. Comput. Sci. 60 101591Google Scholar

    [34]

    Kendall M 1938 Biometrika 30 81Google Scholar

    [35]

    Callaway D S, Newman M E J, Strogatz S H, Watts D J 2000 Phys. Rev. Lett. 85 5468Google Scholar

    [36]

    Cohen R, Erez K, Ben-Avraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682Google Scholar

    [37]

    田柳, 狄增如, 姚虹 2011 物理学报 60 028901Google Scholar

    Tian L, Di Z R, Yao H 2011 Acta Phys. Sin. 60 028901Google Scholar

    [38]

    Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A 2015 Rev. Mod. Phys. 87 925Google Scholar

    [39]

    Gubar E, Zhu Q, Taynitskiy V 2017 Proceedings of the 7th EAI International Conference on Game Theory for Networks Knoxville, Tennessee, USA, May 9, 2017 p108

    [40]

    Zhou F, Lü L Y, Mariani M S 2019 Commun. Nonlinear Sci. Numer. Simul. 74 69Google Scholar

  • [1] 邢梓涵, 刘丝语, 刘慧, 陈凌霄. 基于谱图理论的大规模复杂网络重要节点组挖掘算法. 物理学报, doi: 10.7498/aps.74.20250416
    [2] 侯诗雨, 刘影, 唐明. 融合节点动态传播特征与局域结构的复杂网络传播关键节点识别. 物理学报, doi: 10.7498/aps.74.20250179
    [3] 汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法. 物理学报, doi: 10.7498/aps.72.20221878
    [4] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, doi: 10.7498/aps.71.20220565
    [5] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, doi: 10.7498/aps.67.20172295
    [6] 苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, doi: 10.7498/aps.66.120201
    [7] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, doi: 10.7498/aps.66.038902
    [8] 韩忠明, 陈炎, 李梦琪, 刘雯, 杨伟杰. 一种有效的基于三角结构的复杂网络节点影响力度量模型. 物理学报, doi: 10.7498/aps.65.168901
    [9] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. 物理学报, doi: 10.7498/aps.64.058902
    [10] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, doi: 10.7498/aps.62.178901
    [11] 任卓明, 刘建国, 邵凤, 胡兆龙, 郭强. 复杂网络中最小K-核节点的传播能力分析. 物理学报, doi: 10.7498/aps.62.108902
    [12] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, doi: 10.7498/aps.62.020204
    [13] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, doi: 10.7498/aps.62.040503
    [14] 吕天阳, 谢文艳, 郑纬民, 朴秀峰. 加权复杂网络社团的评价指标及其发现算法分析. 物理学报, doi: 10.7498/aps.61.210511
    [15] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, doi: 10.7498/aps.61.190201
    [16] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, doi: 10.7498/aps.61.090504
    [17] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, doi: 10.7498/aps.61.050201
    [18] 陈华良, 刘忠信, 陈增强, 袁著祉. 复杂网络的一种加权路由策略研究. 物理学报, doi: 10.7498/aps.58.6068
    [19] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, doi: 10.7498/aps.58.1462
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  350
  • PDF下载量:  6
  • 被引次数: 0
出版历程
  • 收稿日期:  2025-03-14
  • 修回日期:  2025-04-14
  • 上网日期:  2025-05-13

/

返回文章
返回