Identifying influential nodes in the genome-scale metabolic networks

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

Abstrakty

EN

The present article introduces two novel centrality indices which can be used in order to characterize the genome-scale metabolic networks. The deliberate attack simulation experiments conducted on two Barab´asi-Albert models and four genome-scale metabolic networks demonstrate that the proposed ranking methods are effective in identifying essential nodes in complex networks. Also, the Principal Component Analysis reveals that the Kendall centrality correlation profile can be used to describe the metabolic networks and distinguish them from their random counter-parts with the preserved degree distribution.

Słowa kluczowe

EN

complex networks; centrality measures; attack simulations

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Silesian Journal of Pure and Applied Mathematics
• Rocznik: 2019
• Tom: vol. 9, iss. 1
• Strony: 9--47
• Opis fizyczny: Bibliogr. 49 poz.

Twórcy

autor

Wilczek Piotr

• Computer Laboratory, Poznan, Poland

Bibliografia

• 1. Ai X.: Node importance ranking of complex networks with entropy variation. Entropy 19 (2017), 303.
• 2. Albert R., Jeong H., Barabasi A.-L.: Error and attack tolerance of complex networks. Nature 406 (2000), 378–382.
• 3. Auguie B.: gridExtra: miscellaneous functions for ”grids” graphics. R package version 2.3 (2017). https://CRAN.R-project.org/package=gridExtra.
• 4. Bhattacharya S., Chakrabarti S., Nayak A., Bhattacharya S.K.: Metabolic networks of microbial systems. Microb Cell Fact. 2, no. 3 (2003).
• 5. Burt R.S.: Structural holes and good ideas. Am. J. Soc. 110 (2004), 349–399.
• 6. Chen D., Lu L., Shang M-S., Zhang Y-C., Zhou T.: Identifying influential nodes in complex networks. Physica A 319 (2012), 1777–1787.
• 7. Crucitti P., Latora V., Marchiori M., Rapisarda A.: Efficiency of scale-free networks: error and attack tolerance. Physica A 320 (2003), 622–642.
• 8. Crucitti P., Latora V., MarchioriM., Rapisarda A.: Error and attack tolerance of complex networks. Physica A 340 (2004), 388–394.
• 9. Csardi G., Nepusz T.: The igraph software package for complex network research. InterJournal Complex Syst. 1695 (2006), http://igraph.org.
• 10. Estrada E.: The Structure of Complex Networks: Theory and Applications. Oxford Univ. Press, Oxford 2011.
• 11. Fei L., Zhang Q., Deng Y.: Identifying influential nodes in complex networks based on the inverse-square law. Physica A 512 (2018), 1044–1059.
• 12. Godsil C.D., Kocay W.L.: Constructing graphs with pairs of pseudo-similar vertices. J. Combin. Theory Ser B 32 (1982), 146–155.
• 13. He X., Meghanathan N.: Alternative to betweenness centrality: a measure of correlation coefficient. Proceedings of the Fifth Inernational Conference on Advanced Information Technologies and Application (2016), 1–10.
• 14. Holme P., Kim B.J., Yoon Ch.N., Han S.K.: Attack vulnerability of complex networks. Phys. Rev. E 65 (2002), 056109.
• 15. Ibnoulouafi A., El Haziti M.: Density centrality: identifying influential nodes based on area density formula. Chaos Soliton Fract. 114 (2018), 69–80.
• 16. 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.
• 17. Ivanciuc O., Balaban T.S., Balaban A.T.: Design of topological indices. Part 4*. Reciprocal distance matrix, related local vertex invariants and topological indices. J. Math. Chem. 12 (1993), 309–318.
• 18. Iyer S., Killingback T., Sundaram B., Wang Z.: Attack robustness and centrality of complex networks. PLoS ONE 8 (4), e59613.
• 19. Jeong H., Tombor B., Albert R., Oltvai Z.N., Barab´asi A-L.: The large-scale organization of metabolic networks. Nature 407 (2000), 651–654.
• 20. Jeong H., Manson S.P., Barabasi A.-L., Oltvai Z.N.: Lethality and centrality in protein networks. Nature 411 (2001), 41–42.
• 21. Kassambara A., Mundt F.: factoextra: Extract and visualize the results of multivariate data analyses. R package version 1.0.5 (2017). https://CRAN.R-project.org/package=factoextra.
• 22. KEGG: Kyoto Encyclopedia of Genes and Genomes. www.genome.jp/kegg/.
• 23. Kitsak M., Gallos L. K., Havlin S., Liljeros F., Muchnik L., Stanley H.E., Makse H.A.: Identification of influential spreaders in complex networks. Nature Phys. 6 (2010), 888–893.
• 24. Kobayashi T., Hasui K.: Efficient immunization strategies to prevent finantial contagion. Sci. Rep. 4 (2014), 3834.
• 25. Kosch˝utzki D., Lehman K.A., Peeters L., Richter S., Tenfelde-Podehl D., Zlotowski O.: Centrality indices. In: Network Analysis: Methodological Foundations. Brandes U., Erlebach T. (eds.), Springer, Berlin 2005.
• 26. Kosch˝utzki D., Junker B.H., Schwender J., Schreiber F.: Structural analysis of metabolic networks based on flux centrality. J. Theor. Biol. 265 (2010), 261–269.
• 27. Latora V., Nicosia V., Russo G.: Complex Networks. Principles, Methods and Applications. Cambridge Univ. Press, Cambridge 2017.
• 28. Lemke N., Her´edia F., Barcellos C.K., dos Reis A.N., Mombach J.C.M.: Essentiality and damage in metabolic networks. Bioinformatics 20 (2004), 115–119.
• 29. Li C., Li Q., van Mieghem P., Stanley H. E., Wang H.: Correlation between centrality metrics and their application to the opinion model. Eur. Phys. J. B 88 (2015), 65.
• 30. Marchiori M., Latora V.: Harmony in the small-world. Physica A 285 (2000), 539–546.
• 31. Melak T., Gakkhar S.: Comparative genome and network centrality analysis to identify drug targets of Mycobacterium tuberculosis H37Rv, BioMed Res. Int. 2015 (2015), 212061.
• 32. Quayle A.P., Siddiqui A.S., Jones S.J.M.: Preferential network perturbation. Physica A 371 (2006), 823–840.
• 33. Raab J., Milward H.B.: Dark networks as problems. J. Public Adm. Res. Theory 13 (2003), 413–439.
• 34. Randi´c M., Pisanski T., Noviˇc M., Plavˇsi´c D.: Novel graph distance matrix. J. Comput. Chem. 31 (2010), 1832–1841.
• 35. R Core Team: R: a language and environment for statistical computing. R foundation for Statistical Computing, Vienna 2017, http://www.R-project.org/.
• 36. Ren J., Wang J., Li M., Wu F.: Discovering essential proteins based on PPI network and protein complex. Int. J. Data Mining and Bioinformatics 12 (2015), 24–43.
• 37. Rochat Y.: Closeness centrality extended to unconnected graphs: the harmonic centrality index. Application of Social Networks Analysis, Zurich 2009.
• 38. Ronqui J.R.F., Travieso G.: Analyzing complex networks through correlations in centrality measurements. J. Stat. Mech.: Theory Exp. 2015 (2015), P05030
• 39. Shao C., Cui P., Xun P., Peng Y., Jiang X.: Rank correlation between centrality metrics in complex networks: an empirical study. Open Phys. 16 (2018), 1009–1023.
• 40. Tan S-Y., Wu J., Lu L., Li M-J, Lu X.: Efficient network disintegration under incomplete information: the comic effect of link prediction. Sci. Rep. 6 (2016), 22916.
• 41. Tripathy R.M., Bagchi A., Mehta S.: A study of rumor control strategies on social networks. CIKM’10 Proceedings of the 19th ACM Inernational conference on Information and Knowledge Management (2010), 1817–1820.
• 42. Wenli F., Zhigang L., Ping H.: Identifying node importance based on information entropy in complex networks. Phys. Scr. 88 (2013), 065201.
• 43. Wickham H.: ggplot2: Elegant Graphics for Data Analysis. Springer-Verlag, New York 2009.
• 44. Wilczek P.: https://github.com/PiotrWilczeknet/R-functions-1.
• 45. Wilczek P.: Novel centrality measures and distance-related topological indices in network data mining. Silesian J. Pure Appl. Math. 7 (2017), 21–63.
• 46. Wuchty S., Stadler P.F.: Centers of complex networks. J. Theor. Biol. 223 (2003), 45–53.
• 47. Xu H., Zhang J., Yang J., Lun L.: Identifying important nodes in complex networks based on multiattribute evaluation. Math. Probl. Eng. 2018 (2018), 8268436.
• 48. Yang C., Li F.: RevEcoR: Reverse ecology analysis on microbiome. R package version 0.99.3 (2016). https://CRAN.R-project.org/package=RevEcoR.
• 49. Zotenko E., Mestre J., O’Leary D.P., Przytycka T.M.: Why do hubs in the yeast protein interaction network tend to be essential: reaxamining the connection between the network topology and essentiality. PLoS Comput. Biol. 4, no. 8 (2008), e1000140.