{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:08:41Z","timestamp":1775002121975,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,11,27]],"date-time":"2022-11-27T00:00:00Z","timestamp":1669507200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,11,27]],"date-time":"2022-11-27T00:00:00Z","timestamp":1669507200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740761"],"award-info":[{"award-number":["CCF-1740761"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1547357"],"award-info":[{"award-number":["DMS-1547357"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["RI-1815697"],"award-info":[{"award-number":["RI-1815697"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s00454-022-00430-8","type":"journal-article","created":{"date-parts":[[2022,11,27]],"date-time":"2022-11-27T21:35:06Z","timestamp":1669584906000},"page":"1102-1132","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology"],"prefix":"10.1007","volume":"68","author":[{"given":"Tamal K.","family":"Dey","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9655-3691","authenticated-orcid":false,"given":"Tianqi","family":"Li","sequence":"additional","affiliation":[]},{"given":"Yusu","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,27]]},"reference":[{"key":"430_CR1","doi-asserted-by":"crossref","unstructured":"Busaryev, O., Cabello, S., Chen, C., Dey, T.K., Wang, Y.: Annotating simplices with a homology basis and its applications. In: 13th Scandinavian Symposium and Workshop on Algorithm Theory (Helsinki 2012). Lecture Notes in Computer Science, vol. 7357, pp. 189\u2013200. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-31155-0_17"},{"key":"430_CR2","doi-asserted-by":"crossref","unstructured":"Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Paris 2009), pp. 199\u2013208. ACM, New York (2009)","DOI":"10.1145\/1557019.1557047"},{"key":"430_CR3","doi-asserted-by":"crossref","unstructured":"Cheung, H.Y., Kwok, T.C., Lau, L.C.: Fast matrix rank algorithms and applications. J. ACM 60(5), #\u00a031 (2013)","DOI":"10.1145\/2528404"},{"issue":"1","key":"430_CR4","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210\u2013223 (1985)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"430_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s41468-018-0020-6","volume":"2","author":"S Chowdhury","year":"2018","unstructured":"Chowdhury, S., M\u00e9moli, F.: A functorial Dowker theorem and persistent homology of asymmetric networks. J. Appl. Comput. Topol. 2(1\u20132), 115\u2013175 (2018)","journal-title":"J. Appl. Comput. Topol."},{"key":"430_CR6","doi-asserted-by":"crossref","unstructured":"Chowdhury, S., M\u00e9moli, F.: Persistent path homology of directed networks. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2018), pp. 1152\u20131169. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.75"},{"key":"430_CR7","doi-asserted-by":"crossref","unstructured":"Cohen-Steiner, D., Edelsbrunner, H., Morozov, D.: Vines and vineyards by updating persistence in linear time. In: 22nd International Symposium on Computational Geometry (Sedona 2006), pp. 119\u2013126. ACM, New York (2006)","DOI":"10.1145\/1137856.1137877"},{"key":"430_CR8","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)"},{"key":"430_CR9","doi-asserted-by":"crossref","unstructured":"Dey, T.K., Li, T., Wang, Y.: Efficient algorithms for computing a minimal homology basis. In: 13th Latin American Symposium on Theoretical Informatics (Buenos Aires 2018). Lecture Notes in Computer Science, vol. 10807, pp. 376\u2013398. Springer, Cham (2018)","DOI":"10.1007\/978-3-319-77404-6_28"},{"key":"430_CR10","unstructured":"D\u0142otko, P., Hess, K., Levi, R., Nolte, M., Reimann, M., Scolamiero,\u00a0M., Turner,\u00a0K., Muller,\u00a0E., Markram,\u00a0H.: Topological analysis of the connectome of digital reconstructions of neural microcircuits (2016). arXiv:1601.01580"},{"key":"430_CR11","unstructured":"Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: 16th Annual ACM-SIAM Symposium on Discrete Algorithms (Vancouver 2005), pp. 1038\u20131046. ACM, New York (2005)"},{"key":"430_CR12","unstructured":"Grigor\u2019yan, A., Lin, Y., Muranov, Yu., Yau, S.-T.: Homologies of path complexes and digraphs (2012). arXiv:1207.2834"},{"key":"430_CR13","doi-asserted-by":"crossref","unstructured":"Grigor\u2019yan, A., Lin, Y., Muranov, Yu., Yau, S.-T.: Homotopy theory for digraphs (2014). arXiv:1407.0234","DOI":"10.4310\/PAMQ.2014.v10.n4.a2"},{"issue":"5","key":"430_CR14","doi-asserted-by":"publisher","first-page":"887","DOI":"10.4310\/AJM.2015.v19.n5.a5","volume":"19","author":"A Grigor\u2019yan","year":"2015","unstructured":"Grigor\u2019yan, A., Lin, Y., Muranov, Yu., Yau, S.-T.: Cohomology of digraphs and (undirected) graphs. Asian J. Math. 19(5), 887\u2013931 (2015)","journal-title":"Asian J. Math."},{"key":"430_CR15","series-title":"Addison-Wesley Series in Mathematics","volume-title":"Graph Theory","author":"F Harary","year":"1971","unstructured":"Harary, F.: Graph Theory. Addison-Wesley Series in Mathematics, Addison-Wesley, Boston (1971)"},{"key":"430_CR16","doi-asserted-by":"crossref","unstructured":"Ignacio, P.S.P., Darcy, I.K.: Tracing patterns and shapes in remittance and migration networks via persistent homology. EPJ Data Sci. 8(1), $$\\# \\,1$$ (2019)","DOI":"10.1140\/epjds\/s13688-018-0179-z"},{"key":"430_CR17","unstructured":"Jeannerod, C.: LSP matrix decomposition revisited (2006). http:\/\/www.ens-lyon.fr\/LIP\/Pub\/Rapports\/RR\/RR2006\/RR2006-28.pdf"},{"issue":"3","key":"430_CR18","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.ipl.2005.01.006","volume":"94","author":"C Liebchen","year":"2005","unstructured":"Liebchen, C., Rizzi, R.: A greedy approach to compute a minimum cycle basis of a directed graph. Inform. Process. Lett. 94(3), 107\u2013112 (2005)","journal-title":"Inform. Process. Lett."},{"key":"430_CR19","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4939-9063-4","volume-title":"A Basic Course in Algebraic Topology","author":"WS Massey","year":"1991","unstructured":"Massey, W.S.: A Basic Course in Algebraic Topology. Graduate Texts in Mathematics, vol. 127. Springer, New York (1991)"},{"key":"430_CR20","doi-asserted-by":"crossref","unstructured":"Masulli, P., Villa, A.E.P.: The topology of the directed clique complex as a network invariant. SpringerPlus 5(1), #\u00a0388 (2016)","DOI":"10.1186\/s40064-016-2022-y"},{"issue":"5594","key":"430_CR21","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298(5594), 824\u2013827 (2002)","journal-title":"Science"},{"key":"430_CR22","doi-asserted-by":"crossref","unstructured":"Reimann, M.W., Nolte, M., Scolamiero, M., Turner, K., Perin, R., Chindemi, G., D\u0142otko, P., Le-vi, R., Hess, K., Markram, H.: Cliques of neurons bound into cavities provide a missing link between structure and function. Front. Comput. Neurosci. 11, #\u00a048 (2017)","DOI":"10.3389\/fncom.2017.00048"},{"issue":"3","key":"430_CR23","first-page":"93","volume":"29","author":"P Sen","year":"2008","unstructured":"Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., Eliassi-Rad, T.: Collective classification in network data. AI Mag. 29(3), 93\u2013106 (2008)","journal-title":"AI Mag."},{"key":"430_CR24","doi-asserted-by":"crossref","unstructured":"Varshney, L.R., Chen, B.L., Paniagua, E., Hall, D.H., Chklovskii, D.B.: Structural properties of the Caenorhabditis elegans neuronal network. PLoS Comput. Biol. 7(2), $$\\#\\,{\\rm e}1001066$$ (2011)","DOI":"10.1371\/journal.pcbi.1001066"},{"key":"430_CR25","unstructured":"The International Development Association, the World Bank Group: Bilateral remittance estimates for 2015 using migrant stocks, host country incomes, and origin country incomes (millions of US\\$) (2016). https:\/\/www.worldbank.org\/en\/topic\/migrationremittancesdiasporaissues\/brief\/migration-remittances-data"},{"key":"430_CR26","unstructured":"United Nations Department of Economic & Social Affairs: PD trends in international migrant stock: migrants by destination and origin (United Nations database, pop\/db\/mig\/stock\/rev.2015) (2015). https:\/\/www.un.org\/en\/development\/desa\/population\/migration\/data\/estimates2\/estimates15.asp"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00430-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00430-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00430-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T18:21:12Z","timestamp":1669832472000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00430-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,27]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["430"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00430-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,27]]},"assertion":[{"value":"11 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 November 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}