Computer Science ›› 2021, Vol. 48 ›› Issue (7): 130-136.doi: 10.11896/jsjkx.201000108

• Database & Big Data & Data Science • Previous Articles     Next Articles

Robustness Analysis of Complex Network Based on Rewiring Mechanism

MU Jun-fang1,2, ZHENG Wen-ping1,2, WANG Jie3, LIANG Ji-ye1,2   

  1. 1 School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
    2 Key Laboratory of Computation Intelligence and Chinese Information Processing,Shanxi University,Taiyuan 030006,China
    3 College of Information,Shanxi University of Finance and Economics,Taiyuan 030006,China
  • Received:2020-10-19 Revised:2021-04-09 Online:2021-07-15 Published:2021-07-02
  • About author:MU Jun-fang,born in 1991,candidate Ph.D,is a member of China Computer Federation.Her main research interests include complex network and bioinformatics,etc.(
    ZHENG Wen-ping,born in 1979,Ph.D,associate professor,Ph.D supervisor,is a member of China Computer Federation.Her main research interests include network science and bioinforma-tics,etc.
  • Supported by:
    National Natural Science Foundation of China (62072292,62006145),Projects of Key Research and Development Plan of Shanxi Province (201903D121162),Natural Science Foundation of Shanxi Province(201801D121123),Shanxi Scholarship Council of China(2017-014) and 1331 Engineering Project of Shanxi Province,China.

Abstract: With the widespread use of infrastructure networks such as power systems,transportation systems,and communication systems,it is of great significance to improve the robustness of complex networks.The rewiring mechanism is an efficient and simple method to improve the robustness of the network.The rewiring mechanism based on the 0-order null model improves the robustness of the network by randomly deleting and creating edges.Although the number of edges is maintained,the degree of nodes will change,such as the RM-ES algorithm.The rewiring mechanism based on the 1-order null model improves the robustness of the network by randomly selecting two edges for rewiring,although the degree distribution is maintained,it is difficult to find the appropriate nodes by random edge selection,which increases the running time of algorithms,such as the RM-LCC algorithm.Therefore,in order to maintain the degree distribution and improve the robustness of the network,this paper proposes a fast rewiring mechanism based on 1-order null model,called FRM.The FRM algorithm first weights the edges by degree for each edge,then selects two edges with the probability proportional to the weight of edge,finally,creates the edges between nodes with similar degree.We compare the FRM algorithm with other methods on real network data sets.The experimental results of three real network data show that FRM algorithm performs better than four representative rewiring algorithms under the attack of degree centrality,betweenness centrality and PageRank centrality with respect to the ratio of nodes in largest connected component s(Q),robustness index R and robustness index I(G).

Key words: Complex network, Largest connected component, Rewiring mechanism, Robustness, Shannon entropy

CLC Number: 

  • TP181
[1]BOCCALETTIA S,LATORAB V,MORENOD Y,et al.Com-plex networks:structure and dynamics[J].Physics Reports,2006,424(4/5):175-308.
[2]NEWMAN M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.
[3]YANG D,LIAO X,SHEN H,et al.Dynamic node immunization for restraint of harmful information diffusion in social networks[J].Physica A:Statistical Mechanics and its Applications,2018,503(1):640-649.
[4]ARENAS A,ALBERT D G,KURTHS J,et al.Synchronization in complex networks[J].Physics Reports,2008,469(3):93-153.
[5]WANG J,LIANG J Y,ZHENG W P,et al.A graph clustering method for detecting protein complexes[J].Journal of Compu-ter Research and Development,2015,52(8):1784-1793.
[6]ZHENG W P,CHE C H,QIAN Y H,et al.A graph clustering algorithm based on paths between nodes in complex networks[J].Chinese Journal of Computer,2018,492(15):1958-1966.
[7]WANG Z Q,LIANG J Y,LI R,et al.An approach to cold-start link prediction:Establishing connections between non-topological and topological information[J].IEEE Transaction on Knowledge and Data Engineering,2016,28:2857-2870.
[8]LIU Z H.Dynamics on complex networks[J].Scientia SinicaPhysica,Mechanica & Astronomica,2020(50):010501.
[9]NEWMAN M E J.Networks:An Introduction[M].Oxford Unversity Press,2010.
[10]WANG X F,LI X,CHENG G R.Network science:An introduction[M].Higher Education Press,2012.
[11]SAFAEI F,YEGANLOO H,AKBAR R.Robustness on topo-logy reconfiguration of complex networks:An entropic approach[J].Mathematics and Computers in Simulation,2020(170):379-409.
[12]HERRMANN H J,SCHNEIDER C M,MOREIRA A A,et al.Onion-like network topology enhances robustness against malicious attacks[J].Journal of Statistical Mechanics:Theory and Experiment,2011(2011):01027.
[13]SCHNEIDER C M,MOREIRA A A,ANDRADE J S,et al.Miti-gation of malicious attacks on networks[J].Proceedings of the National Academy of Sciences,2011(108):3838-3841.
[14]LOUZADA V H P,DAOLIO F,HANS J,et al.Smart rewiring for network robustness[J].IO:Theory eJournal,2013(1):150-159.
[15]BAI L,XIAO Y D,HOU L L,et al.Smart rewiring:Improving network robustness faster[J].Chinese Physics Letters,2015(32):078901.
[16]MIEGHEM P V,WANG H,GE X S,et al.Influence of assortativity and degree-preserving rewiring on the spectra of networks [J].The European Physical Journal B,2010(76):643-652.
[17]ROSSI R A,AHMED N K.The network data repository with interactive graph analytics and visualization[C]//Twenty-Ninth AAAI Conference on Artificial Intelligence.AAAI Press,2015:4292-4293.
[18]JEONG H,MASON S P,BARABASI A L,et al.Oltvai,Lethality and centrality in protein networks[J].Nature,2001(411):41-42.
[19]JOY M P,BROCK A L,INGBER D E,et al.High-betweenness proteins in the yeast protein interaction network[J].Journal of Biomedicine and Biotechnology,2005(2):96-103.
[20]BONACICH P.Power and Centrality:A family of measures[J].American Journal of Sociology,1987 (92):1170-1182.
[1] ZHENG Wen-ping, LIU Mei-lin, YANG Gui. Community Detection Algorithm Based on Node Stability and Neighbor Similarity [J]. Computer Science, 2022, 49(9): 83-91.
[2] ZHOU Hui, SHI Hao-chen, TU Yao-feng, HUANG Sheng-jun. Robust Deep Neural Network Learning Based on Active Sampling [J]. Computer Science, 2022, 49(7): 164-169.
[3] YAN Meng, LIN Ying, NIE Zhi-shen, CAO Yi-fan, PI Huan, ZHANG Lan. Training Method to Improve Robustness of Federated Learning [J]. Computer Science, 2022, 49(6A): 496-501.
[4] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[5] YANG Bo, LI Yuan-biao. Complex Network Analysis on Curriculum System of Data Science and Big Data Technology [J]. Computer Science, 2022, 49(6A): 680-685.
[6] WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen. Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning [J]. Computer Science, 2022, 49(5): 170-178.
[7] CHEN Shi-cong, YUAN De-yu, HUANG Shu-hua, YANG Ming. Node Label Classification Algorithm Based on Structural Depth Network Embedding Model [J]. Computer Science, 2022, 49(3): 105-112.
[8] ZHAO Xue-lei, JI Xin-sheng, LIU Shu-xin, LI Ying-le, LI Hai-tao. Link Prediction Method for Directed Networks Based on Path Connection Strength [J]. Computer Science, 2022, 49(2): 216-222.
[9] ZHANG Cheng-rui, CHEN Jun-jie, GUO Hao. Comparative Analysis of Robustness of Resting Human Brain Functional Hypernetwork Model [J]. Computer Science, 2022, 49(2): 241-247.
[10] LI Jia-wen, GUO Bing-hui, YANG Xiao-bo, ZHENG Zhi-ming. Disease Genes Recognition Based on Information Propagation [J]. Computer Science, 2022, 49(1): 264-270.
[11] HU Jun, WANG Yu-tong, HE Xin-wei, WU Hui-dong, LI Hui-jia. Analysis and Application of Global Aviation Network Structure Based on Complex Network [J]. Computer Science, 2021, 48(6A): 321-325.
[12] 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.
[13] MA Yuan-yuan, HAN Hua, QU Qian-qian. Importance Evaluation Algorithm Based on Node Intimate Degree [J]. Computer Science, 2021, 48(5): 140-146.
[14] YIN Zi-qiao, GUO Bing-hui, MA Shuang-ge, MI Zhi-long, SUN Yi-fan, ZHENG Zhi-ming. Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network [J]. Computer Science, 2021, 48(5): 184-189.
[15] LIU Sheng-jiu, LI Tian-rui, XIE Peng, LIU Jia. Measure for Multi-fractals of Weighted Graphs [J]. Computer Science, 2021, 48(3): 136-143.
Full text



No Suggested Reading articles found!