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

شاخص‌های آنتروپی-انرژی گراف برای رتبه‌بندی گره‌های تأثیرگذار در شبکه‌های پیچیده و اجتماعی

نویسندگان

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

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

چکیده

رتبه‌بندی گره‌های تأثیرگذار با استفاده از روش‌های تحلیلِ کمّی، از اهمیت به سزایی در شبکه‌های پیچیده و اجتماعی برخوردار است. بسیاری از مکانیزم‌ها در شبکه‌های پیچیده همچون دینامیک‌های انتشار ، برهمکنش‌های آبشاری و همگام‌سازی در شبکه به میزان قابل ملاحظه‌ای توسط بخش کوچکی از گره‌های تأثیرگذار تحت تأثیر قرار می‌گیرند. به‌منظور استقرار روش‌های نوین و کارآمد، در این مقاله ما از شاخص‌های نیمه-محلی مبتنی بر آنتروپی-انرژی تعمیم‌یافتة گراف جهت رتبه‌بندی کارآمد گره‌های تأثیرگذار استفاده می‌کنیم. به‌ویژه، آشکار می‌کنیم که معیارهای محلی آنتروپی مانند آنتروپی شانون، ون نیومن و نیز آنتروپی‌های تعمیم یافتة گراف چگونه همراه با معیارهای سراسری انرژی که با ساخت ماتریس‌های مستخرج از گراف در ارتباط اند، می‌توانند جهت ارزیابی اهمیت گره‌ها در شبکه‌های پیچیده و اجتماعی مورد استفاده قرار بگیرند. با به‌کاربستن این معیارها بر روی شبکه‌ها نشان می‌دهیم که از میان شاخص‌های مبتنی بر آنتروپی-انرژی تعمیم‌یافتة گراف، کدامیک از منظر تبیینِ اهمیت گره‌ها کارآمدتر است و در برابر تغییرات ناگهانی حذف گره‌ها پایداری بیشتری دارد.

کلیدواژه‌ها

  • [1] A-L. Barabási, Network science book, Boston, MA: Center for Complex Network, Northeastern University. Available online at: http://barabasi. com/networksciencebook, 2017.
  • [2] X. Li, Z.H. Liu, B.H. Wang, “On spreading dynamics on networks,” Complex Syst. Complexity Sci, vol. 07, no. 2, pp. 33–37, 2010.
  • [3] Z.H. Rong, M. Tang, X.F. Wang, “Annual inventory of complex networks,” J. Univ. Electron. Sci. Technol. China, vol. 6, 2012. pp. 801-806.
  • [4] R. Albert, H. Jeong, A.L. Barabási, “Error and attack tolerance of complex networks,” Nature, vol. 406, no. 6794, pp. 378-382, 2000.
  • [5] S.H. Strogatz, “Exploring complex networks,” Nature, vol. 410, No. 6825, pp. 268-276, 2001.
  • [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/

 

علوم رایانش و فناوری اطلاعات
دوره 18، شماره 1
بهار و تابستان
اردیبهشت 1399