1
دانشیار، دانشکده مهندسی و علوم کامپیوتر، دانشگاه شهید بهشتی، تهران، ایران
2
پژوهشگاه دانش های بنیادی (IPM)، پژوهشکده علوم کامپیوتر، تهران، ایران
چکیده
در شبکههای پیچیده و زیرساختهای پیشرفته امروزی، استحکام یکی از ویژگیهای حیاتی و مهم به شمار میرود و در طی سالیان اخیر به یکی از زمینههای پژوهشی موردعلاقه و رو به رشد تبدیل شده است. این زمینه پژوهشی در شبکههای پیچیده به دنبال آن است تا راهکارها و مکانیزمهایی را جهت بهبود اتصالپذیری شبکهها در برابر خرابیهای تصادفی و حملات هدفمند جستجو کند. تاکنون معیارهای مختلف و متنوعی برای سنجش و ارزیابی میزان استحکام و تابآوری شبکههای پیچیده ارائه شده است. بخش مهمی از این معیارها به نظریهی جبری گراف و مطالعه و بررسی طیف ماتریس مجاورت گراف که طیف گراف نیز نام دارد، اختصاص یافته است. انرژی هر گراف ساده عبارت از مجموع قدرمطلق مقادیر ویژه آن است. در این مقاله ابتدا نشان داده میشود که انرژی هر شبکه با استحکام آن قویاً همبستگی دارد؛ سپس یک الگوریتم سیم بندی مجدد برای بهینهسازی معیار انرژی گراف معرفی میشود. با استفاده از الگوریتم تکاملی تلاش میشود به این پرسش پاسخ داده شود که سیم بندی پیشنهادی کدام مجموعه از یالها را برای افزایش بیشترین مقدار در انرژی در مقایسه با گراف اولیه در بر خواهد داشت. با پاسخ به این پرسش است که میتوان در حوزههای مختلف شبکههای پیچیده و اجتماعی برای یافتن یک راهحل بهینه جهت بهینهسازی انرژی و اتصالپذیری و درنتیجه افزایش استحکام و تابآوری آن تصمیمگیری کرد. نتایج عددی حاصل از شبیهسازی، به پژوهشگر دانشی را دربارهی تعداد یالهای موردنیاز برای سیم بندی و نیز مکانی از شبکه که وجود این یالها سبب افزایش ماکزیمال در انرژی و درنتیجه افزایش ماکزیمال در استحکام میشود، عرضه میدارند.
[1] J. Gao, B. Barzel, A.-L. Barabási, “Universal resilience patterns in complex networks,” Nature, Vol. 530, pp. 307-312, 2016.
[2] A. Avižienis et al., “Basic Concepts and Taxonomy of Dependable and Secure Computing,” IEEE Trans. on Dependable and Secure Computing, Vol. 1, No. 1, pp. 11-33, 2004.
[3] M. N. Youssef, Measure of Robustness for Complex Networks, Ph.D. Thesis, Department of Electrical and Computer Engineering College of Engineering, Kansas State University, 2012.
[4] H. Wang and P.V. Mieghem, “Algebraic connectivity optimization via link addition,” Proceedings of IEEE/ACM Bionetics, Nov. 2008, pp. 25- 28, Hyogo, Japan.
[5] H. Chan and L. Akoglu, “Optimizing Network Robustness by Edge Rewiring: A General Framework, Data Mining and Knowledge Discovery,” Vol. 30, Issue 5, pp 1395-1425, Sept. 2016.
[6] T.S. Evans, “Exact Solutions for Network Rewiring Models,” The European Physical Journal B, Vol. 56, Issue 1, pp 65-69, March 2007.
[7] H. J. Herrmann et al., “Onion-like network topology enhances robustness against malicious attacks,” Journal of Statistical Mechanics: Theory and Experiment, Vol. 2011, Jan. 2011.
[8] E. Estrada, The Structure of Complex Networks, Oxford University Press, 2011.
[9] B. Bollobás, Probabilistic Combinatorics and Its Applications, American Mathematical Society, 1991.
[10] P. Erdös and A. Rényi, “On the Evolution of Random Graphs,” Publications of the Math. Inst. of the Hungarian Academy of Sci., Vol. 5, pp. 17-61, 1960.
[11] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern Physics, Vol. 74, No. 1, pp. 47-97, 2002.
[12] A. Bingham and D. Spradlin, The Long Tail of Expertise, Pearson Education, 2011.
[13] S. Milgram, “Behavioral Study of Obedience,” Journal of Abnormal and Social Psychology, Vol. 67, No. 4, pp. 371-8, 1963.
[14] I. de Sola Pool, M. Kochen, “Contacts and influence, Social networks,” Vol. 1, pp. 5-51, 1978.
[15] D. J. Watts and S. H. Strogatz, “Collective dynamics of small-world networks,” Nature, Vol. 393, No. 6684, pp. 440-442, June 1998.
[16] D. B. West, Introduction to Graph Theory, 2nd ed., Englewood Cliffs, NJ: Prentice-Hall, 2000.
[17] D. Babić et al., “Resistance-Distance Matrix: A Computational Algorithm and Its Applications,” Int. J. Quant. Chem., Vol. 90, pp. 166-176, 2002.
[18] M. Fiedler, “Laplacian of graphs and algebraic connectivity, Combinatorics and Graph Theory,” Banach Center Publications, Vol. 25, No. 1, pp. 57-70, 1989.
[19] I. Gutman, “The energy of a graph,” Steiermärkisches Mathematisches Symposium (Stift Rein, Graz, 1978), Ber. Math., Vol. 10, pp. 1-22, 1978.
[20] L.C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, Vol. 40, No. 35, 1977.
[21] L.C. Freeman, “Centrality in social networks conceptual clarification,” Social Networks, Vol. 1, No. 215 , 1979.
[22] B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics, Vol. 184, Springer-Verlag, 1998.
[23] R. Diestel, Graph Theory, Graduate Texts in Mathematics, Vol. 173, 4th ed., Springer-Verlag, 2010.
[24] V. H. P. Louzada et al., “Smart rewiring for network robustness, Journal of Complex Networks,” pp. 1-10, Sept. 2013.
[25] C. M. Scheneider et al., “Mitigation of malicious attacks on networks,” PNAS, Vol. 108, No. 10, pp. 3838–3841, 2011.
[26] V. H. P. Louzada et al., “Generating Robust and Efficient Networks Under Targeted Attacks,” Intelligent Systems Reference Library, Vol. 85, pp 215-224, 2015.
[28] Z-Xi Wu and P. Holme, “Onion structure and network robustness,” Phys. Rev. E 84, p.026106 , 2011.
[29] A. Sydney, C. Scoglio, D. Gruenbacher, “Optimizing algebraic connectivity by edge rewiring,” Applied Mathematics and Computation, Issue 219, pp. 5465-5479, 2013.
[30] J. Lindquist et al., “Network evolution by different rewiring schemes,” Physica D, Issue 238, pp. 370-378, 2009.
[31] X. –J. Xu et al., “Network evolution by nonlinear preferential rewiring of edges,” Physica A, Issue 390, pp. 2429-2434, 2011.
[32] X-H. Yang et al., “The impact of connection density on scale-free distribution in random networks,” Physica A, Issue 392 pp. 2547-2554, 2013.
[33] L. Ji et al., “Network Entropy Based on Topology Configuration and its Computation to Random Networks,” CHIN. PHYS. LETT., Vol. 25, No. 11, p. 4177, 2008.
[34] Y.-B. Xie, T. Zhou, B.-H. Wang, “Scale-free networks without growth,” Physica A, Issue 387, pp. 1683-1688, 2008.
[35] J. Ohkubo et al., Generation of complex bipartite graphs by using a preferential rewiring process, Physical Review E 72, 036120, 2005.
[36] J. Ohkubo and M. Yasuda, “Fat-tailed degree distributions generated by quenched disorder,” International Conference on Complex Systems (ICCS"06), June 2006, Boston, MA, USA.
[37] V.N. Zadorozhnyi and E.B. Yudin, “Growing network: Models following nonlinear preferential attachment rule,” Physica A, Issue 428, pp. 111–132, 2015.
[38] M. R. Evans and T. Hanney, “Nonequilibrium Statistical Mechanics of the Zero-Range Process and Related Models,” Journal of Physics A: Mathematical and General, Vol. 38, No. 19, 2005.
[39] T.S. Evans and A.D.K. Plato, “Network Rewiring Models,” Heterog. Media 3, pp. 221-238, 2008.
[40] A. Bigdeli, A. Tizghadam, A. Leon-Garcia, “Comparison of Network Criticality, Algebraic Connectivity, and Other Graph Metrics,” SIMPLEX"09, July 1, 2009, Venice, Italy.
[41] W. Ellens, Effective graph resistance and other graph measures for network robustness, Master thesis, Mathematical Institute, University of Leiden, 2011.
[42] A. Yazdani and P. Jefrey, “A note on measurement of network vulnerability under random and intentional attacks,” arXiv:1006.2791 [Cond-Mat, Physics:physics], Retrieved from http://arxiv.org/abs/1006.2791.
[43] E. Estrada, “Network robustness to targeted attacks,” The interplay of expansibility and degree distribution, Eur. Phys. J. B 52, pp. 563-574, 2006.
[44] “Global B2C Ecommerce Sales to Hit $1.5 Trillion This Year Driven by Growth in Emerging Markets - eMarketer.”
[45] D. Fay et al., “Weighted Spectral Distribution for Internet Topology Analysis: Theory and Applications,” IEEE/ACM Transactions on Networking, Vol. 18, No. 1, pp. 164-176, 2010.
[46] J. Wu, M. Barahona, Y.-J. Tan, and H.-Z. Deng, “Spectral measure of structural robustness in complex networks,” Systems, IEEE Trans. on Systems, Man, and Cybernetics - Part A: Systems and Humans, Vol. 41, No. 6, pp. 1244-1252, 2011.
[47] E. Estrada, N. Hatano, M. Benzi, “The physics of communicability in complex networks,” Physics Reports, 514, pp. 89-119, 2012.
[48] A. Yazdani, R. A. Otoo, and P. Jeffrey, “Resilience enhancing expansion strategies for water distribution systems: A network theory approach,” Environmental Modelling & Software, Vol. 26, No. 12, pp. 1574-1582, 2011.
[49] A. Tizghadam and A. Leon-Garcia, Autonomic traffic engineering for network robustness, IEEE Journal on Selected Areas in Communications, Vol. 28, No. 1, pp. 39-50, 2010.
[50] J. P. Rohrer, A. Jabbar, and J. P. G. Sterbenz, “Path diversification: A multipath resilience mechanism,” 7th IEEE International Workshop on the Design of Reliable Communication Networks (DRCN), pp. 343-351, Oct. 2009, Washington, DC, USA.
[51] M. J.F. Alenazi and J. P.G. Sterbenz,” Comprehensive Comparison and Accuracy of Graph Metrics in Predicting Network Resilience,” The 11th International Conference on Design of Reliable Communication Networks (DRCN"015), pp. 157-164, March 2015, Paris, France.
صفایی,فرشاد و بابایی,امین . (1399). بهینهسازی طیف انرژی گرافها و شبکههای پیچیده با استفاده از یک روش سیمبندی مجدد تکاملی. (e162092). علوم رایانش و فناوری اطلاعات, 18(1), e162092
MLA
صفایی,فرشاد , و بابایی,امین . "بهینهسازی طیف انرژی گرافها و شبکههای پیچیده با استفاده از یک روش سیمبندی مجدد تکاملی" .e162092 , علوم رایانش و فناوری اطلاعات, 18, 1, 1399, e162092.
HARVARD
صفایی فرشاد, بابایی امین. (1399). 'بهینهسازی طیف انرژی گرافها و شبکههای پیچیده با استفاده از یک روش سیمبندی مجدد تکاملی', علوم رایانش و فناوری اطلاعات, 18(1), e162092.
CHICAGO
فرشاد صفایی و امین بابایی, "بهینهسازی طیف انرژی گرافها و شبکههای پیچیده با استفاده از یک روش سیمبندی مجدد تکاملی," علوم رایانش و فناوری اطلاعات, 18 1 (1399): e162092,
VANCOUVER
صفایی فرشاد, بابایی امین. بهینهسازی طیف انرژی گرافها و شبکههای پیچیده با استفاده از یک روش سیمبندی مجدد تکاملی. علوم رایانش و فناوری اطلاعات, 1399; 18(1): e162092.
علوم رایانش و فناوری اطلاعات