A comparative performance analysis of the exponential-based and resolvent-based centrality measures

• Autorzy: Wilczek Piotr
• Języki publikacji: EN

Abstrakty

EN

The present study aims to quantitatively assess the effect of the attenuation factor on the resolution, performance, rank correlations, robustness and assortativity of the Katz centrality measure. We found that the granularity of the exponential-based and resolvent-based ranking algorithms is strongly correlated with the number of automorphically equivalent nodes within the network. Thus, this result can be viewed as a bridge between algebraic and quantitative graph theory. Moreover, we substituted the dichotomous adjacency matrix in the definitions of the exponential-based and resolvent-based centrality indices by its weighted (normalized) version and, therefore, we obtained two novel ranking algorithms. The deliberate attack simulation experiments carried out on four empirical and on two model networks showcased that the newly suggested ranking methods considerably outperform their unweighted counterparts as well as the classical degree centrality measure. In the last part of the paper, we introduced the concept of the centrality assortativity profile of a complex network. The extensive numerical results demonstrated that this novel theoretical notion is useful in complex network mining.

Słowa kluczowe

EN

complex networks; centrality measures; attack simulations

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Silesian Journal of Pure and Applied Mathematics
• Rocznik: 2020
• Tom: vol. 10, iss. 1
• Strony: 45--102
• Opis fizyczny: Bibliogr. 53 poz.

Twórcy

autor

Wilczek Piotr

• Computer Laboratory, Poznan, Poland

Bibliografia

• 1. Adamic L.A., Glance N.: The political blogosphere and the 2004 US Election. In: Proceedings of the WWW-2005 Workshop on the Weblogging Ecosystem 2005.
• 2. Albert R., Jeong H., Barab´asi A.-L.: Error and attack tolerance of complex networks. Nature 406 (2000), 378-382.
• 3. Allen-Perkins A., Pastor J.M., Estrada E.: Two-walks degree assortativity in graphs and networks. Appl. Math. Comput. 311 (2017), 262-271.
• 4. Andreotti J., Jann K., Melie-Garcia L., Giezendanner S., Abela E., Wiest R.,Dierks T., Federspiel A.: Validation of network communicability metrics for the analysis of brain structural networks. PloS ONE 9, no. 12 (2014), e115503.
• 5. Aprahamian M., Higham D.J., Higham N.J.: Matching exponential-based and resolvent-based centrality measures. J. Complex Netw. 4, no. 2 (2015), 157-176.
• 6. Arcagni A., Grassi R., Stefani S., Torriero A.: Higher order assortativity in complex networks. Eur. J. Oper. Res. 262 (2017), 708-719.
• 7. Auguie B.: gridExtra: Miscellaneous functions for ’Grid’ graphics. R package version 2.3 (2017). https://CRAN.R-project.org/package=gridExtra.
• 8. Badham J.M.: Commentary: Measuring the shape of degree distribution. Netw. Sci. 1, no. 2 (2013), 213-225.
• 9. Batagelj V., Mrvar A.: Pajek datasets (2006). http://vlado.fmf.uni-lj.si/pub/networks/data.
• 10. Benzi M., Klymko C.: Total communicability as a centrality measure. J. Complex Netw. 1 (2013), 124-149.
• 11. Benzi M., Klymko C.: A matrix analysis of different centrality measures. arXiv:1312.6722v3 (2014).
• 12. Bozkurt S.B., G¨ung¨or A.D., Gutman I.: Randi´c matrix and Randi´c energy. MATCH Commun. Math. Comput. Chem. 64 (2010), 239-250.
• 13. Borchers H.W.: pracma. Practical numerical math functions. R package version 2.1.1 (2017). https://CRAN.R-project.org/package=pracma.
• 14. Crofts J.J., Higham D.J.: A weighted communicability measure applied to complex brain networks. J. R. Soc. Interface 6 (2009), 411-414.
• 15. Csardi G., Nepusz T.: The igraph software package for complex network research. InterJournal Complex Syst. (2006), 1695.
• 16. Dur´on C.: Heatmap centrality: A new measure to identify super-spreader nodes in scale-free networks. PLoS ONE 15, no. 7 (2000), e0235690.
• 17. Estrada E.: The Structure of Complex Networks: Theory and Applications. Oxford University Press, Oxford 2011.
• 18. Estrada E., Hatano N., Benzi M.: The physics of communicability in complex networks. Phys. Rep. 514 (2012), 89-119.
• 19. Estrada E., Rodr´ıgues-Vel´azquez J.A.: Subgraph centrality in complex networks. Phys. Rev. E 71 (2005), 056103.
• 20. Goh K.I., Oh E., Kahng B., Kim D.: Betweenness centrality correlation in social networks. Phys. Rev. E 67 (2003), 017101.
• 21. Guimera R., Danon L., Diaz-Guilera A., Giralt F., Arenas A.: Self-similar community structure in a network of human interactions. Phys. Rev. E 68 (2003), 065103(R).
• 22. Higham N.J.: Functions of Matrices. Theory and Computation. Society for Industrial and Applied Mathematics, Philadelphia 2008.
• 23. Holme P., Kim B.J., Yoon C.N., Han S.K.: Attack vulnerability of complex networks. Phys. Rev. E 65 (2002), 056109.
• 24. Ibnoulouafi A., El Haziti M.: Density centrality: identifying influential nodes based on area density formula. Chaos Soliton Fract. 114 (2018), 69-80.
• 25. Ibnoulouafi A., El Haziti M., Cherifi H.: M-centrality: identifying key nodes based on global position and local degree variation. J. Stat. Mech.: Theory and Exp. 2018 (2018), 073407.
• 26. Iyer S., Killingback T., Sundaram B., Wang Z.: Attack robustness and centrality of complex networks. PLoS ONE 8, no. 4 (2013), e59613.
• 27. Kassambara A.: ggpubr: ’ggplot2’ based publication ready plots. R package version 0.1.8 (2018). https://CRAN.R-project.org/package=ggpubr.
• 28. Kassambara A., Mundt F.: factoextra: Extract and visualize the results of multivariate data analyses. R package version 1.0.5 (2017). https://CRAN.Rproject. org/package=factoextra.
• 29. Katz L.: A new status index derived from sociometric data analysis. Psychometrik 18 (1953), 39–43.
• 30. Kirkland S.J., Neumann M.: Group Inverses of M-Matrices and their Applications. CRC Press, Boca Raton 2013.
• 31. Liu B., Huang Y., Feng J.: A note on the Randi´c spectral radius. MATCH Commun. Math. Comput. Chem. 68 (2012), 913–916.
• 32. Lv M., Guo X., Chen J., Lu Z.-M., Nie T.: Second-order centrality correlation in scale-free networks. Int. J. Mod. Phys. C 26, no. 10 (2015), 1550116.
• 33. Martin C., Niemeyer P.: Influence of measurement errors on networks: Estimating the robustness of centrality measures. Netw. Sci. 7, no. 2 (2019), 180-195.
• 34. Mayo M., Abdelzaher A., Ghosh P.: Long-range degree correlations in complex networks. Comput. Soc. Netw. 2 (2015), article number 4.
• 35. Meghanathan N.: Assortativity analysis of real-world network graphs based on centrality metrics. Computer and Information Science 9, no. 3 (2016), 7-25.
• 36. Mueller L.A.J., Kugler K.G., Dander A., Graber A., Dehmer M.: QuACN: an R package for analyzing complex biological networks quantitatively. Bioinformatics 27 (2011), 140–141.
• 37. Newman M.E.J.: Mixing patterns in networks. Phys. Rev. E 67, no. 2 (2003), 026126.
• 38. Newman M.E.J.: Networks. An Introduction. Oxford University Press Inc., New York 2010.
• 39. Niu Q., Zeng A., Fan Y., Di Z.: Robustness of centrality measures against network manipulation. Physica A 438 (2015), 124–131.
• 40. Noldus R., Van Mieghem P.: Assortativity in complex networks. J. Complex Netw. 3, no. 4 (2015), 507-542.
• 41. Opsahl T.: Why anchorage is not (that) important: Binary ties and sample selection. http://wp.me/poFcY-Vw.
• 42. Opahl T., Agneessens J., Skvoretz J.: Node centrality in weighted networks: Generalizing degree and shortest paths. Soc. Netw. 32 (2010), 245-251.
• 43. Plemmons R.J.: M-matrix characterizations. I-nonsingular M-matrices. Linear Algebra Appl. 18 (1977), 175-188.
• 44. R Core Team: R: a Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna 2017, http://www.Rproject.org/.
• 45. Ronqui J.R.F., Travieso G.: Analyzing complex networks through correlations in centrality measurements. J. Stat. Mech.: Theory Exp. 2015 (2015), P05030.
• 46. Steyvers M., Tenenbaum J.B.: The large-scale structure of semantic networks: Statistical analyses and a model of semantic growth. Cogn. Sci. 29 (2005), 41-78.
• 47. Takemoto K., Oosawa C.: Introduction to complex networks: measures, statistical properties, and models. In: Statistical and Machine Learning Approaches for Network Analysis. Dehmer M., Basak S.C. (eds.), JohnWiley & Sons, New Jersey 2012.
• 48. Todeschini R., Consonni V.: Molecular Descriptors for Chemoinformatics. Wiley-VCH, Weinheim 2009.
• 49. Wickham H.: ggplot2: Elegant Graphics for Data Analysis. Springer-Verlag, New York 2009.
• 50. Wilczek P.: Novel centrality measures and distance-related topological indices in network data mining. Silesian J. Pure Appl. Math. 7 (2017), 21-63.
• 51. Wilczek P.: Identifying influential nodes in the genome-scale metabolic networks. Silesian J. Pure Appl. Math. 9 (2019), 9-47.
• 52. Wilczek P.: The communicability-based centrality measures (2020). https://repod.icm.edu.pl/dataset.xhtml?persistentId=doi:10.18150/J0G6U.
• 53. Zhou S., Cox I.J., Hansen L.K.: Second-order assortative mixing in social networks. In: Complex Networks VIII: Proceedings of the 8th Conference on Complex Networks. CompleNet 2017. Gon¸calves B., Menezes R., Sinatra R., Zlatic V. (eds.), Springer Int. Publ., Cham, 2017.