1
دانشکده مهندسی و علوم کامپیوتر، دانشگاه شهید بهشتی، تهران، ایران
2
دانشکده فنی و مهندسی، دانشگاه آزاد اسلامی واحد علوم و تحقیقات، تهران، ایران
چکیده
رتبهبندی گرههای تأثیرگذار با استفاده از روشهای تحلیلِ کمّی، از اهمیت به سزایی در شبکههای پیچیده و اجتماعی برخوردار است. بسیاری از مکانیزمها در شبکههای پیچیده همچون دینامیکهای انتشار ، برهمکنشهای آبشاری و همگامسازی در شبکه به میزان قابل ملاحظهای توسط بخش کوچکی از گرههای تأثیرگذار تحت تأثیر قرار میگیرند. بهمنظور استقرار روشهای نوین و کارآمد، در این مقاله ما از شاخصهای نیمه-محلی مبتنی بر آنتروپی-انرژی تعمیمیافتة گراف جهت رتبهبندی کارآمد گرههای تأثیرگذار استفاده میکنیم. بهویژه، آشکار میکنیم که معیارهای محلی آنتروپی مانند آنتروپی شانون، ون نیومن و نیز آنتروپیهای تعمیم یافتة گراف چگونه همراه با معیارهای سراسری انرژی که با ساخت ماتریسهای مستخرج از گراف در ارتباط اند، میتوانند جهت ارزیابی اهمیت گرهها در شبکههای پیچیده و اجتماعی مورد استفاده قرار بگیرند. با بهکاربستن این معیارها بر روی شبکهها نشان میدهیم که از میان شاخصهای مبتنی بر آنتروپی-انرژی تعمیمیافتة گراف، کدامیک از منظر تبیینِ اهمیت گرهها کارآمدتر است و در برابر تغییرات ناگهانی حذف گرهها پایداری بیشتری دارد.
[6] M. Kurant, P. Thiran, P. Hagmann, “Error and attack tolerance of layered complex networks,” Phys. Rev. E, vol. 76, no. 2, pp. 026103, 2007.
[7] A.E. Motter, Y.C. Lai, “Cascade-based attacks on complex networks,” Phys. Rev. E, vol. 66, no. 6, pp. 065102, 2002.
[8] Estrada, E.; Hatano, N. “A vibrational approach to node centrality and vulnerability in complex networks,” Phys. A Stat. Mech. Appl, Issue 17, pp 3648-3660, 2009.
[9] E. Estrada, “Quantifying network heterogeneity,” Physical Review E, vol. 82, no. 6, p.066102, 2010.
[10] Ai, Xinbo, “Node importance ranking of complex networks with entropy variation,” Entropy, vol.19, no. 7, pp. 303, 2017.
[11] Anand, K.; Krioukov, D.; Bianconi, G. “Entropy distribution and condensation in random networks with a given degree distribution,” Phys. Rev. E Stat. Nonlinear Soft Matter Phys, vol. 6, pp. 062807, 2014.
[12] Li, Xueliang, Z. Qin, M. Wei, I. Gutman, M. Dehmer. “Novel inequalities for eneralized graph entropies–Graph energies and topological indices,” Applied Mathematics and Computation, vol. 259, pp. 470-479, 2015.
[13] A. Mowshowitz, and M. Dehmer, “Entropy and the complexity of graphs revisited,” Entropy, vol. 14, no. 3, p.559-570, 2012.
[14] I. Gutman, “The energy of a graph,” Ber Math–Statist Sekt Forschungsz Graz, Issue 103, pp. 1-22, 1978.
[15] M. Dehmer, X. Li, Y. Shi, “Connections between Generalized Graph Entropies and Graph Energy,” Complexity, vol. 21, Issue 1, Sept./Oct. 2015, pp. 35-41.
[16] B.J. McClelland, “Properties of the latent roots of a matrix: The estimation of -electron energies,” J Chem Phys, Issue 54, pp. 640-643, 1971.
[17] J. H. Koolen, V. Moulton, and I. Gutman, “Improving the McClelland inequality for total -electron energy,” Chemical Physics Letters, vol. 320, no. 3, pp. 213-216, 2000.
[18] B. Huo, Y Shi, X. Li, “Complete solution to a conjecture on the maximal energy of unicyclic graphs,” European journal of combinatorics, vol. 32, no. 5, pp. 662-673, 2011.
[19] E.O.D. Andriantiana and S. Wagner, “Unicyclic graphs with large energy,” Linear Algebra and its Applications, vol. 435, no. 6, pp.1399-1414, 2011.
[20] E. Estrada amd M. Benzi, “What is the meaning of the graph energy after all?,” Discrete Applied Mathematics, Issue 230, pp. 71-77, 2017.
[21] F. Safaei, F. Kashkooei Jahromi, S. Fathi, “A method for computing local contributions to graph energy based on Estrada–Benzi approach,” Discrete Applied Mathematics, vol. 260, pp. 214-226, 2019.
[22] F. Safaei, F. Kashkooei Jahromi, S. Fathi, “Graphlets Importance Ranking in Complex Networks based on the Spectral Energy Contribution,” International Journal of Computer Mathematics: Computer Systems Theory, pp. 1-14, 2020.
[23] I. Gutman and B. Zhou, “Laplacian energy of a graph,” Linear Algebra and its applications, vol. 414, no. 1, pp. 29-37, 2006.
[24] C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal, vol. 27, no. 3, p.379-423, 1948.
[25] M. Faloutsos, P. Faloutsos, C. Faloutsos, “On power-law relationships of the internet topology,” Comp. Comm. Rev. vol. 29, pp. 251-262, 1999.
[26] S.N. Dorogovtsev, J.F.F. Mendes, A.N. Samukhin, “Metric structure of random networks,” Nucl. Phys. B 653, pp. 307-338, 2003.
[27] K. Malarz, J. Karpinska, A. Kardas, K. Kulalowski, “Node-node distance distribution for growing networks,” arXiv:cond-mat/0309255v2.
[28] V.D. Blondell, J.-L. Guillaume, J.M. Hendrickx, R.M. Jungers, “Distance distribution in random graphs and application to network exploration,” Phys. Rev. E, vol. 76, pp. 066101, 2007.
[29] H. Wiener, “Structural determination of paraffin boiling points,” J. Amer. Chem. Soc, vol. 69, pp. 17-20, 1947.
[30] E. Estrada and E. Vargas-Estrada, “Distance-sum heterogeneity in graphs and complex networks,” Applied Mathematics and Computation, vol. 218, Issue 21, pp. 10393-10405, 2012.
[31] A.T. Balaban, “Highly discriminating distance-based topological index,” Chem. Phys. Lett, vol. 89, pp. 399-404, 1982.
[32] L.C. Freeman, “Centrality in networks: I. Conceptual clarification,” Social Networks, Issue 1, pp. 215-239, 1979.
[33] C. DANGALCHEV, “Residual closeness in networks,” Physica A: Statistical Mechanics and its Applications, Issue 365, pp. 556-564, 2006.
[34] 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.
[35] F. Passerini and S. Severini, “Quantifying complexity in networks: the von Neumann entropy,” International Journal of Agent Technologies and Systems (IJATS), Vol. 1, no. 4, pp. 58-67, 2009.
[36] V. Latora and M. Marchiori, “Efficient behavior of small-world networks,” Phys Rev Lett., vol. 87, no. 19, pp. 198701, 2001.
[37] http://www-personal.umich.edu/~mejn/netdata/
[38] 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.
[39] 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/
صفایی,فرشاد , عمادیکوچک,محمدمهدی و امین,محمد . (1399). شاخصهای آنتروپی-انرژی گراف برای رتبهبندی گرههای تأثیرگذار در شبکههای پیچیده و اجتماعی. (e162094). علوم رایانش و فناوری اطلاعات, 18(1), e162094
MLA
صفایی,فرشاد , , عمادیکوچک,محمدمهدی , و امین,محمد . "شاخصهای آنتروپی-انرژی گراف برای رتبهبندی گرههای تأثیرگذار در شبکههای پیچیده و اجتماعی" .e162094 , علوم رایانش و فناوری اطلاعات, 18, 1, 1399, e162094.
HARVARD
صفایی فرشاد, عمادیکوچک محمدمهدی, امین محمد. (1399). 'شاخصهای آنتروپی-انرژی گراف برای رتبهبندی گرههای تأثیرگذار در شبکههای پیچیده و اجتماعی', علوم رایانش و فناوری اطلاعات, 18(1), e162094.
CHICAGO
فرشاد صفایی, محمدمهدی عمادیکوچک و محمد امین, "شاخصهای آنتروپی-انرژی گراف برای رتبهبندی گرههای تأثیرگذار در شبکههای پیچیده و اجتماعی," علوم رایانش و فناوری اطلاعات, 18 1 (1399): e162094,
VANCOUVER
صفایی فرشاد, عمادیکوچک محمدمهدی, امین محمد. شاخصهای آنتروپی-انرژی گراف برای رتبهبندی گرههای تأثیرگذار در شبکههای پیچیده و اجتماعی. علوم رایانش و فناوری اطلاعات, 1399; 18(1): e162094.
علوم رایانش و فناوری اطلاعات