علوم رایانش و فناوری اطلاعات

بازپیکربندی توپولوژی مبتنی بر انتروپی برای بهبود استحکام شبکه های پیچیده در برابر خرابی های تصادفی و حملات هدفمند

نویسندگان

دانشکده مهندسی و علوم کامپیوتر، دانشگاه شهید بهشتی، تهران، ایران

چکیده

یکی از راه بردهای دفاعی جهت افزایش تاب آوری در شبکه های تحت حمله، مکانیزم سیم بندی مجدد است که در آن گرههای آسیب دیده، اتصال خویش را از گرههای معیوب قطع کرده و با یک احتمال مشخص به گرههای مناسب دیگری متصل می شوند. در این مقاله، یک روش سیم بندی مجدد مبتنی بر مفهوم انتروپی شانون  برای اصلاح پیکربندی شبکههای پیچیده و به منظور افزایش و بهبود       تابآوری آن ها پیشنهاد گردیده است. استحکام شبکه براساس طیف توزیع درجه، ناهمگنی و نیز متوسط اندازه‌ی بزرگترین خوشه‌ی همبند در حین حذف گره ها با دنباله ای از حملات نظام مند به مرکزیت های درجه، بینیت و نزدیکی دانگالچو  مورد ارزیابی و سنجش قرار داده شده است. رویکرد سیم بندی مجدد پیشنهادی به شش شبکه ساختگی و نیز شش شبکه‌ٔ دنیای واقعی اِعمال گردیده و نشان داده شده است که از طریق حدوداً 30% جابه جاییِ پیوندها می توان به بهبود چشمگیری در استحکام و تابآوری کلی شبکهها دست یافت.

کلیدواژه‌ها

  • [1] S. H. Strogatz, Exploring complex networks, Nature, 410 (2001) 268-276.
  • [2] N. Basov, J.-S. Lee, A. Antoniuk, Social Networks and Construction of Culture: A Socio-Semantic Analysis of Art Groups, International Workshop on Complex Networks and their Applications (2016) 785-796.
  • [3] L. D. F. Costa, F. A. Rodrigues, A. S. Cristino, Complex networks: the key to systems biology, Genetics and Molecular Biology, 31(3) (2008) 591-601.
  • [4] F. Safaei and H. Sotoodeh, On the probability of facing random breakdowns: a measure of networks" vulnerability, Int. J. Comput. Math., 93 (7) (2016) 1045-1073.
  • [5] J. P. G. Sterbenz et al., Resilience and Survivability in Communication Networks: Strategies, Principles, and Survey of Disciplines, Computer Networks, Special Issue on Resilient and Survivable Networks, 54 (8) (2010) 1245–1265.
  • [6] Z. Jiang, M. Liang, D. Guo, Enhancing network performance by edge addition, Int. J. Mod, Phys. C, 22 (2011) 1211–1226.
  • [7] A. N. Zeng and W. Liu, Enhancing network robustness against malicious attacks, Physical Review E 85.6, 85 (2012) 066130.
  • [8] T. P. Peixoto and S. Bornholdt, Evolution of robust network topologies: emergence of central backbones, Phys. Rev. Lett., 109 (2012) 118703.
  • [9] H. Wang and P.V. Mieghem, Algebraic connectivity optimization via link addition, Proceedings of IEEE/ACM Bionetics, (2008) 25- 28, Hyogo, Japan.
  • [10] H. Chan and L. Akoglu, Optimizing Network Robustness by Edge Rewiring: A General Framework, Data Mining and Knowledge Discovery, 30 (5) (2016) 1395-1425.
  • [11] T.S. Evans, Exact Solutions for Network Rewiring Models, The European Physical Journal B, 56 (1) (2007) 65-69.
  • [12] H. J. Herrmann et al., Onion-like network topology enhances robustness against malicious attacks, Journal of Statistical Mechanics: Theory and Experiment, 2011 (01) (2011) P01027.
  • [13] J. Lindquist et al., Network evolution by different rewiring schemes, Physica D, 238 (2009) 370-378.
  • [14] C. M. Scheneider et al., Mitigation of malicious attacks on networks, PNAS, 108 (10) (2011) 3838-3841.
  • [15] A. Sydney, C. Scoglio, D. Gruenbacher, Optimizing algebraic connectivity by edge rewiring, Applied Mathematics and Computation, 219 (2013) 5465-5479.
  • [16] B. Liang, Smart Rewiring Improving Network Robustness Faster, Chinese Physics Letters, 32 (7) (2015) 078901.
  • [17] J. A. Bondy and U. S. R Murty, Graph theory: Graduate texts in mathematics, Springer-Verlag, 2008.
  • [18] R. Diestel, Graph Theory, Graduate Texts in Mathematics, Vol. 173, 4th ed., Springer-Verlag, 2010.
  • [19] P. Erdös and A. Rényi, On the Evolution of Random Graphs, Publications of the Math. Inst. of the Hungarian Academy of Sci., 5 (1960) 17-61.
  • [20] A- L. Barabási and R. Albert, Emergence of Scaling in Random Networks, Science, 286 (5439) (1999) 509-512.
  • [21] D. J. Watts and S. H. Strogatz, Collective dynamics of small-world networks, Nature, 393 (6684) (1998) 440-442.
  • [22] J. S. Andrade et al., Apollonian networks: Simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs, Phys. Rev. Lett., 94 (2005) 018702.
  • [23] G. L. Pellegrini, L. de Arcangelis, H. J. Herrmann, C. Perrone-Capano. Modelling the brain as an Apollonian network. arXiv preprint q-bio/0701045 (2007).
  • [24] T. Zhou, G. Yan, and B.-H. Wang. Maximal planar networks with large clustering coefficient and power-law degree distribution. Phys. Rev. E, 71 (2005) 046141.
  • [25] A. Frieze and C. E. Tsourakakis, On certain properties of random apollonian networks, In WAW, 7323 (2012) 93-112.
  • [26] J. Ozik et al., Growing networks with geographical attachment preference: Emergence of small worlds, Physical Review E, 69 (2004) 026108.
  • [27] J. Zhang, E. Yeh, E. Modiano, Robustness of interdependent random geometric networks, 54th Annual Allerton Conference on Communication, Control, and Computing, Sept. 2016, pp. 172-179. Monticello, IL, USA.
  • [28] C. Dangalchev, Residual closeness in networks, Physica A: Statistical Mechanics and its Applications, 365 (2) (2006) 556-564.
  • [29] E. Estrada, The Structure of Complex Networks, Oxford University Press, 2011.
  • [30] G. Sabidussi, The centrality index of a graph, 31 (4) (1966) 581–603.
  • [31] L.C. Freeman, Centrality in social networks conceptual clarification, Social Networks, 1 (215) (1979) 215-239.
  • [32] V. Latora and M. Marchiori, Efficient behavior of small-world networks, Phys Rev Lett., 87 (19) (2001) 198701.
  • [33] R. Albert and A.-L. Barabási, Statistical mechanics of complex networks. Reviews of Modern Physics, 74 (1) (2002) 47-97.
  • [34] W. Greiner, L. Neise, H. Stöcker, Thermodynamics and statistical mechanics, Springer Science & Business Media, 2012.
  • [35] Z.-Xi Wu and P. Holme, Onion structure and network robustness, Physical Review E, 84 (2) (2011) 026106.
  • [36] M. Zare, Z. Rezvani, A. A. Benasich, Automatic classification of 6-month-old infants at familial risk for language-based learning disorder using a support vector machine, Clinical Neurophysiology, Issue 127, pp. 2695-2703, 2016.
  • [37] Original website online: http://www-personal.umich.edu/~mejn/netdata/
  • [38] J. Kunegis, KONECT: The Koblenz Network Collection, In Proc. Int. Web Observatory Workshop, 2013, pp. 1343-1350. Original website online:http://konect.uni-koblenz.de/networks/
  • [39] A. Clauset et al., Power-Law Distributions in Empirical Data, SIAM Rev., 51 (4) (2009) 661-703.
  • [40] Estrada, E., Quantifying Network Heterogeneity. Physical Review E, 82 (2010) 066102.
  • [41] M. Randić, Characterization of molecular branching. Journal of the American Chemical Society, 97(23), pp.6609-6615, 1975.
علوم رایانش و فناوری اطلاعات
دوره 16، شماره 1
بهار و تابستان
اردیبهشت 1397