Document Open Access Logo

An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology

Authors Tamal K. Dey, Tianqi Li, Yusu Wang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.36.pdf
  • Filesize: 0.84 MB
  • 15 pages

Document Identifiers

Author Details

Tamal K. Dey
  • Department of Computer Science and Engineering, The Ohio State University, Columbus, OH, 43210, USA
Tianqi Li
  • Department of Computer Science and Engineering, The Ohio State University, Columbus, OH, 43210, USA
Yusu Wang
  • Department of Computer Science and Engineering, The Ohio State University, Columbus, OH, 43210, USA

Funding

This work is in part supported by National Science Foundation under grants CCF1740761, DMS-1547357, and RI-1815697.

Cite As Get BibTex

Tamal K. Dey, Tianqi Li, and Yusu Wang. An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.36

Abstract

This paper focuses on developing an efficient algorithm for analyzing a directed network (graph) from a topological viewpoint. A prevalent technique for such topological analysis involves computation of homology groups and their persistence. These concepts are well suited for spaces that are not directed. As a result, one needs a concept of homology that accommodates orientations in input space. Path-homology developed for directed graphs by Grigoryan, Lin, Muranov and Yau has been effectively adapted for this purpose recently by Chowdhury and Mémoli. They also give an algorithm to compute this path-homology. Our main contribution in this paper is an algorithm that computes this path-homology and its persistence more efficiently for the 1-dimensional (H₁) case. In developing such an algorithm, we discover various structures and their efficient computations that aid computing the 1-dimensional path-homology. We implement our algorithm and present some preliminary experimental results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • computational topology
  • directed graph
  • path homology
  • persistent path homology

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 199-208. ACM, 2009. Google Scholar
  2. Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. Fast matrix rank algorithms and applications. Journal of the ACM (JACM), 60(5):31, 2013. Google Scholar
  3. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing, 14(1):210-223, 1985. Google Scholar
  4. Samir Chowdhury and Facundo Mémoli. A functorial dowker theorem and persistent homology of asymmetric networks. Journal of Applied and Computational Topology, 2(1-2):115-175, 2018. Google Scholar
  5. Samir Chowdhury and Facundo 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. Google Scholar
  6. David Cohen-Steiner, Herbert Edelsbrunner, and Dmitriy Morozov. Vines and vineyards by updating persistence in linear time. In Proceedings of the twenty-second annual symposium on Computational geometry, pages 119-126. ACM, 2006. Google Scholar
  7. Tamal K Dey, Tianqi Li, and Yusu Wang. Efficient algorithms for computing a minimal homology basis. In Latin American Symposium on Theoretical Informatics, pages 376-398, 2018. Google Scholar
  8. Pawel Dlotko, Kathryn Hess, Ran Levi, Max Nolte, Michael Reimann, Martina Scolamiero, Katharine Turner, Eilif Muller, and Henry Markram. Topological analysis of the connectome of digital reconstructions of neural microcircuits. arXiv preprint, 2016. URL: http://arxiv.org/abs/1601.01580.
  9. Jeff Erickson and Kim Whittlesey. Greedy optimal homotopy and homology generators. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1038-1046. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  10. Alexander Grigor'yan, Yong Lin, Yuri Muranov, and Shing-Tung Yau. Homologies of path complexes and digraphs. arXiv preprint, 2012. URL: http://arxiv.org/abs/1207.2834.
  11. Alexander Grigor'yan, Yong Lin, Yuri Muranov, and Shing-Tung Yau. Homotopy theory for digraphs. arXiv preprint, 2014. URL: http://arxiv.org/abs/1407.0234.
  12. Alexander Grigor’yan, Yong Lin, Yuri Muranov, and Shing-Tung Yau. Cohomology of digraphs and (undirected) graphs. Asian J. Math, 19(5):887-931, 2015. Google Scholar
  13. F. Harary. Graph Theory. Addison Wesley series in mathematics. Addison-Wesley, 1971. URL: https://books.google.com/books?id=q8OWtwEACAAJ.
  14. Paolo Masulli and Alessandro EP Villa. The topology of the directed clique complex as a network invariant. SpringerPlus, 5(1):388, 2016. Google Scholar
  15. Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824-827, 2002. Google Scholar
  16. Lav R Varshney, Beth L Chen, Eric Paniagua, David H Hall, and Dmitri B Chklovskii. Structural properties of the caenorhabditis elegans neuronal network. PLoS computational biology, 7(2):e1001066, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact