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

ارزیابی ناهمگنی فرآیند ادغام شبکه‌های پیچیده و اجتماعی در مدل باراباشی-آلبرت براساس روش ترکیبی تاپسیس-انتروپی وزن‌دار

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشگاه آزاد اسلامی، واحد علوم و تحقیقات، تهران، ایران

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

چکیده

یکی از موفق‌ترین مدل‌های رشد در شبکه‌های پیچیده و اجتماعی، مدل باراباشی-آلبرت  (BA) است که رشد و اتصال ترجیحی خطی  (LPA) را به‌عنوان دو عنصر سازندة اصلیِ یک شبکه خود-سازمانده  در ساختار مقیاس-آزاد  (SF) پیشنهاد کرده است. این عوامل ناظر به این واقعیت‌اند که پدیدة رشد در اغلب شبکه‌ها حاصل از افزودن گره‌های جدیدی است که به شکل ترجیحی به گره‌هایی با درجه بالا در شبکه اتصال می‌یابند. رسانه‌های اجتماعی در یکپارچه‌سازی روابط عمومی کمک شایان توجهی کرده و فن‌آوری‌ها و روش‌های راه‌بردی را بیش از پیش گسترش داده‌اند که این امر ناشی از پدیدة مهم ادغام رسانه‌ها و شبکه‌های جدید در یکدیگر بوده است. ویژگی ادغام در شبکه‌ها به رشد و گسترش آن‌ها کمک می‌کند و بدین ترتیب، شبکه‌های مختلف از منظر تحقیق و توسعه، سرمایه‌گذاری، منابع انسانی، خدمات پس از فروش و خدمات مشتری در یکدیگر ادغام  و یکپارچه‌سازی می‌شوند. همچنین، تبیین شباهت‌ها/عدم شباهت‌ها میان مدل‌های مختلف گراف‌ و مطالعة ناهمگنی (نامنتظمی) گراف‌ها، یکی از مسایل پژوهشی بنیادی در مطالعة شبکه‌های پیچیده و اجتماعی محسوب می‌شود. مدل BA، مدل مولدی است که مکانیزم‌هایی را جهت ورود و افزودن گره‌ها در شبکه پیشنهاد داده است. در این مقاله، یک روش نوین و کارآمد جهت ادغام دو شبکه مقیاس-آزاد مبتنی بر مدل BA ارائه شده است. تکنیک پیشنهادی براساس ترکیب روش ترجیح براساس مشابهت به راه‌حل ایدآل  (TOPSIS) با انتروپی وزن‌دار است که به اختصار EWM-TOPSIS نام دارد. این تکنیک با روش رتبه‌بندی مبتی بر انتروپی کوانتومی مقایسه و برتری آن با نتایج برآمده از آزمون‌های شبیه‌سازی نشان داده شده است. افزون براین، پدیده ناهمگنی در گرافِ یکپارچة ناشی از فرآیند ادغام، به کمک مهمترین شاخص‌های ناهمگنی، اندازه‌گیری و سنجش شده است. الگوریتم ادغام پیشنهادی می‌تواند بازتابی از سناریوهای دنیای واقعی در فرآیند یک‌پارچه‌سازی شبکه‌های پیچیده و اجتماعی باشد و محوریت اصلی آن نیز بر حفظ ویژگیهای اصلی گراف‌های مدل BA استوار است. نتایج تجربیِ آزمونهای شبیه‌سازی نشان می‌دهند که روش ادغام پیشنهادی در مقایسه با سایر روش‌ها و همراه با شاخص‌های ناهمگنی می‌تواند با دقت و صحت مناسبی به‌منظور تبیینِ مشخصات شبکه‌های مقیاس-آزاد مدل BA مورد استفاده قرار بگیرد.

کلیدواژه‌ها

  • [1] D. J. Watts and S. H. Strogatz “Collective dynamics of small-world networks,” Nature, Vol. 393, No. 6684, pp. 440-442, 1998.
  • [2] A-L. Barabási and R. Albert, “Emergence of Scaling in Random Networks,” Science, Vol. 286, No. 5439, pp. 509-512, 1999.
  • [3] 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.
  • [4] I. Gutman, "Topological indices and irregularity measures," J. Bull, Vol. 8, pp.469-475, 2018.
  • [5] E. Estrada, "Quantifying network heterogeneity," Physical Review E, Vol. 82, No. 6, p.066102, 2010.
  • [6] X. Li, Y. Shi, "A survey on the Randić index," MATCH: Comm. Math. Comput. Chem., Vol. 59, pp. 127-156, 2008.
  • [7] M. Maier, U. von Luxburg, M. Hein, "Influence of graph construction on graph-based clustering measures," NIPS, pp. 1-9, 2010.
  • [8] L. Han, F. Escolano, E.R. Hancock, R.C. Wilson, "Graph characterizations from von Neumann entropy." Pattern Recognition Letters, Vol. 33, No. 15, pp.1958-1967, 2012.
  • [9] E. Estrada and E. Vargas-Estrada, "Distance-sum Heterogeneity in Graphs and Complex Networks," Applied Mathematics and Computation, Issue 218, pp. 10393-10405, 2012.
  • [10] R. Olfati-Saber, J. A. Fax and R. M. Murray, "Consensus and Cooperation in Networked Multi-Agent Systems," in Proceedings of the IEEE, vol. 95, no. 1, pp. 215-233, Jan. 2007, doi: 10.1109/JPROC.2006.887293.
  • [11] A.T. Balaban, "Highly discriminating distance-based topological index," Chem. Phys. Lett., Vol. 89, pp. 399-404, 1982.
  • [12] L. Collatz and U. Sinogowitz, "Spektren endlicher Grafen. Abh." Math. Sem. Univ. Hamburg, Vol. 21, pp. 63-77, 1957.
  • [13] D. Cvetković and P. Rowlinson, "On connected graphs with maximal index," Publ. Inst. Math. (Beograd), Vol. 44, pp. 29-34, 1988.
  • [14] F. K. Bell, "A note on the irregularity of a graph," Linear Algebra Appl., Vol. 161, pp. 45-54, 1992.
  • [15] T.A.B. Snijders, "The degree variance: an index of graph heterogeneity," Social Networks, Vol. 3, No. 3, pp. 163-174, 1981.
  • [16] M. O. Albertson, "The irregularity of a graph," Ars Comb., Vol. 46, pp. 219-225, 1997.
  • [17] G.H. Fath-Tabar, I. Gutman, R. Nasiri, "Extremely irregular trees," Bulletin (Académie serbe des sciences et des arts. Classe des sciences mathématiques et naturelles. Sciences mathématiques), pp.1-8, 2013.
  • [18] P. Hansen, H. Mélot, in S. Fajtlowicz (Eds.), Graphs and Discovery, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Providence, American Mathematical Society, Vol. 69, pp. 253-264, 2005.
  • [19] H. Abdo, D. Dimitrov, I. Gutman, "Graphs with maximal s irregularity," Discrete Appl. Math., Vol. 250, pp. 57-64, 2018.
  • [20] H. Abdo, S. Brandt, D. Dimitrov, "The total irregularity of a graph," Discrete Math. Theory Comput. Sci., Vol. 16, pp. 201-206, 2014.
  • [21] V. Nikiforov, "Eigenvalues and degree deviation in graphs," Linear Algebra Appl., Issue 414, pp. 347-360, 2006.
  • [22] L. Shi, "Bounds on Randic indices," Discr. Appl. Math., Vol. 309, pp. 5238-5241, 2009.
  • [23] I. Gutman, B. Furtula, C. Elphick, "The new/old vertex-degree-based topological indices," MATCH Commun. Math. Comput. Chem., Vol. 72, pp. 617-632, 2014.
  • [24] F. Goldberg, "Spectral radius minus average degree: a better bound," arXiv: 1407.4285v1 [math.co], 16 July, 2014.
  • [25] T. Réti, E. Tóth-Laufer, "On the construction and comparison of graph irregularity indices," Kragujevac Journal of Science, Vol. 39, pp.53-75, 2017.
  • [26] C. Elphick and P. Wocjan, "New measures of graph irregularity," Electronic Journal of Graph Theory and Applications, Vol. 2, No. 1, pp. 52-65, 2014.
  • [27] A. Hamzeh, and T. Réti, "An analogue of Zagreb index inequality obtained from graph irregularity measures," MATCH Commun. Math. Comput. Chem, Vol. 72, No. 3, pp.669-683, 2014.
  • [28] S. Izumino, H. Mori and Y. Seo, "On Ozeki"s inequality," Journal of Inequalities and Applications, Vol. 2, pp. 235-253, 1998.
  • [29] O. Favaron, M. Mah´eo, J.-F. Sacl´e, "Some eigenvalue properties in Graphs (conjectures of Graffiti-II)," Discrete Math., Vol. 111, pp. 197-220, 1993.
  • [30] M. E. J. Newman, "Random graphs as models of networks," Sante Fe Institute, Working Paper 2002-02-005.
  • [31] A. Ilić, D. Stevanović, "On comparing Zagreb indices," MATCH Commun. Math. Comput. Chem., Vol. 62, pp. 681-687, 2009.
  • [32] Ilić and B. Zhou, On reformulated Zagreb indices, Discr. Appl. Math., Vol. 160, pp. 204-209, 2012.
  • [33] J. Hao, "Theorems about Zagreb indices and modified Zagreb indices," MATCH Commun. Math. Comput. Chem., Vol. 65, pp.659-670, 2011.
  • [34] K.M. Smith and J. Escudero, "Normalised degree variance," Applied Network Science, Vol. 5, No. 1, pp.1-22, 2020.
  • [35] F. Safaei, S. Tabrizchi, A.H. Rasanan, M. Zare, "An energy-based heterogeneity measure for quantifying structural irregularity in complex networks," Journal of Computational Science, Vol. 36, p.101011, 2019.
  • [36] P. Held, A. Dockhorn, R. Kruse, “On merging and dividing of barabasi-albert-graphs,” In 2014 IEEE Symposium on Evolving and Autonomous Learning Systems (EALS), pp. 17-24, 2014.
  • [37] A-L. Barabási, Network science book, Boston, MA: Center for Complex Network, Northeastern University, Available online at: http://barabasi.com/networksciencebook, 2022.
  • [38] E. Estrada, P.A. Knight, A First Course in Network Theory, Oxford University Press, Oxford, UK, 2015.
  • [39] L. Han, “Graph Generative Models from Information Theory, “Doctoral dissertation, University of York, 2012.
  • [40] F. Passerini and S. Severini, "The von Neumann entropy of networks." arXiv preprint arXiv:0812.2597, 2008.
  • [41] K. Anand, G. Bianconi, S. Severini, "Shannon and von Neumann entropy of random networks with heterogeneous expected degree," Physical Review E, Vol. 83, No. 3, p.036109, 2011.
  • [42] E. Estrada, “Degree heterogeneity of graphs and networks. I. Interpretation and the “heterogeneity paradox,” Journal of Interdisciplinary Mathematics, Vol. 22, No. 4, pp.503-529, 2019.
علوم رایانش و فناوری اطلاعات
دوره 20، شماره 2
پاییز و زمستان 1401
آذر 1401