×

Persistent homology of geospatial data: a case study with voting. (English) Zbl 1460.62201

Summary: A crucial step in the analysis of persistent homology is the transformation of data into an appropriate topological object (which, in our case, is a simplicial complex). Software packages for computing persistent homology typically construct Vietoris-Rips or other distance-based simplicial complexes on point clouds because they are relatively easy to compute. We investigate alternative methods of constructing simplicial complexes and the effects of making associated choices during simplicial-complex construction on the output of persistent-homology algorithms. We present two new methods for constructing simplicial complexes from two-dimensional geospatial data (such as maps). We apply these methods to a California precinct-level voting data set, and we thereby demonstrate that our new constructions can capture geometric characteristics that are missed by distance-based constructions. Our new constructions can thus yield more interpretable persistence modules and barcodes for geospatial data. In particular, they are able to distinguish short-persistence features that occur only for a narrow range of distance scales (e.g., voting patterns in densely populated cities) from short-persistence noise by incorporating information about other spatial relationships between regions.

MSC:

62P25 Applications of statistics to social sciences
62R40 Topological data analysis
62M30 Inference from spatial processes
55N31 Persistent homology and applications, topological data analysis
55U10 Simplicial sets and complexes in algebraic topology
91D20 Mathematical geography and demography
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Adamaszek and H. Adams, The Vietoris-Rips complexes of a circle, Pacific J. Math., 290 (2017), pp. 1-40. · Zbl 1366.05124
[2] H. Adams, T. Emerson, M. Kirby, R. Neville, C. Peterson, P. Shipman, S. Chepushtanova, E. Hanson, F. Motta, and L. Ziegelmeier, Persistence images: A stable vector representation of persistent homology, J. Mach. Learn. Res., 18 (2017), pp. 218-252. · Zbl 1431.68105
[3] P. Bajardi, M. Delfino, A. Panisson, G. Petri, and M. Tizzoni, Unveiling patterns of international communities in a global city using mobile phone data, European Phys. J. Data Sci., 4 (2015), art. 3.
[4] A. Banman and L. Ziegelmeier, Mind the gap: A study in global development through persistent homology, in Research in Computational Topology, E. W. Chambers, B. T. Fasy, and L. Ziegelmeier, eds., Springer International Publishing, Cham, Switzerland, 2018, pp. 125-144.
[5] R. Barnes and J. Solomon, Gerrymandering and Compactness: Implementation Flexibility and Abuse, preprint, https://arxiv.org/abs/1803.02857, 2018.
[6] U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner, Phat-Persistent homology algorithms toolbox, in Mathematical Software-ICMS 2014, H. Hong and C. Yap, eds., Springer-Verlag, Heidelberg, Germany, 2014, pp. 137-143. · Zbl 1402.65187
[7] P. Bendich, H. Edelsbrunner, D. Morozov, and A. Patel, Homology and robustness of level and interlevel sets, Homology Homotopy Appl., 15 (2013), pp. 51-72. · Zbl 1266.55004
[8] O. Bobrowski, S. Mukherjee, and J. E. Taylor, Topological consistency via kernel estimation, Bernoulli, 23 (2017), pp. 288-328. · Zbl 1395.62073
[9] P. Bubenik, Statistical topological data analysis using persistence landscapes, J. Mach. Learn. Res., 16 (2015), pp. 77-102. · Zbl 1337.68221
[10] P. Bubenik, M. Hull, D. Patel, and B. Whittle, Persistent homology detects curvature, Inverse Problems, 36 (2020), art. 025008. · Zbl 1508.55004
[11] H. M. Byrne, H. A. Harrington, R. Muschel, G. Reinert, B. J. Stolz, and U. Tillmann, Topology characterises tumour vasculature, Math. Today, 55 (2019), pp. 206-210.
[12] G. Carlsson, Topological methods for data modelling, Nat. Rev. Phys., 2 (2020), pp. 697-708
[13] G. Carlsson, T. Ishkhanov, V. de Silva, and A. Zomorodian, On the local behavior of spaces of natural images, Internat. J. Comput. Vision, 76 (2008), pp. 1-12. · Zbl 1477.68463
[14] C. Curto, What can topology tell us about the neural code?, Bull. Amer. Math. Soc., 54 (2017), pp. 63-78. · Zbl 1353.92027
[15] M. Duchin and B. E. Tenner, Discrete Geometry for Electoral Geography, preprint, https://arxiv.org/abs/1808.05860, 2018.
[16] H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, AMS, Providence, RI, 2010. · Zbl 1193.55001
[17] H. Edelsbrunner, D. Kirkpatrick, and R. Seidel, On the shape of a set of points in the plane, IEEE Trans. Inform. Theory, 29 (1983), pp. 551-559. · Zbl 0512.52001
[18] K. Emmett, B. Schweinhart, and R. Rabadan, Multiscale topology of chromatin folding, in Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies (Formerly BIONETICS), BICT ’15, ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2016, pp. 177-180.
[19] R. Ghrist, Barcodes: The persistent topology of data, Bull. Amer. Math. Soc., 45 (2008), pp. 61-75. · Zbl 1391.55005
[20] F. Gibou, R. Fedkiw, and S. Osher, A review of level-set methods and some recent applications, J. Comput. Phys., 353 (2018), pp. 82-109. · Zbl 1380.65196
[21] The Gudhi Project, Gudhi User and Reference Manual, Version 3.0.0, Gudhi Editorial Board, 2015, https://gudhi.inria.fr/doc/3.0.0/.
[22] C. Giusti, R. Ghrist, and D. S. Bassett, Two’s company, three (or more) is a simplex, J. Comput. Neurosci., 41 (2016), pp. 1-14.
[23] A. Hatcher, Algebraic Topology, Cambridge University Press, Cambridge, UK, 2002. · Zbl 1044.55001
[24] D. P. Humphreys, M. R. McGuirl, M. Miyagi, and A. J. Blumberg, Fast estimation of recombination rates using topological data analysis, Genetics, 211 (2019), pp. 1191-1204.
[25] P. S. P. Ignacio and I. K. Darcy, Tracing patterns and shapes in remittance and migration networks via persistent homology, European Phys. J. Data Sci., 8 (2019), art. 1.
[26] L. Kanari, P. Dłotko, M. Scolamiero, R. Levi, J. C. Shillcock, K. Hess, and H. Markram, A topological representation of branching neuronal morphologies, Neuroinform., 16 (2018), pp. 3-13.
[27] M. Kerber and R. Sharathkumar, Approximate Čech Complex in Low and High Dimensions, preprint, https://arxiv.org/abs/1307.3272, 2013. · Zbl 1406.68119
[28] M. Kramár, A. Goullet, L. Kondic, and K. Mischaikow, Quantifying force networks in particulate systems, Phys. D, 283 (2014), pp. 37-55. · Zbl 1349.74083
[29] R. Kwitt, S. Huber, M. Niethammer, W. Lin, and U. Bauer, Statistical topological data analysis-A kernel perspective, in Advances in Neural Information Processing Systems 28, C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, eds., Curran Associates, 2015, pp. 3070-3078.
[30] D. Lo and B. Park, Modeling the spread of the Zika virus using topological data analysis, PLoS ONE, 13 (2018), art. e0192120.
[31] C. Maria, Filtered complexes, in Gudhi User and Reference Manual, Version 3.0.0, Gudhi Editorial Board, 2015, https://gudhi.inria.fr/doc/3.0.0/group__simplex__tree.html.
[32] C. Maria, P. Dłotko, V. Rouvreau, and M. Glisse, Rips complex, in Gudhi User and Reference Manual, Version 3.0.0, Gudhi Editorial Board, 2016, https://gudhi.inria.fr/doc/3.0.0/group__rips__complex.html.
[33] M. E. J. Newman, Networks, 2nd ed., Oxford University Press, Oxford, UK, 2018. · Zbl 1391.94006
[34] S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Appl. Math. Sci. 153, Springer-Verlag, Heidelberg, Germany, 2003. · Zbl 1026.76001
[35] S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79 (1988), pp. 12-49. · Zbl 0659.65132
[36] N. Otter, M. A. Porter, U. Tillmann, P. Grindrod, and H. A. Harrington, A roadmap for the computation of persistent homology, European Phys. J. Data Sci., 6 (2017), art. 17.
[37] L. Papadopoulos, M. A. Porter, K. E. Daniels, and D. S. Bassett, Network analysis of particles and grains, J. Complex Networks, 6 (2018), pp. 485-565.
[38] QGIS Association, QGIS 2.18.17: A Free and Open Source Geographic Information System, 2016, http://www.qgis.org.
[39] J. Reininghaus, S. Huber, U. Bauer, and R. Kwitt, A stable multi-scale kernel for topological machine learning, in 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015, pp. 4741-4748.
[40] J. W. Rocks, A. J. Liu, and E. Katifori, The Topological Basis of Function in Flow Networks, preprint, https://arxiv.org/abs/1901.00822, 2019.
[41] H. Ronellenfitsch, J. Lasser, D. C. Daly, and E. Katifori, Topological phenotypes constitute a new dimension in the phenotypic space of leaf venation networks, PLOS Comput. Biol., 11 (2015), art. e1004680.
[42] V. Rouvreau, Alpha complex, in Gudhi User and Reference Manual, Version 3.0.0, Gudhi Editorial Board, 2015, https://gudhi.inria.fr/doc/3.0.0/group__alpha__complex.html.
[43] V. Rouvreau, Python interface, in Gudhi User and Reference Manual, Version 3.0.0, Gudhi Editorial Board, 2016, https://gudhi.inria.fr/python/3.0.0.
[44] J. Schleuss, J. Fox, and P. Krishnakumar, California 2016 Election Precinct Maps, https://github.com/datadesk/california-2016-election-precinct-maps, 2016. (See https://www.latimes.com/projects/la-pol-ca-california-neighborhood-election-results/ for the associated newspaper article.)
[45] L. Speidel, H. A. Harrington, S. J. Chapman, and M. A. Porter, Topological data analysis of continuum percolation with disks, Phys. Rev. E, 98 (2018), art. 012318.
[46] B. J. Stolz, H. A. Harrington, and M. A. Porter, The Topological “Shape” of Brexit, preprint, https://arxiv.org/abs/1610.00752, 2016.
[47] B. J. Stolz, H. A. Harrington, and M. A. Porter, Persistent homology of time-dependent functional networks constructed from coupled time series, Chaos, 27 (2017), art. 047410.
[48] D. Taylor, F. Klimm, H. A. Harrington, M. Kramár, K. Mischaikow, M. A. Porter, and P. J. Mucha, Topological data analysis of contagion maps for examining spreading processes on networks, Nature Commun., 6 (2015), art. 7723.
[49] L. Vietoris, Über den höheren zusammenhang kompakter räume und eine klasse von zusammenhangstreuen abbildungen, Math. Ann., 97 (1927), pp. 454-472. · JFM 53.0552.01
[50] K. Xia and G.-W. Wei, Persistent homology analysis of protein structure, flexibility, and folding, Internat. J. Numer. Methods Biomed. Engrg., 30 (2014), pp. 814-844.
[51] W. Zhou and H. Yan, Alpha shape and Delaunay triangulation in studies of protein-related interactions, Briefings Bioinform., 15 (2014), pp. 54-64.
[52] X. Zhu, A. Vartanian, M. Bansal, D. Nguyen, and L. Brandl, Stochastic multiresolution persistent homology kernel, in Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI ’16, AAAI Press, 2016, pp. 2449-2455.
[53] A. Zomorodian, Fast construction of the Vietoris-Rips complex, Computers & Graphics, 34 (2010), pp. 263-271.
[54] A. Zomorodian and G. Carlsson, Computing persistent homology, Discrete Comput. Geom., 33 (2005), pp. 249-274. · 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. 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.