Graph pseudometrics from a topological point of view. (English) Zbl 1498.05080
Gasparovic, Ellen (ed.) et al., Research in computational topology 2. Proceedings of the second women in computational topology, WinCompTop, research collaboration workshop, Mathematical Sciences Institute, MSI, Australian National University, ANU, Canberra, Australia, July 1–5, 2019. Cham: Springer. Assoc. Women Math. Ser. 30, 99-128 (2022).
Summary: We explore pseudometrics for directed graphs in order to better understand their topological properties. The directed flag complex associated to a directed graph provides a useful bridge between network science and topology. Indeed, it has often been observed that phenomena exhibited by real-world networks reflect the topology of their flag complexes, as measured, for example, by Betti numbers or simplex counts. As it is often computationally expensive (or even unfeasible) to determine such topological features exactly, it would be extremely valuable to have pseudometrics on the set of directed graphs that can both detect the topological differences and be computed efficiently. To facilitate work in this direction, we introduce methods to measure how well a graph pseudometric captures the topology of a directed graph. We then use these methods to evaluate some well-established pseudometrics, using test data drawn from several families of random graphs.
For the entire collection see [Zbl 1487.55002].
For the entire collection see [Zbl 1487.55002].
MSC:
| 05C12 | Distance in graphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C20 | Directed graphs (digraphs), tournaments |
References:
| [1] | Adamaszek, M.; Stacho, J., Complexity of simplicial homology and independence complexes of chordal graphs, Comput. Geom. Theory Appl., 57, 8-18 (2016) · Zbl 1386.65086 · doi:10.1016/j.comgeo.2016.05.003 |
| [2] | Bagrow, JP; Bollt, EM, An information-theoretic, all-scales approach to comparing networks, Appl. Netw. Sci., 4, 1, 45 (2019) · doi:10.1007/s41109-019-0156-x |
| [3] | Bagrow, J.P., Bollt, E.M., Skufca, J.D., ben Avraham, D.: Portraits of complex networks. Europhys. Lett. 81(6), 68004 (2008) |
| [4] | Benjamini, Y.; Yekutieli, D., The control of the false discovery rate in multiple testing under dependency, Ann. Stat., 29, 4, 1165-1188 (2001) · Zbl 1041.62061 · doi:10.1214/aos/1013699998 |
| [5] | Bobrowski, O.; Kahle, M., Topology of random geometric complexes: a survey, J. Appl. Comput. Topol., 1, 331-363 (2018) · Zbl 1402.60015 · doi:10.1007/s41468-017-0010-0 |
| [6] | Chowdhury, S., Mémoli, F.: Persistent path homology of directed networks. In: Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (2018) · Zbl 1403.68154 |
| [7] | Fowlkes, EB; Mallows, CL, A method for comparing two hierarchical clusterings, J. Am. Stat. Assoc., 78, 383, 553-569 (1983) · Zbl 0545.62042 · doi:10.1080/01621459.1983.10478008 |
| [8] | Giusti, C.; Pastalkova, E.; Curto, C.; Itskov, V., Clique topology reveals intrinsic geometric structure in neural correlations, Proc. Natl. Acad. Sci. U. S. A., 112, 44, 13455-13460 (2015) · Zbl 1355.92015 · doi:10.1073/pnas.1506407112 |
| [9] | Giusti, C.; Ghrist, R.; Bassett, DS, Two’s company, three (or more) is a simplex, J. Comput. Neurosci., 41, 1, 1-14 (2016) · doi:10.1007/s10827-016-0608-6 |
| [10] | Grigor’yan, A.; Lin, Y.; Muranov, Y.; Yau, ST, Path complexes and their homologies, J. Math. Sci., 248, 564-599 (2020) · Zbl 1448.05171 · doi:10.1007/s10958-020-04897-9 |
| [11] | Hatcher, A., Algebraic Topology (2002), Cambridge: Cambridge University Press, Cambridge · Zbl 1044.55001 |
| [12] | Jones, E., Oliphant, T., Peterson, P., et al.: SciPy: Open source scientific tools for Python (2001). http://www.scipy.org/ |
| [13] | Kahle, M.; Meckes, E., Limit the theorems for Betti numbers of random simplicial complexes, Homology Homotopy Appl., 15, 1, 343-374 (2013) · Zbl 1268.05180 · doi:10.4310/HHA.2013.v15.n1.a17 |
| [14] | Kriege, N.M., Johansson, F.D., Morris, C.: A survey on graph kernels. Appl. Netw. Sci. 5(1) (2020) |
| [15] | Lasalle, E.: Topological analysis of random graphs in the context of neuroscience. Unpublished report (2019) |
| [16] | Luetgehetmann, D., Govc, D., Smith, J., Levi, R.: Computing persistent homology of directed flag complexes. Preprint (2019). arXiv:1906.10458 |
| [17] | Lyons, R., Distance covariance in metric spaces, Ann. Probab., 41, 5, 3284-3305 (2013) · Zbl 1292.62087 · doi:10.1214/12-AOP803 |
| [18] | Masulli, P., Villa, A.E.P.: The topology of the directed clique complex as a network invariant. SpringerPlus 5(1) (2016) |
| [19] | Munkres, JR, Elements of Algebraic Topology (1984), Redwood City: Addison-Wesley, Redwood City · Zbl 0673.55001 |
| [20] | Newman, M., Networks (2018), Oxford: Oxford University Press, Oxford · Zbl 1391.94006 · doi:10.1093/oso/9780198805090.001.0001 |
| [21] | Nikolentzos, G., Siglidis, G., Vazirgiannis, M.: Graph kernels: A survey. Preprint (2019). arXiv:1904.12218 · Zbl 1522.68477 |
| [22] | Przulj, N., Biological network comparison using graphlet degree distribution, Bioinformatics, 26, 6, 853-854 (2010) · doi:10.1093/bioinformatics/btq091 |
| [23] | Pržulj, N.; Corneil, DG; Jurisica, I., Modeling interactome: scale-free or geometric?, Bioinformatics, 20, 18, 3508-3515 (2004) · doi:10.1093/bioinformatics/bth436 |
| [24] | Reimann, MW; Nolte, M.; Scolamiero, M.; Turner, K.; Perin, R.; Chindemi, G.; Dłotko, P.; Levi, R.; Hess, K.; Markram, H., Cliques of neurons bound into cavities provide a missing link between structure and function, Front. Comput. Neurosci., 11, 48 (2017) · doi:10.3389/fncom.2017.00048 |
| [25] | Rousseeuw, PJ, Silhouettes: A graphical aid to the interpretation and validation of cluster analysis, J. Comput. Appl. Math., 20, 53-65 (1987) · Zbl 0636.62059 · doi:10.1016/0377-0427(87)90125-7 |
| [26] | Sarajlić, A., Malod-Dognin, N., Yaveroğlu, Ö.N., Pržulj, N.: Graphlet-based characterization of directed networks. Sci. Rep. 6(1) (2016) |
| [27] | Shen, C.; Priebe, CE; Vogelstein, JT, From distance correlation to multiscale graph correlation, J. Am. Stat. Assoc., 115, 529, 280-291 (2020) · Zbl 1437.62210 · doi:10.1080/01621459.2018.1543125 |
| [28] | Sizemore, A.; Giusti, C.; Bassett, DS, Classification of weighted networks through mesoscale homological features, J. Complex Networks., 5, 2, 245-273 (2017) |
| [29] | Sizemore, AE; Giusti, C.; Kahn, A.; Vettel, JM; Betzel, RF; Bassett, DS, Cliques and cavities in the human connectome, J. Comput. Neurosci., 44, 1, 115-145 (2018) · Zbl 1402.92119 · doi:10.1007/s10827-017-0672-6 |
| [30] | Székely, GJ; Rizzo, ML; Bakirov, NK, Measuring and testing dependence by correlation of distances, Ann. Stat., 35, 6, 2769-2794 (2007) · Zbl 1129.62059 · doi:10.1214/009053607000000505 |
| [31] | Tantardini, M., Ieva, F., Tajoli, L., Piccardi, C.: Comparing methods for comparing networks. Sci. Rep. 9(1) (2019) |
| [32] | Tauzin, G., Lupo, U., Tunstall, L., Perez, J.B., Caorsi, M., Reise, W., Medina-Mardones, A.M., Dassatti, A., Hess, K.: giotto-tda: A topological data analysis toolkit for machine learning and data exploration. In: NeurIPS 2020 Workshop on Topological Data Analysis and Beyond (2020) · Zbl 1541.68324 |
| [33] | Turner, K., Spreemann, G.: Same but different: Distance correlations between topological summaries. Preprint (2019). arXiv:1903.01051 · Zbl 1450.62141 |
| [34] | Wegner, AE; Ospina-Forero, L.; Gaunt, RE; Deane, CM; Reinert, G., Identifying networks with common organizational principles, J. Complex Networks, 6, 6, 887-913 (2018) · doi:10.1093/comnet/cny003 |
| [35] | Xu, X.; Reinert, G.; Aiello, LM; Cherifi, C.; Cherifi, H.; Lambiotte, R.; Lió, P.; Rocha, LM, Triad-based comparison and signatures of directed networks, Complex Networks and Their Applications VII. Complex Networks 2018. Studies in Computational Intelligence, 590-602 (2018), Berlin: Springer International Publishing, Berlin |
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.
