-
圈比作为一种基于圈结构的量化指标, 已在无权无向网络中展现出其在识别关键节点方面的显著优势. 传统的圈比未能充分考虑边权信息对网络结构的影响, 限制了其在更广泛网络分析中的应用. 为了解决这一问题, 本文提出了一种加权网络中新的网络分析指标——加权圈比, 旨在提升识别加权网络中关键节点的准确性. 通过对示例网络的分析, 验证了加权圈比的可行性; 进一步的实验在多个真实世界的网络中表明, 加权圈比不仅与现有的基准指标存在显著差异, 而且在评估网络连通性及早期传播覆盖范围方面, 总体表现优于包括传统圈比在内的其他基准指标. 这些发现强调了加权圈比在网络分析中的潜在价值, 尤其是在处理加权网络时的有效性 .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.
-
Keywords:
- complex network /
- cycle ratio /
- weighted cycle ratio /
- vital node
[1] Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175
Google Scholar
[2] Lü L, Chen D, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1
Google 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 025103
Google Scholar
[5] Easley D, Kleinberg J 2010 IEEE Technol. Soc. Mag. 32 3
[6] Freeman L C 1978 Soc. Networks 1 215
Google Scholar
[7] Bonacich P 1972 J. Math. Sociol. 2 113
Google Scholar
[8] Freeman L C 1977 Sociometry 40 35
Google 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 116
Google 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 116
Google Scholar
[12] Lambiotte R, Rosvall M 2019 Nat. Phys. 15 313
Google Scholar
[13] Perera S, Bell M G, Bliemer M C 2017 Appl. Netw. Sci. 2 33
Google Scholar
[14] Battiston F, Cencetti G, Iacopini I, Latora V, Lucas M, Patania A, Young J G, Petri G 2020 Phys. Rep. 874 1
Google 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 962
Google Scholar
[17] Shi D H, Chen R, Thong W W K, Yan X Y 2013 IEEE Circuits Syst. Mag. 13 66
Google 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 440
Google Scholar
[21] Fronczak A, Hołst J A, Jedynak M, Sienkiewicz J 2002 Physica A 316 688
Google Scholar
[22] Caldarelli G, Pastor-Satorras R, Vespignani A 2004 Eur. Phys. J. B 38 183
Google Scholar
[23] Kim H J, Kim J M 2005 Phys. Rev. E 72 036109
Google Scholar
[24] Fan T L, Lü L Y, Shi D H, Zhou T 2021 Commun. Phys. 4 272
Google 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 7794
Google Scholar
[28] Kossinets G, Watts D J 2006 Science 311 88
Google Scholar
[29] Yang H, Bell M G H 1998 Transp. Rev. 18 257
Google Scholar
[30] Lü J, Zhang B, Zhou T 2015 Physica A 418 65
Google Scholar
[31] Helander M, Kertész J 2021 EPJ Data Sci. 11 1
Google Scholar
[32] Noschese S, Reichel L 2024 Numer. Algor. 95 451
Google Scholar
[33] Zhang J, Liu X 2022 J. Comput. Sci. 60 101591
Google Scholar
[34] Kendall M 1938 Biometrika 30 81
Google Scholar
[35] Callaway D S, Newman M E J, Strogatz S H, Watts D J 2000 Phys. Rev. Lett. 85 5468
Google Scholar
[36] Cohen R, Erez K, Ben-Avraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682
Google Scholar
[37] 田柳, 狄增如, 姚虹 2011 60 028901
Google Scholar
Tian L, Di Z R, Yao H 2011 Acta Phys. Sin. 60 028901
Google Scholar
[38] Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A 2015 Rev. Mod. Phys. 87 925
Google 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 69
Google Scholar
-
图 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.
图 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.
图 10 6种节点重要性指标对6种真实网络节点移除的网络效率变化
Fig. 10. Changes in network efficiency of six node importance metrics for six real network node removals.
图 A1 网络拓扑结构 (a) Dolphinq网络; (b) E-mail网络
Fig. A1. Network topology (a) Dolphinq network; (b) E-mail network.
表 1 每个节点的基本圈以及其他指标的值
Table 1. Value of the base cycle for each node as well as other metrics.
节点 基本圈 WCR WCR1 CR NS BC CC EC 1 {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2, 5} 2.72 3.76 3.92 1.93 5 0.101 0.158 2 {2, 3, 1}, {2, 4, 1}, {2, 5, 1}, {2, 4, 3} 2.98 3.80 3.92 1.47 25.75 0.117 0.099 3 {3, 1, 4}, {3, 2, 4}, {3, 2, 1}, {3, 10, 11, 9} 3.63 4.78 5.67 2.60 22 0.109 0.170 4 {4, 1, 2}, {4, 1, 3}, {4, 2, 3} 1.90 2.33 2.50 1.47 2.25 0.100 0.080 5 {5, 1, 2} 1.32 1.57 1.50 2.13 21 0.105 0.143 6 0 0 0 0.60 0 0.051 0.031 7 0 0 0 2.07 17 0.070 0.092 8 0 0 0 0.53 0 0.053 0.027 9 {9, 11, 10, 3} 2.156 2.38 3.25 0.60 8 0.099 0.027 10 {9, 11, 10, 3} 1.90 2.38 3.25 1.73 0 0.058 0.117 11 {9, 11, 10, 3} 2.47 3 3.25 1.20 0 0.074 0.055 
下载: 导出CSV
表 2 6个真实网络的基本拓扑特征
Table 2. Six basic topological characteristics of real networks.
节点 连边 平均度 同配性 平均聚类系数 Usa 332 2.1k 12 –0.20788 0.625 Dolphin 291 3.2k 21 0.177476 0.68233 Email 906 12.1k 26 –0.0878 0.6139 Rw496 496 2k 7 0.045056 0.395 Road 1.2k 1.4k 2 0.126684 0.0167 Advogato 5.2k 47.3k 18 –0.0834 0.2868
下载: 导出CSV
表 3 邮件网络部分节点排序
Table 3. Email network partial node ordering.
排名指标 CR WCR NS BC CC EC 1 1874 1874 1874 1669 599 1874 2 1258 1258 1258 1874 1669 1258 3 453 999 999 599 1731 999 4 999 453 1586 453 1874 1963 5 1669 1963 1963 713 1854 1586 6 1586 1669 1576 1952 272 1576 7 1963 1586 1987 702 339 1987 8 203 1159 1120 1258 344 1792 9 1987 1768 1792 511 1453 1120 10 1159 203 1669 1159 1782 465 11 511 1377 419 272 74 1323 12 1768 1440 1440 585 92 419 13 412 511 1323 1563 108 1669 14 1440 1987 465 1987 136 1440 ··· ··· ··· ··· ··· ··· ··· n 2029 2029 2028 2029 2028 984
下载: 导出CSV
表 4 海豚社交网络部分节点排序
Table 4. Dolphin network partial node ordering.
排名指标 CR WCR NS BC CC EC 1 202 202 43 89 118 43 2 32 118 118 79 202 118 3 118 32 32 32 129 232 4 185 185 173 271 173 243 5 173 173 202 202 174 49 6 4 43 232 133 4 185 7 271 4 107 174 32 107 8 222 232 243 4 35 202 9 174 107 185 222 42 173 10 43 174 49 35 133 32 11 201 222 20 47 135 164 12 232 271 164 118 218 20 13 86 201 4 291 222 266 14 47 243 86 201 243 225 ··· ··· ··· ··· ··· ··· ··· n 156 156 156 285 156 274
下载: 导出CSV
表 5 不同指标下各网络的鲁棒性R
Table 5. The robustness of each network under different metrics R
Networks CR WCR NS BC CC EC USAair 0.0740 0.0738 0.1047 0.0817 0.2520 0.1147 Dolphin 0.3801 0.3713 0.4293 0.3577 0.3793 0.3889 Email 0.0173 0.0141 0.0205 0.0146 0.0287 0.1003 Rw496 0.2177 0.1548 0.200 0.1919 0.2508 0.2150 Road 0.1341 0.1031 0.1221 0.0979 0.1838 0.3152 Advogato 0.2746 0.2575 0.2800 0.2632 0.706 0.3006
下载: 导出CSV
表 6 各指标下的平均排名和R平均值
Table 6. Average ranking and R-mean under each indicator.
CR WCR NS BC CC EC 平均排名 3.67 1.5 4.167 1.67 4.67 5.3 R平均值 0.1830 0.1626 0.1928 0.1678 0.2275 0.2391
下载: 导出CSV
表 7 各指标下累积节点排名
Table 7. Cumulative node rankings under each indicator.
t =1 t = 2 t = 4 t = 6 t = 8 t = 10 平均排名 CR 2.67 2. 83 2.83 2.67 2.67 2.67 2.72 WCR 1.67 1. 50 1.33 1.33 1.33 1.33 1.42 NS 3.50 4.00 4.50 4.50 4.50 4.50 4.25 BC 3.33 2.83 2.50 2.50 2.50 2.50 2.69 CC 4.67 4.67 4.67 4.83 4.83 4.83 4.75 EC 5.17 5.17 5.17 5.17 5.17 5.17 5.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 175
Google Scholar
[2] Lü L, Chen D, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1
Google 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 025103
Google Scholar
[5] Easley D, Kleinberg J 2010 IEEE Technol. Soc. Mag. 32 3
[6] Freeman L C 1978 Soc. Networks 1 215
Google Scholar
[7] Bonacich P 1972 J. Math. Sociol. 2 113
Google Scholar
[8] Freeman L C 1977 Sociometry 40 35
Google 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 116
Google 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 116
Google Scholar
[12] Lambiotte R, Rosvall M 2019 Nat. Phys. 15 313
Google Scholar
[13] Perera S, Bell M G, Bliemer M C 2017 Appl. Netw. Sci. 2 33
Google Scholar
[14] Battiston F, Cencetti G, Iacopini I, Latora V, Lucas M, Patania A, Young J G, Petri G 2020 Phys. Rep. 874 1
Google 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 962
Google Scholar
[17] Shi D H, Chen R, Thong W W K, Yan X Y 2013 IEEE Circuits Syst. Mag. 13 66
Google 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 440
Google Scholar
[21] Fronczak A, Hołst J A, Jedynak M, Sienkiewicz J 2002 Physica A 316 688
Google Scholar
[22] Caldarelli G, Pastor-Satorras R, Vespignani A 2004 Eur. Phys. J. B 38 183
Google Scholar
[23] Kim H J, Kim J M 2005 Phys. Rev. E 72 036109
Google Scholar
[24] Fan T L, Lü L Y, Shi D H, Zhou T 2021 Commun. Phys. 4 272
Google 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 7794
Google Scholar
[28] Kossinets G, Watts D J 2006 Science 311 88
Google Scholar
[29] Yang H, Bell M G H 1998 Transp. Rev. 18 257
Google Scholar
[30] Lü J, Zhang B, Zhou T 2015 Physica A 418 65
Google Scholar
[31] Helander M, Kertész J 2021 EPJ Data Sci. 11 1
Google Scholar
[32] Noschese S, Reichel L 2024 Numer. Algor. 95 451
Google Scholar
[33] Zhang J, Liu X 2022 J. Comput. Sci. 60 101591
Google Scholar
[34] Kendall M 1938 Biometrika 30 81
Google Scholar
[35] Callaway D S, Newman M E J, Strogatz S H, Watts D J 2000 Phys. Rev. Lett. 85 5468
Google Scholar
[36] Cohen R, Erez K, Ben-Avraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682
Google Scholar
[37] 田柳, 狄增如, 姚虹 2011 60 028901
Google Scholar
Tian L, Di Z R, Yao H 2011 Acta Phys. Sin. 60 028901
Google Scholar
[38] Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A 2015 Rev. Mod. Phys. 87 925
Google 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 69
Google Scholar
下载:
计量
- 文章访问数: 701
- PDF下载量: 18
- 被引次数: 0
