复杂网络上的非线性负载容量模型

doi:10.11896/jsjkx.200700040

计算机科学 ›› 2021, Vol. 48 ›› Issue (6): 282-287.doi: 10.11896/jsjkx.200700040

复杂网络上的非线性负载容量模型

王学光¹, 张爱新², 窦炳琳²

1 华东政法大学信息科学技术系上海200052
2 上海交通大学网络空间安全学院上海200240

收稿日期:2020-07-08 修回日期:2020-08-19 出版日期:2021-06-15 发布日期:2021-06-03
通讯作者: 王学光(wangxueguang@ecupl.edu.cn)
基金资助:
国家重点研发计划(2017YFB0802103)

Non-linear Load Capacity Model of Complex Networks

WANG Xue-guang¹, ZHANG Ai-xin², DOU Bing-lin²

1 Department of Information Science and Technology,East China University of Political Science and Law,Shanghai 200052,China
2 School of Cyber Science and Engineering,Shanghai Jiao Tong University,Shanghai 200240,China

Received:2020-07-08 Revised:2020-08-19 Online:2021-06-15 Published:2021-06-03
About author:WANG Xue-guang,born in 1975,Ph.D,professor,is a member of China Computer Federation.His main research interests include computer networks,big data application and electronic data.
Supported by:
National Key R&D Program of China (2017YFB0802103).

摘要/Abstract

摘要： 对网络的形成机制、几何性质、演化规律以及网络结构分析、行为预测和控制的研究产生了复杂网络学科,其中关于复杂网络级联失效过程的研究一直受到研究人员的关注。文中提出一种更符合实际网络的两变量非线性负载容量模型来解决复杂网络的级联失效问题。通过在4个不同的网络上进行仿真,验证了所提模型的有效性,发现该模型能够更好地抵御级联失效。实验还发现,所提模型在获得较高鲁棒性的情况下具有更好的性能,且投资成本较小。

关键词: 度关联, 非线性模型, 复杂网络, 级联失效, 鲁棒性

Abstract: The study of network formation mechanism,geometric property,evolution rules,network structure analysis,behavior prediction and control gives rise to the discipline of complex network,and cascade failure process of complex network has always been concerned.This paper presents a non-linear load capacity model with two variable parameters,which is more suitable for real network,to solve the cascading failures problem of complex networks.Simulations on four different networks verify the effectiveness of the proposed model.The results show that the model can better defend against cascading failures,and has a lower investment cost and a better performance in the case of higher robustness.

Key words: Cascading failures, Complex networks, Degree correlation, Non-linear model, Robustness

中图分类号:

TP393

王学光, 张爱新, 窦炳琳. 复杂网络上的非线性负载容量模型[J]. 计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040

WANG Xue-guang, ZHANG Ai-xin, DOU Bing-lin. Non-linear Load Capacity Model of Complex Networks[J]. Computer Science, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040

参考文献

[1]WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393(6684):440-442.
[2]BARABÁSI A L,ALBERT R.Emergence of scaling in random networks [J].Science,1999,286(5439):509-512.
[3]CHEN C.Connectivity in Complex Networks:Measures,Infe-rence and Optimization[C]//The Eleventh ACM International Conference on Web Search and Data Mining.2018:747-748.
[4]KATCHAGUY A,SUCHETA S.Measuring the sampling ro-bustness of complex networks[C]//The 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.2019:294-301.
[5]TANMOY C,NOSEONG P,AYUSH A,et al.Ensemble Detection and Analysis of Communities in Complex Networks[J].ACM/IMS Transactions on Data Science,2020,1(1):1-34.
[6]ARTUR K,KAMIL B,PIOTR B,et al.Influencing information spreading processes in complex networks with probability spraying[C]//The 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.2018:1038-1046.
[7]ISAAC K,AFROZA S,FRANCESCO S.Locally Optimal Control of Complex Networks [J].Physical Review Letters,2017,119(26):268301.
[8]TYLOO M,COLETTA T,JACQUOD P.Robustness of Synchrony in Complex Networks and Generalized Kirchhoff Indices [J].Physical Review Letters,2018,120(8):084101.
[9]TONG T,JIANG Y,ZHOU Y,et al.Mitigation Strategy for the Cascading Failure of Complex Networks Based on Node Capacity Control Function [J].IEEE Access,2019,7:184743-184758.
[10]KOLLI N,NARAYANASWAMY B.Influence MaximizationFrom Cascade Information Traces in Complex Networks in the Absence of Network Structure [J].IEEE Transactions on Computational Social Systems,2019,6(6):1147-1155.
[11]VEGA C J,SANCHEZ E N,CHEN G.Trajectory Tracking on Complex Networks With Non-Identical Chaotic Nodes via Inverse Optimal Pinning Control [J].IEEE Control Systems Letters,2018,2(4):635-640.
[12]SHANG Y.Subgraph Robustness of Complex Networks Under Attacks [J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2019,49(4):821-832.
[13]DADLANI A,KUMAR M S,MURUGAN S,et al.System Dynamics of a Refined Epidemic Model for Infection Propagation Over Complex Networks [J].IEEE Systems Journal,2016,10(4):1316-1325.
[14]CHEN G,LOU Y,WANG L.A Comparative Study on Control-lability Robustness of Complex Networks [J].IEEE Transactions on Circuits and Systems II:Express Briefs,2019,66(5):828-832.
[15]KLICKSTEIN I,SORRENTINO F.Control Distance and Energy Scaling of Complex Networks [J].IEEE Transactions on Network Science and Engineering,2020,7(2):726-736.
[16]PIZZUTI C,SOCIEVOLE A.A Genetic Algorithm for Impro-ving Robustness of Complex Networks[C]//2018 IEEE 30th International Conference on Tools with Artificial Intelligence(ICTAI).2018:514-521.
[17]YAMASHITA K,NAKAMURA R,OHSAKI H.A Study on Robustness of Complex Networks Against Random Node Removals[C]//2018 IEEE 42nd Annual Computer Software and Applications Conference(COMPSAC).2018:966-969.
[18]BOCCALETTI S,LATORA V,MORENO Y,et al.Complex networks:Structure and dynamics [J].Physics Reports,2006,424(4):175-308.
[19]MOTTER A E,LAI Y C.Cascade-based attacks on complex networks [J].Physical Review E,2002,66(6):065102(4).
[20]XIANG L Y,CHEN Z Q,LIU Z X,et al.A review of modeling,Analysis and Control of Complex Dynamic Networks [J].Progress in natural science,2006,16(12):1543-1551.
[21]GOH K I,KAHNG B,KIM D.Universal behavior of load distribution in scale-free networks [J].Physical Review Letters,2001,87(27):278701(4).
[22]ERDÖS P,RÉNYI A.On the evolution of random graphs [J].Publications of the Mathematical Institute of the Hungarian Academy of Sciences,1960,5:17-60.
[23]CAID A.The AS Relationships Dataset [EB/OL].(2020-07-05).http://www.caida.org/data/active/as-relationships/.
[24]NEWMAN M E J.Assortative mixing in networks [J].Physical Review Letters,2002,89(20):208701(4).
[25]NEWMAN M E J.Mixing patterns in networks [J].Physical Review E,2003,67(2):26126(13).
[26]NOH J D.Percolation transition in networks with degree-degree correlation [J].Physical Review E,2007,76(2):26116(7).
[27]PAYNE J L,DODDS P S,EPPSTEIN M J.Information cascades on degree-correlated random networks [J].Physical Review E,2009,80(2):26125(7).
[28]SUN J T,WANG S J,HUANG Z G,et al.Effect of degree correlations on networked traffic dynamics [J].Physica A,2009,388(15):3244-3248.

相关文章 15

[1]	郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2]	周慧, 施皓晨, 屠要峰, 黄圣君. 基于主动采样的深度鲁棒神经网络学习 Robust Deep Neural Network Learning Based on Active Sampling 计算机科学, 2022, 49(7): 164-169. https://doi.org/10.11896/jsjkx.210600044
[3]	杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[4]	闫萌, 林英, 聂志深, 曹一凡, 皮欢, 张兰. 一种提高联邦学习模型鲁棒性的训练方法 Training Method to Improve Robustness of Federated Learning 计算机科学, 2022, 49(6A): 496-501. https://doi.org/10.11896/jsjkx.210400298
[5]	何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[6]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[7]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[8]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[9]	张程瑞, 陈俊杰, 郭浩. 静息态人脑功能超网络模型鲁棒性对比分析 Comparative Analysis of Robustness of Resting Human Brain Functional Hypernetwork Model 计算机科学, 2022, 49(2): 241-247. https://doi.org/10.11896/jsjkx.201200067
[10]	李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[11]	穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[12]	胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉. 基于复杂网络的全球航空网络结构分析与应用 Analysis and Application of Global Aviation Network Structure Based on Complex Network 计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[13]	马媛媛, 韩华, 瞿倩倩. 基于节点亲密度的重要性评估算法 Importance Evaluation Algorithm Based on Node Intimate Degree 计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184
[14]	殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明. 群智体系网络结构的自治调节:从生物调控网络结构谈起 Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network 计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161
[15]	刘胜久, 李天瑞, 谢鹏, 刘佳. 带权图的多重分形度量 Measure for Multi-fractals of Weighted Graphs 计算机科学, 2021, 48(3): 136-143. https://doi.org/10.11896/jsjkx.200700159

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

复杂网络上的非线性负载容量模型

Non-linear Load Capacity Model of Complex Networks

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0