CENTRALITY METRICS FOR IDENTIFYING NETWORK FRAGILITY IN PROTEIN-PROTEIN INTERACTION NETWORKS AND SYNTHESIZED NK SYSTEMS

Ken A. Hawick

View Full Paper

References

  1. [1] Abdo, A.H., de Moura, A.P.S.: Clustering as a measure ofthe local topology of networks. Tech. rep., Universidade deS˜ao Paulo, University of Aberdeen (February 2006), http://arxiv.org/abs/physics/0605235v4
  2. [2] Baillie, C.F., Johnston, D.: Damaging 2d quantum gravity.Physics Letters B 326, 51–56 (1994)
  3. [3] Baillie, C., Hawick, K., Johnston, D.: Quenching 2d quan-tum gravity. Physics Letters B 328(3-4), 284–290 (June1994)
  4. [4] Barabasi, A.L., Oltvai, Z.N.: Network biology: Under-standing the cell’s functional organization. Nature Reviews- Genetiocs 5, 101–113 (2004)
  5. [5] Barrat, A., Barthelemy, M., Pastor-Satorras, R., Vespignani,A.: The architecture of complex weighted networks. PNAS101(11), 3747–3752 (2004), http://www.pnas.org/cgi/content/abstract/101/11/3747
  6. [6] Blomberg, C.: Physics of Life - The Physicist’s Road toBiology. No. ISBN 978-0-444-52798-1, Elsevier (2007)29
  7. [7] Blossey, R.: Computational Biology A Statistical Mechan-ics Perspective. No. ISBN 1-58488-556-4, Chapman andHall (2006)
  8. [8] Brandes, U.: A faster algorithm for betweenness central-ity. The Journal of Mathematical Sociology 25(2), 163–177(2010)
  9. [9] Butland, G., Peregrin-Alvarez, J.M., Li, J., Yang, W., Yang,X., Canadien, V., Starostine, A., Richards, D., Beattie, B.,Krogan, N., Davey, M., Parkinson, J., Greenblatt, J., Emili,A.: Interaction network containing conserved and essentialprotein complexes in escherichia coli. Nature 433, 531–537(February 2005)
  10. [10] Caflisch, A.: Protein folding: Simple models for a complexprocess. Structure 12, 1750–1752 (2004)
  11. [11] Choen, J.: Bioinformatics - an introduction for computerscientists. ACM Computing Surveys 36(2), 122–158 (June2004)
  12. [12] Clauset, A.: Finding local community structure in networks.Phys. Rev. E 72, 026132–1–6 (2005)
  13. [13] Cordero, F., Manini, D., Gribaudo, M., Balbo, G.: Anew framework for modeling complex biological systems:user?s manual. Ricercatore - Universita degli Studi diTorino, Dipartimento di Informatica, Corso Svizzera 185 -10149 Torino (Italy) (2011), http://www.di.unito.it/?manini/OBAM-Tool-Draw/
  14. [14] COSIN: Complexity in networks - european project coevo-lution and self-organization in dynamical networks (cosin).http://www.cosinproject.org/ (August 2011)
  15. [15] Darabos, C., Tomassini, M., Cunto, F.D., Provero, P.,Moore, J.H., Giacobini, M.: Toward robust network basedcomplex systems: from evolutionary cellular automata tobiological models. Intelligenza Artificiale 5, 37–47 (2011)
  16. [16] Derrida, B., Pomeau, Y.: Random networks of automata: Asimple annealed approximation. Europhys. Lett. 1(2), 45–49(1986)
  17. [17] Derrida, B., Stauffer, D.: Phase transitions in two-dimensional Kauffman cell automata. Europhys. Lett. 2, 739(1986)
  18. [18] Dijkstra, E.W.: A note on two problems in connection withgraphs. Numerische Mathematik 1, 269–271 (1959)
  19. [19] Dijkstra, E.: A Note on Two Problems in Connexion withGraphs. Numerische Mathematik 1(1), 269–271 (1959)
  20. [20] Ebden, J.H., Phillips, C.A., Rogers, G.L., Langston, M.A.:The maximum clique enumeration problem: Algorithms,applications and implementations. In: Proc. ISBRA 2011.pp. 306–319. No. 6674 in LNBI, Springer (2011)
  21. [21] ElisabethWong, Baur, B., Quader, S., Huang, C.H.: Biolog-ical network motif detection: principles and practice. Brief-ings in Bioinformatics June, 1–14 (2011)
  22. [22] Everett, M., Borgatti, S.P.: Ego network betweenness. So-cial Networks 27, 31–38 (2005)
  23. [23] Fenyo, D. (ed.): Computational Biology. No. ISBN 978-160-7618-416, Springer, NY, USA. (2010)
  24. [24] Ferraro, N., Palopoli, L., Panni, S., Rombo, S.E.: Asym-metric comparison and querying of biological networks.IEEE/ACM Trans. Computational Biology and Bioinfor-matics 8, 876–889 (2011)
  25. [25] Floyd, R.W.: Algorithm 97: Shortest Path. Communicationsof the ACM 5(6), 345 (1962)
  26. [26] Freeman, L.C.: Centrality in social networks conceptualclarification. Social Networks 1, 215–239 (1978)
  27. [27] Freeman, L.C., Borgatti, S.P., White, D.R.: Centrality in val-ued graphs: A measure of betweenness based on networkflow. Social Networks 13, 141–154 (1991)
  28. [28] Gershenson, C.: Introduction to random boolean networks.Tech. Rep. arXiv.org:nlin/0408006v3, Vrije UniversiteitBrussel (August 2004)
  29. [29] Girvan, M., Newman, M.E.J.: Community structure in so-cial and biological networks. Proc. Nat. Acad. Sci. 99,7821–7826 (2002)
  30. [30] Goldberg, A.V.: A simple shortest path algorithm with lin-ear average time. In: Proc. 9th Annual European Sympo-sium on Algorithms. pp. 230–241 (2001)
  31. [31] Hagburg, A., Schult, D., Swart, P.: NetworkX Reference(4 August 2013), https://networkx.github.io/,release 1.8.1
  32. [32] Harvey, I., Bossomaier, T.: Time out of joint: Attractorsin asynchronous random boolean networks. In: Husbands,P., Harvey, I. (eds.) Proc Fourth European Conference onArtificial Life (ECAL97). pp. 67–75. MIT Press (1997)
  33. [33] Hawick, K.A.: Eigenvalue spectra measurements of com-plex networks. In: H.Arabnia (ed.) Proc. Int. Conf on Scien-tific Computing (CSC’08). pp. 174–179. CSREA, Las Vegas(14-17 July 2008)
  34. [34] Hawick, K.A.: Detecting and labelling wireless commu-nity network structures from eigen-spectra. In: Proc. Inter-national Conference on Wireless Networks (ICWN’10). pp.398–404. WorldComp, Las Vegas, USA (12-15 July 2010),iCW5189
  35. [35] Hawick, K.A.: Interactive Graph Algorithm Visualizationand the GraViz Prototype. Tech. Rep. CSTN-061, ComputerScience, Massey University, Albany, North Shore 102-904,Auckland, New Zealand (October 2010), www.massey.ac.nz/˜kahawick/cstn/061/cstn-061.pdf
  36. [36] Hawick, K.A.: Applying enumerative, spectral and hybridgraph analyses to biological network data. In: Int. Conf. onComputational Intelligence and Bioinformatics (CIB 2011).pp. 89–96. IASTED, Pittsburgh, USA (7-9 November 2011)
  37. [37] Hawick, K.A.: Betweenness centrality metrics for assess-ing electrical power network robustness against fragmenta-tion and node failure. In: Proc. International Conference onPower and Energy Systems (EuroPES 2012). pp. 186–193.IASTED, Napoli, Italy. (25-27 June 2012)
  38. [38] Hawick, K.A.: Node-failure and islanding in national gridscale electricity distribution networks. In: Proc. Int. Conf.Power and Energy Systems and Applications. pp. 52–58.IASTED, Las Vegas (12-14 November 2012)
  39. [39] Hawick, K.A.: Water distribution network robustness andfragmentation using graph metrics. In: Proc. Int. Conf.on Water Resource Management (AfricaWRM 2012). pp.304–310. No. 762-037, IASTED, Gabarone, Botswana (3-5September 2012), cSTN-158
  40. [40] Hawick, K.A., James, H.A.: Managing community mem-bership information in a small-world grid. Research Let-ters in the Information and Mathematical Sciences 7(CSTN-002), 101–115 (March 2005), iSSN 1175-2777
  41. [41] Hawick, K.A., James, H.A.: Node importance ranking andscaling properties of some complex road networks. Tech.Rep. CSTN-021, Computer Science, Massey University, Al-bany, North Shore 102-904, Auckland, New Zealand (Au-gust 2005)
  42. [42] Hawick, K.A., James, H.A., Scogings, C.J.: Structural Cir-cuits and Attractors in Kauffman Networks. In: Abbass,H.A., Randall, M. (eds.) Proc. Third Australian Conference30on Artificial Life. LNCS, vol. 4828, pp. 189–200. Springer,Gold Coast, Australia (4-6 December 2007), 978-3-540-76930-9
  43. [43] Hawick, K.A., Leist, A., Playne, D.P.: Parallel Graph Com-ponent Labelling with GPUs and CUDA. Parallel Comput-ing 36(12), 655–678 (December 2010), www.elsevier.com/locate/parco
  44. [44] Hines, P., Blumsack, S.: A centrality measure for electricalnetworks. In: Proc. 41st Hawaii Int. Conf. on System Sci-ences. pp. 1–8. HICSS, Hawaii, Big Island (7-10 January2008)
  45. [45] Jamil, H.: Computing subgraph isomorphic queries usingstructural unification and minimum graph structures. In:Proc. SAC 2011, Taichung, Taiwan. pp. 1053–1058 (2011)
  46. [46] Joy, M.P., Brock, A., Ingber, D.E., Huang, S.: High-betweenness proteins in the yeast protein interaction net-work. Journal of Biomedecine and Biotechnology 2, 96–103(2005)
  47. [47] Kadanoff, L., Coppersmith, S., Aldana, M.: Boolean dy-namics with random couplings. In: Kaplan, E., Marsden, J.,Sreenivasan, K. (eds.) Perspectives and Problems in Nonlin-ear Science. Springer (2003)
  48. [48] Kauffman, S.A.: The Origins of Order. Oxford UniversityPress (1993)
  49. [49] Kauffman, S., Peterson, C., Samuelsson, B., Troein, C.:Random boolean network models and the yeast transcrip-tional network. Proc. Natl. Acad. Sci. USA 100, 14796(2003)
  50. [50] Mattiussi, C., Durr, P., Marbach, D., Floreano, D.: Beyondgraphs: A new synthesis. Journal of Computational Science2, 165–177 (2011)
  51. [51] Mueller, L.A.J., Kugler, K.G., Dander, A., Graber, A.,Dehmer, M.: Quacn: an r package for analyzing complexbiological networks quantitatively. Bioinformatics 27, 140–141 (2011)
  52. [52] Muff, S., Rao, F., Caflisch, A.: Local modularity measurefor network clusterizations. Phys. Rev. E 72, 056107 (2005)
  53. [53] Nacher, J.C., Ueda, N., Yamada, T., Kanehisa, M., Akutsu,T.: Study on the clustering coeffcients in metabolic net-work using a hierarchical framework. In: Fourth Interna-tional Workshop on Bioinformatics and Systems Biology.pp. 34–35. Kyoto, Japan (31 May - 3 June 2004)
  54. [54] Nepusz, T., Setany, P.P.: iGraph. Budapest, Hungary(4 February 2014), http://igraph.org/python/doc/python-igraph.pdf, version 0.7.0
  55. [55] Newman, M.E.J.: Models of the small world: A review.Journal of Statistical Physics 101, 819–841 (2000)
  56. [56] Newman, M., Girvan, M.: Finding and evaluating commu-nity structure in networks. Phys. Rev. E 69, 026113 (2004)
  57. [57] Pal, D., Rao, P.R.: A tool for fast indexing and queryingof graphs. In: Proc. Int. World Wide Web Conf. (IW3C2),Hyderabad, India, 2011. pp. 241–244 (28 March - 1 April2011)
  58. [58] Prim, R.: Shortest connection networks and some gener-alizations. The Bell System Technical Journal November,1389–1401 (1957)
  59. [59] Rao, F., Caflisch, A.: The protein folding network. J. Mol.Biol. 342, 299–306 (2004)
  60. [60] Rao, F.: Theoretical and Computational Studies of Pro-tein Folding Energy Landscapes. Ph.D. thesis, University ofZurich (2005)
  61. [61] Ravasz, E., Somera, A.L., Mongru, D.A., Oltvai, Z.N.,Barabasi, A.L.: Hierarchical organization of modularity inmetabolic networks. Science 297, 1551–1555 (2002)
  62. [62] Samatova, N.F., Schmidt, M.C., Hendrix, W., Breimyer, P.,Thomas, K., Park, B.H.: Coupling graph perturbation the-ory with scalable parallel algorithms for large-scale enu-meration of maximal cliques in biological graphs. Journalof Physics: Conf. Series 125, 012053–1–7 (2008)
  63. [63] Schank, T., Wagner, D.: Approximating clustering coefi-cient and transitivity. Journal of Graph Algorithms ad Ap-plications 9(2), 265–275 (2005)
  64. [64] Schietgat, L.: Graph-based data mining for biological appli-cations. AI Communications 24, 95–96 (2011)
  65. [65] Settanni, G., Fersht, A.R.: High temperature unfolding sim-ulations of the trpz1 peptide. Biophys J. BioFAST 94(11),4444–4453 (June 2008)
  66. [66] Sevon, P., Eronen, L., Hintsanen, P., Kulovesi, K., Toivo-nen, H.: Link discovery in graphs derived from biologicaldatabases. In: Proc. 3rd Int. Workshop on Data Integrationin the Life Sciences (DILS 2006). pp. 35–49 (2006)
  67. [67] Team, J.D.: Java Universal Graph/Network Framework(JUNG2) (22 April 2009), http://sourceforge.net/apps/trac/jung/wiki/JUNGManual, version2.0
  68. [68] Tizghadam, A., Leon-Garcia, A.: Betweenness centralityand resistance distance in communication networks. IEEENetwork Nov/Dec, 10–16 (2010)
  69. [69] Toivonen, H., Zhou, F., Hartikainen, A., Hinkka, A.: Com-pression of weighted graphs. In: Proc. 17th ACM SIGKDDConference on Knowledge Discovery and Data Mining(KDD), San Diego, CA, USA. pp. 1–9 (August 2011)
  70. [70] UCLA: Database of interacting proteins (dip). http://dip.doe-mbi.ucla.edu/dip/ (August 2011)
  71. [71] Wolfram, S.: Theory and Applications of Cellular Au-tomata. World Scientific (1986)
  72. [72] Wuchty, S., Ravasz, E., Barabasi, A.L.: The architec-ture of biological networks. In: Proc. Complex Systems inBiomedecine. pp. 1–30. Kluwer (2003)
  73. [73] Yang, M., Li, R., Chu, T.: Construction of a boolean modelof gene and protein regulatory network with memory. Neu-ral Networks 52, 18–24 (2014)
  74. [74] yWorks: yed - java graph editor (2008), http://www.yworks.com/
  75. [75] Zertuche, F.: On the robustness of nk-kauffman networksagainst changes in their connections and boolean functions.J. Math. Phys. 50, 043513 (2009)
  76. [76] Zgeng, G., Jiang, M., He, X., Zhao, J., Guo, H., Chen,G., Zha, Q., Lu, A.: Discrete derivative: a data slicing al-gorithm for exploration of sharing biological networks be-tween rheumatoid arthritis and coronary heart disease. Bio-Data Mining 4, 1–21 (2011), www.biodatamining.org/content/4/1/18
  77. [77] Zhou, W., Nakhleh, L.: Properties of metabolic graphs: bio-logical organization or representation artifacts? BMC Bioin-formatics 12, 1–12 (2011)
  78. [78] Zhou, Z.: Using expansion algorithm to identify proteinfrom biological networks. Journal of Convergence Informa-tion Technology 6, 63–69 (2011)
  79. [79] Zhu, L., Ng, W.K., Cheng, J.: Structure and attribute indexfor approximate graph matching in large graphs. Informa-tion Systems 36, 958–972 (2011)

Important Links:

Go Back