×

zbMATH — the first resource for mathematics

Topological graph persistence. (English) Zbl 07293737
Summary: Graphs are a basic tool in modern data representation. The richness of the topological information contained in a graph goes far beyond its mere interpretation as a one-dimensional simplicial complex. We show how topological constructions can be used to gain information otherwise concealed by the low-dimensional nature of graphs. We do this by extending previous work in homological persistence, and proposing novel graph-theoretical constructions. Beyond cliques, we use independent sets, neighborhoods, enclaveless sets and a Ramsey-inspired extended persistence.

MSC:
55N31 Persistent homology and applications, topological data analysis
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 1. D. Alberici, P. Contucci, E. Mingione, and M. Molari. Aggregation models on hypergraphs. Annals of Physics, 376:412-424, 2017. · Zbl 1364.82071
[2] 2. M. G. Bergomi, M. Ferri, and A. Tavaglione. Steady and ranging sets in graph persistence. arXiv preprint arXiv:2009.06897, 2020.
[3] 3. M. G. Bergomi, M. Ferri, P. Vertechi, and L. Zu . Beyond topological persistence: Starting from networks. arXiv preprint arXiv:1901.08051, 2019.
[4] 4. M. G. Bergomi and P. Vertechi. Rank-based persistence. Theory and Applications of Categories, 35(9):228-260, 2020.
[5] 5. A. Bondy and U. Murty. Graph Theory. Graduate Texts in Mathematics. Springer London, 2011.
[6] 6. R. Boppana and M. M. Halldórsson. Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2):180-196, 1992. · Zbl 0761.68044
[7] 7. G. Carlsson. Topology and data. Bull. Amer. Math. Soc., 46(2):255-308, 2009.
[8] 8. F. Chazal, D. Cohen-Steiner, M. Glisse, L. J. Guibas, and S. Y. Oudot. Proximity of persistence modules and their diagrams. In SCG ’09: Proceedings of the 25th annual symposium on Computational geometry, pages 237-246, New York, NY, USA, 2009. ACM. · Zbl 1380.68387
[9] 9. S. Chowdhury and F. Mémoli. Persistent homology of asymmetric networks: An approach based on dowker filtrations. arXiv preprint arXiv:1608.05432, 2016. · Zbl 1423.55038
[10] 10. S. Chowdhury and F. Mémoli. Persistent path homology of directed networks. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1152-1169. SIAM, 2018. · Zbl 1403.68154
[11] 11. D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discr.Comput. Geom., 37(1):103-120, 2007. · Zbl 1117.54027
[12] 12. D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Extending persistence using Poincaré and Lefschetz duality. Foundations of Computational Mathematics, 9(1):79-103, 2009. · Zbl 1189.55002
[13] 13. M. d’Amico, P. Frosini, and C. Landi. Using matching distance in size theory: A survey. Int. J. Imag. Syst. Tech., 16(5):154-161, 2006.
[14] 14. M. d’Amico, P. Frosini, and C. Landi. Natural pseudo-distance and optimal matching between reduced size functions. Acta Applicandae Mathematicae, 109(2):527-554, 2010. · Zbl 1198.68224
[15] 15. P. Dłotko, K. Hess, R. Levi, M. Nolte, M. Reimann, M. Scolamiero, K. Turner, E. Muller, and H. Markram. Topological analysis of the connectome of digital reconstructions of neural microcircuits. arXiv preprint arXiv:1601.01580, 2016.
[16] 16. C. H. Dowker. Homology groups of relations. Annals of mathematics, pages 84-95, 1952. · Zbl 0046.40402
[17] 17. H. Edelsbrunner and J. Harer. Persistent homology—a survey. In Surveys on discrete and computational geometry, volume 453 of Contemp. Math., pages 257-282. Amer. Math. Soc., Providence, RI, 2008. · Zbl 1145.55007
[18] 18. H. Edelsbrunner and J. Harer. Computational Topology: An Introduction. American Mathematical Society, 2009. · Zbl 1193.55001
[19] 19. A.-H. Esfahanian. Connectivity algorithms. In Topics in structural graph theory, pages 268-281. Cambridge University Press, 2013.
[20] 20. P. Frosini and C. Landi. Size theory as a topological tool for computer vision. Pattern Recognition and Image Analysis, 9(4):596-603, 1999.
[21] 21. C. Giusti, R. Ghrist, and D. S. Bassett. Two’s company, three (or more) is a simplex. Journal of computational neuroscience, 41(1):1-14, 2016.
[22] 22. C. Giusti, E. Pastalkova, C. Curto, and V. Itskov. Clique topology reveals intrinsic geometric structure in neural correlations. Proceedings of the National Academy of Sciences, 112(44):13455-13460, 2015. · Zbl 1355.92015
[23] 23. A. Hagberg, P. Swart, and D. S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
[24] 24. A. Hatcher. Algebraic Topology. Algebraic Topology. Cambridge University Press, 2002. · Zbl 1044.55001
[25] 25. D. Horak, S. Maletić, and M. Rajković. Persistent homology of complex networks. Journal of Statistical Mechanics: Theory and Experiment, 2009(03):P03034, 2009. · Zbl 1459.55004
[26] 26. W. Huang and A. Ribeiro. Persistent homology lower bounds on high-order network distances. IEEE Transactions on Signal Processing, 65(2):319-334, 2017. · Zbl 1414.94255
[27] 27. R. Jayaraman, G. Raja, A. K. Bashir, C. S. Hussain, A. Hassan, and M. A. Alqarni. Interference mitigation based on radio aware channel assignment for wireless mesh networks. Wireless Personal Communications, 101(3):1539-1557, 2018.
[28] 28. J. Jonsson. Simplicial complexes of graphs, volume 3. Springer, 2008. · Zbl 1152.05001
[29] 29. C. Landi and P. Frosini. New pseudodistances for the size function space. In R. A. Melter, A. Y. Wu, and L. J. Latecki, editors, Proceedings SPIE, Vision Geometry VI, volume 3168, pages 52-60, 1997.
[30] 30. M. Lesnick. The theory of the interleaving distance on multidimensional persistence modules. Foundations of Computational Mathematics, pages 1-38, 2015. · Zbl 1335.55006
[31] 31. L.-D. Lord, P. Expert, H. M. Fernandes, G. Petri, T. J. Van Hartevelt, F. Vaccarino, G. Deco, F. Turkheimer, and M. L. Kringelbach. Insights into brain architectures from the homological sca olds of functional connectivity networks. Frontiers in Systems Neuroscience, 10, 2016.
[32] 32. L. Lovász. Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3):319-324, 1978. · Zbl 0418.05028
[33] 33. S. Maletić, M. Rajković, and D. Vasiljević. Simplicial complexes of networks and their statistical properties. In International Conference on Computational Science, pages 568-575. Springer, 2008.
[34] 34. S. Maletić, Y. Zhao, and M. Rajković. Persistent topological features of dynamical systems. Chaos: An Interdisciplinary Journal of Nonlinear Science, 26(5):053105, 2016. · Zbl 1361.37068
[35] 35. P. Masulli and A. E. Villa. The topology of the directed clique complex as a network invariant. SpringerPlus, 5(1):388, 2016.
[36] 36. E. I. Moser, E. Krop , and M.-B. Moser. Place cells, grid cells, and the brain’s spatial representation system. Annu. Rev. Neurosci., 31:69-89, 2008.
[37] 37. S. Pal, T. J. Moore, R. Ramanathan, and A. Swami. Comparative topological signatures of growing collaboration networks. In Workshop on Complex Networks CompleNet, pages 201-209. Springer, 2017.
[38] 38. G. Petri, M. Scolamiero, I. Donato, and F. Vaccarino. Topological strata of weighted complex networks. PloS one, 8(6):e66506, 2013.
[39] 39. T. Pino, S. Choudhury, and F. Al-Turjman. Dominating set algorithms for wireless sensor networks survivability. IEEE Access, 6:17527-17532, 2018.
[40] 40. E. Prisner. Convergence of iterated clique graphs. Discrete Mathematics, 103(2):199-207, 1992. · Zbl 0766.05096
[41] 41. F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, s2-30(1):264-286, 1930. · JFM 55.0032.04
[42] 42. M. W. Reimann, M. Nolte, M. Scolamiero, K. Turner, R. Perin, G. Chindemi, P. Dłotko, R. Levi, K. Hess, and H. Markram. Cliques of neurons bound into cavities provide a missing link between structure and function. Frontiers in Computational Neuroscience, 11:48, 2017.
[43] 43. C. Shannon. The zero error capacity of a noisy channel. IRE Transactions on Information Theory, 2(3):8-19, 1956.
[44] 44. G. Singh, F. Mémoli, and G. E. Carlsson. Topological methods for the analysis of high dimensional data sets and 3d object recognition. In SPBG, pages 91-100, 2007.
[45] 45. A. Sizemore, C. Giusti, and D. S. Bassett. Classification of weighted networks through mesoscale homological features. Journal of Complex Networks, 5(2):245-273, 2017.
[46] 46. A. E. Sizemore, C. Giusti, A. Kahn, J. M. Vettel, R. F. Betzel, and D. S. Bassett. Cliques and cavities in the human connectome. Journal of Computational Neuroscience, 44(1):115-145, Feb 2018. · Zbl 1402.92119
[47] 47. E. H. Spanier. Algebraic topology, volume 55. Springer Science & Business Media, 1994. · Zbl 0145.43303
[48] 48. R. Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2):146-160, 1972. · Zbl 0251.05107
[49] 49. E. Tomita, A. Tanaka, and H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science, 363(1):28-42, 2006. · Zbl 1153.68398
[50] 50. K. Turner. Rips filtrations for quasimetric spaces and asymmetric functions with stability results. Algebraic & Geometric Topology, 19(3):1135-1170, 2019. · Zbl 1434.55002
[51] 51. A. Verri, C. Uras, P. Frosini, and M. Ferri. On the use of size functions for shape analysis. Biol. Cybern., 70:99-107, 1993. · Zbl 0789.92030
[52] 52. D. J. Watts and S. H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440, 1998. · Zbl 1368.05139
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.