×

zbMATH — the first resource for mathematics

A functorial Dowker theorem and persistent homology of asymmetric networks. (English) Zbl 1423.55038
Summary: We study two methods for computing network features with topological underpinnings: the Rips and Dowker persistent homology diagrams. Our formulations work for general networks, which may be asymmetric and may have any real number as an edge weight. We study the sensitivity of Dowker persistence diagrams to asymmetry via numerous theoretical examples, including a family of highly asymmetric cycle networks that have interesting connections to the existing literature. In particular, we characterize the Dowker persistence diagrams arising from asymmetric cycle networks. We investigate the stability properties of both the Dowker and Rips persistence diagrams, and use these observations to run a classification task on a dataset comprising simulated hippocampal networks. Our theoretical and experimental results suggest that Dowker persistence diagrams are particularly suitable for studying asymmetric networks. As a stepping stone for our constructions, we prove a functorial generalization of a theorem of Dowker, after whom our constructions are named.

MSC:
55U99 Applied homological algebra and category theory in algebraic topology
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
55N35 Other homology theories in algebraic topology
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Adamaszek, M.; Adams, H., The Vietoris-Rips complexes of a circle, Pac. J. Math., 290, 1-40, (2017) · Zbl 1366.05124
[2] Adamaszek, M.; Adams, H.; Frick, F.; Peterson, C.; Previte-Johnson, C., Nerve complexes of circular arcs, Discrete Comput. Geom., 56, 251-273, (2016) · Zbl 1354.05149
[3] Acemoglu, D.; Ozdaglar, A.; Tahbaz-Salehi, A., Systemic risk and stability in financial networks, Am. Econ. Rev., 105, 564-608, (2015)
[4] Atkin, RH, From cohomology in physics to q-connectivity in social science, Int. J. Man Mach. Stud., 4, 139-167, (1972)
[5] Atkin, R.: Mathematical Structure in Human Affairs. Crane, Russak, New York (1975)
[6] Barmak, J.A.: Algebraic Topology of Finite Topological Spaces and Applications, vol. 2032. Springer, Belrin (2011) · Zbl 1235.55001
[7] Burago, D., Burago, Y., Ivanov, S.: A Course in Metric Geometry, Volume 33 of AMS Graduate Studies in Mathematics. American Mathematical Society, Providence (2001) · Zbl 0981.51016
[8] Burghelea, D.; Dey, TK, Topological persistence for circle-valued maps, Discrete Comput. Geom., 50, 69-98, (2013) · Zbl 1275.55009
[9] Björner, A., Topological methods, Handb. Comb., 2, 1819-1872, (1995) · Zbl 0851.52016
[10] Björner, A.; Korte, B.; Lovász, L., Homotopy properties of greedoids, Adv. Appl. Math., 6, 447-494, (1985) · Zbl 0642.05014
[11] Bauer, U., Lesnick, M.: Induced matchings of barcodes and the algebraic stability of persistence. In: Proceedings of the Thirtieth Annual Symposium on Computational Geometry, p. 355. ACM, London (2014) · Zbl 1395.68289
[12] Barabási, A-L; Oltvai, ZN, Network biology: understanding the cell’s functional organization, Nat. Rev. Genet., 5, 101-113, (2004)
[13] Carlsson, G., Topology and data, Bull. Am. Math. Soc., 46, 255-308, (2009) · Zbl 1172.62002
[14] Chazal, F., Cohen-Steiner, D., Glisse, M., Guibas, L.J., Oudot, S.Y: Proximity of persistence modules and their diagrams. In: Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, pp. 237-246. ACM, London (2009) · Zbl 1380.68387
[15] Chazal, Frédéric; Cohen-Steiner, David; Guibas, Leonidas J.; Mémoli, Facundo; Oudot, Steve Y., Gromov-Hausdorff Stable Signatures for Shapes using Persistence, Computer Graphics Forum, 28, 1393-1403, (2009)
[16] Chowdhury, S., Dai, B., Mémoli, F.: The importance of forgetting: limiting memory improves recovery of topological characteristics from neural data (2017). arXiv preprint arXiv:1710.11279
[17] Chowdhury, S., Dai, B., Mémoli, F.: Topology of stimulus space via directed network persistent homology. Cosyne Abstracts 2017 (2017)
[18] Carlsson, G.; Silva, V., Zigzag persistence, Found. Comput. Math., 10, 367-405, (2010) · Zbl 1204.68242
[19] Chazal, F., De Silva, V., Glisse, M., Oudot, S.: The Structure and Stability of Persistence Modules. Springer, Berlin (2016) · Zbl 1362.55002
[20] Chazal, F.; Silva, V.; Oudot, S., Persistence stability for geometric complexes, Geom. Dedic., 173, 193-214, (2014) · Zbl 1320.55003
[21] Carstens, CJ; Horadam, KJ, Persistent homology of collaboration networks, Math. Problems Eng., 2013, 815035, (2013) · Zbl 1299.91104
[22] Curto, C.; Itskov, V., Cell groups reveal structure of stimulus space, PLoS Comput. Biol., 4, e1000205, (2008)
[23] Carlsson, G., Mémoli, F.: Persistent clustering and a theorem of J. Kleinberg (2008). arXiv preprint arXiv:0808.2241
[24] Carlsson, G.; Mémoli, F., Characterization, stability and convergence of hierarchical clustering methods, J. Mach. Learn. Res., 11, 1425-1470, (2010) · Zbl 1242.62050
[25] Chowdhury, S., Mémoli, F.: Metric structures on networks and applications. In: 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1470-1472 (2015)
[26] Chowdhury, S., Mémoli, F.: Distances between directed networks and applications. In: 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6420-6424. IEEE, Washington (2016)
[27] Chowdhury, S., Mémoli, F.: Persistent homology of directed networks. In: 2016 50th Asilomar Conference on Signals, Systems and Computers, pp. 77-81. IEEE, Washington (2016)
[28] Chowdhury, S., Mémoli, F.: Distances and isomorphism between networks and the stability of network invariants (2017). arXiv preprint arXiv:1708.04727
[29] Chowdhury, Samir; Mémoli, Facundo, Persistent Path Homology of Directed Networks, 1152-1169, (2018), Philadelphia, PA · Zbl 1403.68154
[30] Carlsson, G.E., Mémoli, F., Ribeiro, A., Segarra, S.: Hierarchical quasi-clustering methods for asymmetric networks. In: Proceedings of the 31th International Conference on Machine Learning, pp. 352-360 (2014)
[31] Chazal, F., Oudot, S.Y: Towards persistence-based reconstruction in Euclidean spaces. In: Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry, pp. 232-241. ACM, New York (2008) · Zbl 1271.57058
[32] Cohen-Steiner, D.; Edelsbrunner, H.; Harer, J., Stability of persistence diagrams, Discrete Comput. Geom., 37, 103-120, (2007) · Zbl 1117.54027
[33] Collins, A.; Zomorodian, A.; Carlsson, G.; Guibas, LJ, A barcode shape descriptor for curve point cloud data, Comput. Graph., 28, 881-894, (2004)
[34] Carlsson, G.; Zomorodian, A.; Collins, A.; Guibas, LJ, Persistence barcodes for shapes, Int. J. Shape Model., 11, 149-187, (2005) · Zbl 1092.68688
[35] Dey, T.K., Fan, F., Wang, Y.: Computing topological persistence for simplicial maps. In: Proceedings of the Thirtieth Annual Symposium on Computational Geometry, pp. 345. ACM, London (2014) · Zbl 1395.68299
[36] Dłotko, P., Hess, K., Levi, R., Nolte, M., Reimann, M., Scolamiero, M., Turner, K., Muller, E., Markram, H.: Topological analysis of the connectome of digital reconstructions of neural microcircuits (2016). arXiv preprint arXiv:1601.01580
[37] Dantchev, S.; Ivrissimtzis, I., Efficient construction of the Čech complex, Comput. Graph., 36, 708-713, (2012)
[38] Dabaghian, Y.; Mémoli, F.; Frank, L.; Carlsson, G., A topological paradigm for hippocampal spatial map formation using persistent homology, PLoS Comput. Biol., 8, e1002581, (2012)
[39] Dowker, CH, Homology groups of relations, Ann. Math., 56, 84-95, (1952) · Zbl 0046.40402
[40] De Silva, V., Carlsson, G.: Topological estimation using witness complexes. In: Proceedings of the Symposium on Point-Based Graphics, pp. 157-166 (2004)
[41] Elliott, M.; Golub, B.; Jackson, MO, Financial networks and contagion, Am Econ Rev, 104, 3115-3153, (2014)
[42] Edelsbrunner, H.; Harer, J., Persistent homology—a survey, Contemp Math, 453, 257-282, (2008) · Zbl 1145.55007
[43] Edelsbrunner, H., Harer, J.: Computational Topology: An Introduction. American Mathematical Soc, Providence (2010) · Zbl 1193.55001
[44] Efrat, A.; Itai, A.; Katz, MJ, Geometry helps in bottleneck matching and related problems, Algorithmica, 31, 1-28, (2001) · Zbl 0980.68101
[45] Edelsbrunner, H.; Jabłoński, G.; Mrozek, M., The persistent homology of a self-map, Found. Comput. Math., 15, 1213-1244, (2015) · Zbl 1330.55009
[46] Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York (2010) · Zbl 1205.91007
[47] Edelsbrunner, H.; Letscher, D.; Zomorodian, A., Topological persistence and simplification, Discrete Comput. Geom., 28, 511-533, (2002) · Zbl 1011.68152
[48] Edelsbrunner, H., Morozov, D.: Persistent homology: theory and practice. In: European Congress of Mathematics Kraków, 2-7 July, 2012, pp. 31-50 (2014) · Zbl 1364.55008
[49] Engström, A., Complexes of directed trees and independence complexes, Discrete Math., 309, 3299-3309, (2009) · Zbl 1226.05084
[50] Edelsbrunner, H., Wagner, H.: Topological data analysis with Bregman divergences (2017) · Zbl 1436.55008
[51] Frosini, P.; Landi, C., Size theory as a topological tool for computer vision, Pattern Recogn. Image Anal., 9, 596-603, (1999)
[52] Frosini, P.: Measuring shapes by size functions. In: Intelligent Robots and Computer Vision X: Algorithms and Techniques, pp. 122-133. International Society for Optics and Photonics (1992)
[53] Ghrist, R., Barcodes: the persistent topology of data, Bull. Am. Math. Soc., 45, 61-75, (2008) · Zbl 1391.55005
[54] Ghrist, R.: Elementary Applied Topology. Createspace, Scotts Valley (2014)
[55] Giusti, C.; Pastalkova, E.; Curto, C.; Itskov, V., Clique topology reveals intrinsic geometric structure in neural correlations, Proc. Natl. Acad. Sci., 112, 13455-13460, (2015) · Zbl 1355.92015
[56] Horak, D.; Maletić, S.; Rajković, M., Persistent homology of complex networks, J. Stat. Mech. Theory Exp., 2009, p03034, (2009)
[57] Hiraoka, Y.; Nakamura, T.; Hirata, A.; Escolar, EG; Matsue, K.; Nishiura, Y., Hierarchical structures of amorphous solids characterized by persistent homology, Proc. Natl. Acad. Sci., 113, 7035-7040, (2016)
[58] Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press, Cambridge (2010)
[59] Johnson, J.: Hypernetworks in the Science of Complex Systems, vol. 3. World Scientific, Singapore (2013) · Zbl 1296.94001
[60] Khalid, A.; Kim, BS; Chung, MK; Ye, JC; Jeon, D., Tracing the evolution of multi-scale functional networks in a mouse model of depression using persistent brain network homology, NeuroImage, 101, 351-363, (2014)
[61] Kumar, Ravi; Novak, Jasmine; Tomkins, Andrew, Structure and Evolution of Online Social Networks, 337-357, (2010), New York, NY
[62] Kalton, NJ; Ostrovskii, MI; Fliess, M. (ed.), Distances between Banach spaces, No. 11, 17-48, (1999), Berlin
[63] Kozlov, D.: Combinatorial Algebraic Topology, vol. 21. Springer, Berlin (2007) · Zbl 1130.55001
[64] Krishnamoorthy, B.; Provan, S.; Tropsha, A.; Pardalos, PM (ed.); Boginski, VL (ed.); Alkis, V. (ed.), A topological characterization of protein structure, 431-455, (2007), Berlin
[65] Lee, Hyekyoung; Chung, Moo K.; Kang, Hyejin; Kim, Boong-Nyun; Lee, Dong Soo, Computing the Shape of Brain Networks Using Graph Filtration and Gromov-Hausdorff Metric, 302-309, (2011), Berlin, Heidelberg
[66] Lefschetz, S.: Algebraic Topology, vol. 27. American Mathematical Soc, Providence (1942) · Zbl 0061.39302
[67] Masys, A.J.: Networks and Network Analysis for Defence and Security. Springer, Berlin (2014)
[68] Mac Lane, S.: Categories for the Working Mathematician, vol. 5. Springer, Berlin (2013) · Zbl 0232.18001
[69] Munkres, J.R.: Elements of Algebraic Topology, vol. 7. Addison-Wesley, Reading (1984) · Zbl 0673.55001
[70] Newman, MEJ, The structure and function of complex networks, SIAM Rev., 45, 167-256, (2003) · Zbl 1029.68010
[71] Dowker’s theorem. https://ncatlab.org/nlab/show/Dowker%27s+theorem. Accessed 24 Apr 2017
[72] O’Keefe, J.; Dostrovsky, J., The hippocampus as a spatial map. Preliminary evidence from unit activity in the freely-moving rat, Brain Res., 34, 171-175, (1971)
[73] Pessoa, L., Understanding brain networks and brain organization, Phys. Life Rev., 11, 400-435, (2014)
[74] Petri, G.; Scolamiero, M.; Donato, I.; Vaccarino, F., Topological strata of weighted complex networks, PLoS ONE, 8, e66506, (2013)
[75] Robins, V., Towards computing homology from finite approximations, Topol. Proc., 24, 503-532, (1999) · Zbl 1026.55009
[76] Rubinov, M.; Sporns, O., Complex network measures of brain connectivity: uses and interpretations, NeuroImage, 52, 1059-1069, (2010)
[77] Schmiedl, F.: Shape matching and mesh segmentation. Dissertation, Technische Universität München, München (2015)
[78] Sporns, O.; Kötter, R., Motifs in brain networks, PLoS Biol., 2, e369, (2004)
[79] Spanier, E.H.: Algebraic Topology, vol. 55. Springer, Berlin (1994) · Zbl 0810.55001
[80] Sporns, O.: Networks of the Brain. MIT Press, Cambridge (2011) · Zbl 1093.92028
[81] Sporns, O.: Discovering the Human Connectome. MIT Press, Cambridge (2012)
[82] Turner, K.: Generalizations of the Rips filtration for quasi-metric spaces with persistent homology stability results (2016). arXiv preprint arXiv:1608.00365
[83] Tausz, A., Vejdemo-Johansson, M., Adams, H.: Javaplex: a research software package for persistent (co)homology (2011) · Zbl 1402.65186
[84] Weinberger, S., What is... persistent homology?, Not. AMS, 58, 36-39, (2011) · Zbl 1232.55002
[85] Xia, K.; Wei, G-W, Persistent homology analysis of protein structure, flexibility, and folding, Int. J. Numer. Methods Biomed. Eng., 30, 814-844, (2014)
[86] Zomorodian, A.; Carlsson, G., Computing persistent homology, Discrete Comput. Geom., 33, 249-274, (2005) · Zbl 1069.55003
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.