Network distances for weighted digraphs. (English) Zbl 1458.90167
Kochetov, Yury (ed.) et al., Mathematical optimization theory and operations research. 19th international conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020. Revised selected papers. Cham: Springer. Commun. Comput. Inf. Sci. 1275, 389-408 (2020).
Summary: The interpretation of the biological mechanisms through the systems biology approach involves the representation of the molecular components in an integrated system, namely a network, where the interactions among them are much more informative than the single components. The definition of the dissimilarity between complex biological networks is fundamental to understand differences between conditions, states, and treatments. It is, therefore, challenging to identify the most suitable distance measures for this kind of analysis. In this work, we aim at testing several measures to define the distance among sample- and condition-specific metabolic networks. The networks are represented as directed, weighted graphs, due to the nature of the metabolic reactions. We used four different case studies and exploited Support Vector Machine classification to define the performance of each measure.
For the entire collection see [Zbl 1454.90004].
For the entire collection see [Zbl 1454.90004].
MSC:
| 90B10 | Deterministic network models in operations research |
| 68M10 | Network design and communication in computer systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C22 | Signed and weighted graphs |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
Software:
igraph; KEGG; WEKA; DirectedClustering; philentropy; MetaboX; profvis; RStudio; NetworkDistanceReferences:
| [1] | Bartlett, J., et al.: Comparing breast cancer multiparameter tests in the OPTIMA prelim trial: no test is more equal than the others. JNCI J. Natl. Cancer Inst. 108(9), djw050 (2016) · doi:10.1093/jnci/djw050 |
| [2] | Carpi, L., et al.: Assessing diversity in multiplex networks. Sci. Rep. 9(1), 1-12 (2019) |
| [3] | Cha, S.H.: Comprehensive survey on distance/similarity measures between probability density functions. Int. J. Math. Models Methods Appl. Sci. 1(4), 300-307 (2007) |
| [4] | Chang, W., Luraschi, J., Mastny, T.: profvis: Interactive Visualizations for Profiling R Code (2019). https://CRAN.R-project.org/package=profvis. r package version 0.3.6 |
| [5] | Clemente, G.P., Grassi, R.: DirectedClustering: Directed Weighted Clustering Coefficient (2018). https://CRAN.R-project.org/package=DirectedClustering. r package version 0.1.1 |
| [6] | Clemente, G., Grassi, R.: Directed clustering in weighted networks: a new perspective. Chaos Solitons Fractals 107, 26-38 (2018) · doi:10.1016/j.chaos.2017.12.007 |
| [7] | Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms, 2nd edn. McGraw-Hill Higher Education, New York (2001) · Zbl 1047.68161 |
| [8] | Csardi, G., Nepusz, T.: The igraph software package for complex network research. InterJournal Complex Syst. 1695 (2006). http://igraph.org |
| [9] | Dehmer, M., Mowshowitz, A.: A history of graph entropy measures. Inf. Sci. 181(1), 57-78 (2011) · Zbl 1204.94050 · doi:10.1016/j.ins.2010.08.041 |
| [10] | Deza, E., Deza, M.M. (eds.): Dictionary of Distances. Elsevier, Amsterdam (2006) · Zbl 1351.51001 |
| [11] | Donnat, C., Holmes, S.: Tracking network dynamics: a survey using graph distances. Ann. Appl. Stat. 12(2), 971-1012 (2018) · Zbl 1405.62171 · doi:10.1214/18-AOAS1176 |
| [12] | Emmert-Streib, F., Dehmer, M., Shi, Y.: Fifty years of graph matching, network alignment and network comparison. Inf. Sci. 346(C), 180-197 (2016) · Zbl 1398.68393 · doi:10.1016/j.ins.2016.01.074 |
| [13] | Endres, D.M., Schindelin, J.E.: A new metric for probability distributions. IEEE Trans. Inf. Theory 49(7), 1858-1860 (2003) · Zbl 1294.62003 · doi:10.1109/TIT.2003.813506 |
| [14] | Costa, L.d.F., Rodrigues, F.A., Travieso, G., Boas, P.R.V.: Characterization of complex networks: a survey of measurements. Adv. Phys. 56, 167-242 (2007) |
| [15] | Fagiolo, G.: Clustering in complex directed networks. Phys. Rev. E 76, 026107 (2007) · doi:10.1103/PhysRevE.76.026107 |
| [16] | Granata, I., Guarracino, M., Kalyagin, V., Maddalena, L., Manipur, I., Pardalos, P.: Supervised classification of metabolic networks. In: IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018, Madrid, Spain, 3-6 December 2018, pp. 2688-2693 (2018) · Zbl 1436.62254 |
| [17] | Granata, I., Guarracino, M.R., Kalyagin, V.A., Maddalena, L., Manipur, I., Pardalos, P.M.: Model simplification for supervised classification of metabolic networks. Ann. Math. Artif. Intell. 88(1), 91-104 (2019). https://doi.org/10.1007/s10472-019-09640-y · Zbl 1436.62254 · doi:10.1007/s10472-019-09640-y |
| [18] | Granata, I., Guarracino, M.R., Maddalena, L., Manipur, I., Pardalos, P.M.: On network similarities and their applications. In: Mondaini, R.P. (ed.) BIOMAT 2019, pp. 23-41. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-46306-9_3 · Zbl 1480.92087 · doi:10.1007/978-3-030-46306-9_3 |
| [19] | Granata, I., Troiano, E., Sangiovanni, M., Guarracino, M.: Integration of transcriptomic data in a genome-scale metabolic model to investigate the link between obesity and breast cancer. BMC Bioinformatics 20(4), 162 (2019) · doi:10.1186/s12859-019-2685-9 |
| [20] | Guzzi, P., Milenković, T.: Survey of local and global biological network alignment: the need to reconcile the two sides of the same coin. Brief. Bioinform. 19(3), 472-481 (2017) |
| [21] | Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., Witten, I.H.: The WEKA data mining software: an update. SIGKDD Explor. 11(1), 10-18 (2009) · doi:10.1145/1656274.1656278 |
| [22] | Hammond, D.K., Gur, Y., Johnson, C.R.: Graph diffusion distance: a difference measure for weighted graphs based on the graph Laplacian exponential kernel. In: 2013 IEEE Global Conference on Signal and Information Processing, pp. 419-422, December 2013 |
| [23] | Dorst, H.G.: Philentropy: information theory and distance quantification with R. J. Open Source Softw. 3(26), 765 (2018). http://joss.theoj.org/papers/10.21105/joss.00765 · doi:10.21105/joss.00765 |
| [24] | Jaccard, P.: Étude comparative de la distribution florale dans une portion des alpes et des jura. Bulletin del la Société Vaudoise des Sciences Naturelles 37, 547-579 (1901) |
| [25] | Jurman, G., Visintainer, R., Filosi, M., Riccadonna, S., Furlanello, C.: The HIM glocal metric and kernel for network comparison and classification. In: 2015 IEEE International Conference on Data Science and Advanced Analytics (DSAA), pp. 1-10 (2015) |
| [26] | Kalyagin, V.A., Pardalos, P.M., Rassias, T.M. (eds.): Network Models in Economics and Finance. SOIA, vol. 100. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09683-4 · Zbl 1302.91003 · doi:10.1007/978-3-319-09683-4 |
| [27] | Konstantinos, G., et al.: Network Design and Optimization for Smart Cities, vol. 8. World Scientific, Singapore (2017) |
| [28] | Latora, V., Marchiori, M.: Efficient behavior of small-world networks. Phys. Rev. Lett. 87, 198701 (2001) · Zbl 1060.91520 · doi:10.1103/PhysRevLett.87.198701 |
| [29] | Liu, Q., Dong, Z., Wang, E.: Cut based method for comparing complex networks. Sci. Rep. 8(1), 1-11 (2018) |
| [30] | Maiorano, F., Ambrosino, L., Guarracino, M.R.: The MetaboX library: building metabolic networks from KEGG database. In: Ortuño, F., Rojas, I. (eds.) IWBBIO 2015. LNCS, vol. 9043, pp. 565-576. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16483-0_55 · doi:10.1007/978-3-319-16483-0_55 |
| [31] | Mueller, L.A.J., Dehmer, M., Emmert-Streib, F.: Comparing biological networks: a survey on graph classifying techniques. In: Prokop, A., Csukás, B. (eds.) Systems Biology, pp. 43-63. Springer, Dordrecht (2013). https://doi.org/10.1007/978-94-007-6803-1_2 · doi:10.1007/978-94-007-6803-1_2 |
| [32] | Opsahl, T., Panzarasa, P.: Clustering in weighted networks. Soc. Netw. 31(2), 155-163 (2009) · doi:10.1016/j.socnet.2009.02.002 |
| [33] | Parker, J.S., et al.: Supervised risk predictor of breast cancer based on intrinsic subtypes. J. Clin. Oncol. 27(8), 1160 (2009) · doi:10.1200/JCO.2008.18.1370 |
| [34] | Pavlopoulos, G.A., et al.: Using graph theory to analyze biological networks. BioData Min. 4(1), 10 (2011) · doi:10.1186/1756-0381-4-10 |
| [35] | Platt, J.: Fast training of support vector machines using sequential minimal optimization. In: Schoelkopf, B., Burges, C., Smola, A. (eds.) Advances in Kernel Methods - Support Vector Learning. MIT Press, Cambridge (1998) |
| [36] | RStudio Team: RStudio: Integrated Development Environment for R. RStudio Inc, Boston (2019). http://www.rstudio.com/ |
| [37] | Ruan, D., Young, A., Montana, G.: Differential analysis of biological networks. BMC Bioinformatics 16, 1-13 (2015) · doi:10.1186/s12859-015-0735-5 |
| [38] | Saramäki, J., Kivelä, M., Onnela, J.P., Kaski, K., Kertész, J.: Generalizations of the clustering coefficient to weighted complex networks. Phys. Rev. E 75, 027105 (2007) · doi:10.1103/PhysRevE.75.027105 |
| [39] | Schieber, T., Carpi, L., Díaz-Guilera, A., Pardalos, P., Masoller, C., Ravetti, M.: Quantification of network structural dissimilarities. Nat. Commun. 8(1), 1-10 (2017) |
| [40] | Tsuda, K., Saigo, H.: Graph classification. In: Aggarwal, C., Wang, H. (eds.) Managing and Mining Graph Data. Advances in Database Systems, vol. 40, pp. 337-363. Springer, Boston (2010). https://doi.org/10.1007/978-1-4419-6045-0_11 · Zbl 1185.68458 · doi:10.1007/978-1-4419-6045-0_11 |
| [41] | You, K.: NetworkDistance: Distance Measures for Networks (2019). https://CRAN.R-project.org/package=NetworkDistance. r package version 0.3.2 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
