{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T22:37:17Z","timestamp":1740177437913,"version":"3.37.3"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Path homology is a powerful method for attaching algebraic invariants to digraphs. While there have been growing theoretical developments on the algebro-topological framework surrounding path homology, <jats:italic>bona fide<\/jats:italic> applications to the study of complex networks have remained stagnant. We address this gap by presenting an algorithm for path homology that combines efficient pruning and indexing techniques and using it to topologically analyze a variety of real-world complex temporal networks. A crucial step in our analysis is the complete characterization of path homologies of certain families of small digraphs that appear as subgraphs in these complex networks. These families include all digraphs, directed acyclic graphs, and undirected graphs up to certain numbers of vertices, as well as some specially constructed cases. Using information from this analysis, we identify small digraphs contributing to path homology in dimension two for three temporal networks in an aggregated representation and relate these digraphs to network behavior. We then investigate alternative temporal network representations and identify complementary subgraphs as well as behavior that is preserved across representations. We conclude that path homology provides insight into temporal network structure, and in turn, emergent structures in temporal networks provide us with new subgraphs having interesting path homology.<\/jats:p>","DOI":"10.1007\/s41109-021-00441-z","type":"journal-article","created":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T10:02:59Z","timestamp":1641463379000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Path homologies of motifs and temporal network representations"],"prefix":"10.1007","volume":"7","author":[{"given":"Samir","family":"Chowdhury","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9168-2216","authenticated-orcid":false,"given":"Steve","family":"Huntsman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matvey","family":"Yutin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,6]]},"reference":[{"key":"441_CR1","doi-asserted-by":"crossref","unstructured":"Adams H, Tausz A, Vejdemo-Johansson M (2014) Javaplex: a research software package for persistent (co) homology. In: International congress on mathematical software. Springer, pp 129\u2013136","DOI":"10.1007\/978-3-662-44199-2_23"},{"key":"441_CR2","doi-asserted-by":"crossref","unstructured":"Battiston F, Cencetti G, Iacopini I, Latora V, Lucas M, Patania A, Young J-G, Petri G (2020) Networks beyond pairwise interactions: structure and dynamics. Phys Rep","DOI":"10.1016\/j.physrep.2020.05.004"},{"issue":"6295","key":"441_CR3","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1126\/science.aad9029","volume":"353","author":"AR Benson","year":"2016","unstructured":"Benson AR, Gleich DF, Leskovec J (2016) Higher-order organization of complex networks. Science 353(6295):163\u2013166","journal-title":"Science"},{"key":"441_CR4","unstructured":"Bergomi MG, Ferri M, Tavaglione A (2020) Steady and ranging sets in graph persistence. arXiv preprint arXiv:2009.06897"},{"issue":"2","key":"441_CR5","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1090\/S0273-0979-09-01249-X","volume":"46","author":"G Carlsson","year":"2009","unstructured":"Carlsson G (2009) Topology and data. Bull Am Math Soc 46(2):255\u2013308","journal-title":"Bull Am Math Soc"},{"key":"441_CR6","doi-asserted-by":"publisher","first-page":"107254","DOI":"10.1016\/j.topol.2020.107254","volume":"279","author":"S Chowdhury","year":"2020","unstructured":"Chowdhury S, Clause N, M\u00e9moli F, S\u00e1nchez J\u00c1, Wellner Z (2020) New families of stable simplicial filtration functors. Topol Appl 279:107254n","journal-title":"Topol Appl"},{"issue":"1","key":"441_CR7","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 (2018) A functorial Dowker theorem and persistent homology of asymmetric networks. J Appl Comput Topol 2(1):115\u2013175","journal-title":"J Appl Comput Topol"},{"key":"441_CR8","doi-asserted-by":"crossref","unstructured":"Chowdhury S, M\u00e9moli F (2018) Persistent path homology of directed networks. In: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms. SIAM, pp 1152\u20131169","DOI":"10.1137\/1.9781611975031.75"},{"key":"441_CR9","doi-asserted-by":"crossref","unstructured":"Chowdhury S, Huntsman S, Yutin M (2020) Path homology and temporal networks. In: International conference on complex networks and their applications. Springer, pp 639\u2013650","DOI":"10.1007\/978-3-030-65351-4_51"},{"key":"441_CR10","doi-asserted-by":"crossref","unstructured":"Chowdhury S, Gebhart T, Huntsman S, Yutin M (2019) Path homologies of deep feedforward networks. In: 2019 18th IEEE international conference on machine learning and applications (ICMLA). IEEE, pp 1077\u20131082","DOI":"10.1109\/ICMLA.2019.00181"},{"issue":"1","key":"441_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41109-019-0209-1","volume":"4","author":"G Cybenko","year":"2019","unstructured":"Cybenko G, Huntsman S (2019) Analytics for directed contact networks. Appl Netw Sci 4(1):1\u201321","journal-title":"Appl Netw Sci"},{"key":"441_CR12","unstructured":"Dey TK, Li T, Wang Y (2020) An efficient algorithm for 1-dimensional (persistent) path homology. In: 36th international symposium on computational geometry (SoCG 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"6","key":"441_CR13","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1109\/MS.2016.147","volume":"33","author":"C Ebert","year":"2016","unstructured":"Ebert C, Cain J, Antoniol G, Counsell S, Laplante P (2016) Cyclomatic complexity. IEEE Softw 33(6):27\u201329","journal-title":"IEEE Softw"},{"key":"441_CR14","volume-title":"Computational topology: an introduction","author":"H Edelsbrunner","year":"2010","unstructured":"Edelsbrunner H, Harer J (2010) Computational topology: an introduction. American Mathematical Soc, Providence"},{"key":"441_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316339831","volume-title":"Introduction to random graphs","author":"A Frieze","year":"2016","unstructured":"Frieze A, Karo\u0144ski M (2016) Introduction to random graphs. Cambridge University Press, Cambridge"},{"key":"441_CR16","unstructured":"Gebhart T, Funk RJ (2020) The emergence of higher-order structure in scientific and technological knowledge networks. arXiv preprint arXiv:2009.13620"},{"key":"441_CR17","volume-title":"Elementary applied topology","author":"RW Ghrist","year":"2014","unstructured":"Ghrist RW (2014) Elementary applied topology, vol 1. Createspace Seattle, Scotts Valley"},{"issue":"1","key":"441_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10827-016-0608-6","volume":"41","author":"C Giusti","year":"2016","unstructured":"Giusti C, Ghrist R, Bassett DS (2016) Two\u2019s company, three (or more) is a simplex. J Comput Neurosci 41(1):1\u201314","journal-title":"J Comput Neurosci"},{"issue":"2","key":"441_CR19","doi-asserted-by":"publisher","first-page":"179","DOI":"10.4310\/HHA.2018.v20.n2.a9","volume":"20","author":"A Grigor\u2019yan","year":"2018","unstructured":"Grigor\u2019yan A, Jimenez R, Muranov Y, Yau S-T (2018) On the path homology theory of digraphs and Eilenberg\u2013Steenrod axioms. Homol Homot Appl 20(2):179\u2013205","journal-title":"Homol Homot Appl"},{"issue":"4","key":"441_CR20","doi-asserted-by":"publisher","first-page":"619","DOI":"10.4310\/PAMQ.2014.v10.n4.a2","volume":"10","author":"A Grigor\u2019yan","year":"2014","unstructured":"Grigor\u2019yan A, Lin Y, Muranov Y, Yau S-T (2014) Homotopy theory for digraphs. Pure Appl Math Q 10(4):619\u2013674","journal-title":"Pure Appl Math Q"},{"issue":"5","key":"441_CR21","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 Y, Yau S-T (2015) Cohomology of digraphs and (undirected) graphs. Asian J Math 19(5):887\u2013932","journal-title":"Asian J Math"},{"issue":"1","key":"441_CR22","doi-asserted-by":"publisher","first-page":"295","DOI":"10.4310\/HHA.2014.v16.n1.a16","volume":"16","author":"A Grigor\u2019yan","year":"2014","unstructured":"Grigor\u2019yan A, Muranov YV, Yau S-T et al (2014) Graphs associated with simplicial complexes. Homol Homot Appl 16(1):295\u2013311","journal-title":"Homol Homot Appl"},{"issue":"5","key":"441_CR23","doi-asserted-by":"publisher","first-page":"969","DOI":"10.4310\/CAG.2017.v25.n5.a4","volume":"25","author":"A Grigor\u2019yan","year":"2017","unstructured":"Grigor\u2019yan A, Muranov Y, Yau S-T (2017) Homologies of digraphs and k\u00fcnneth formulas. Commun Anal Geom 25(5):969\u20131018","journal-title":"Commun Anal Geom"},{"key":"441_CR24","unstructured":"Grigor\u2019yan A, Lin Y, Muranov Y, Yau S-T (2012) Homologies of path complexes and digraphs. arXiv preprint arXiv:1207.2834"},{"key":"441_CR25","doi-asserted-by":"crossref","unstructured":"Grigor\u2019yan A, Muranov Y, Vershinin V, Yau S-T (2018) Path homology theory of multigraphs and quivers. In: Forum mathematicum, vol 30. De Gruyter, pp 1319\u20131337","DOI":"10.1515\/forum-2018-0015"},{"key":"441_CR26","unstructured":"G\u00f3mez M, M\u00e9moli F (2021) Curvature sets over persistence diagrams. arXiv preprint arXiv:2103.04470"},{"key":"441_CR27","unstructured":"Hatcher A (2001) Algebraic topology"},{"issue":"9","key":"441_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1140\/epjb\/e2015-60657-4","volume":"88","author":"P Holme","year":"2015","unstructured":"Holme P (2015) Modern temporal network theory: a colloquium. Eur Phys J B 88(9):1\u201330","journal-title":"Eur Phys J B"},{"key":"441_CR29","unstructured":"Huntsman S (2020) Path homology as a stronger analogue of cyclomatic complexity. arXiv preprint arXiv:2003.00944"},{"key":"441_CR30","doi-asserted-by":"crossref","unstructured":"Kunegis J (2013) Konect: the koblenz network collection. In: Proceedings of the 22nd international conference on World Wide Web, pp 1343\u20131350","DOI":"10.1145\/2487788.2488173"},{"issue":"3","key":"441_CR31","doi-asserted-by":"publisher","first-page":"033015","DOI":"10.1088\/1367-2630\/11\/3\/033015","volume":"11","author":"A Lancichinetti","year":"2009","unstructured":"Lancichinetti A, Fortunato S, Kert\u00e9sz J (2009) Detecting the overlapping and hierarchical community structure in complex networks. New J Phys 11(3):033015","journal-title":"New J Phys"},{"key":"441_CR32","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: Stanford large network dataset collection"},{"key":"441_CR33","unstructured":"Lin Y, Ren S, Wang C, Wu J (2019) Weighted path homology of weighted digraphs and persistence. arXiv preprint arXiv:1910.09891"},{"issue":"1","key":"441_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/srep01236","volume":"3","author":"PY Lum","year":"2013","unstructured":"Lum PY, Singh G, Lehman A, Ishkanov T, Vejdemo-Johansson M, Alagappan M, Carlsson J, Carlsson G (2013) Extracting insights from the shape of complex data using topology. Sci Rep 3(1):1\u20138","journal-title":"Sci Rep"},{"issue":"1","key":"441_CR36","doi-asserted-by":"publisher","first-page":"19","DOI":"10.3390\/a13010019","volume":"13","author":"D L\u00fctgehetmann","year":"2020","unstructured":"L\u00fctgehetmann D, Govc D, Smith JP, Levi R (2020) Computing persistent homology of directed flag complexes. Algorithms 13(1):19","journal-title":"Algorithms"},{"issue":"251","key":"441_CR35","first-page":"1","volume":"21","author":"H Lyu","year":"2020","unstructured":"Lyu H, Needell D, Balzano L (2020) Online matrix factorization for Markovian data and applications to network dictionary learning. J Mach Learn Res 21(251):1\u201349","journal-title":"J Mach Learn Res"},{"key":"441_CR37","doi-asserted-by":"publisher","DOI":"10.1142\/q0268","volume-title":"Guide to temporal networks","author":"N Masuda","year":"2020","unstructured":"Masuda N, Lambiotte R (2020) Guide to temporal networks, vol 6. A World Scientific, Singapore"},{"key":"441_CR38","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1109\/TSE.1976.233837","volume":"4","author":"TJ McCabe","year":"1976","unstructured":"McCabe TJ (1976) A complexity measure. IEEE Trans Softw Eng 4:308\u2013320","journal-title":"IEEE Trans Softw Eng"},{"issue":"5594","key":"441_CR39","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 (2002) Network motifs: simple building blocks of complex networks. Science 298(5594):824\u2013827","journal-title":"Science"},{"key":"441_CR40","doi-asserted-by":"crossref","unstructured":"Montoya LV, Ma A, Mondrag\u00f3n RJ (2013) Social achievement and centrality in mathoverflow. In: Complex networks IV. Springer, pp 27\u201338","DOI":"10.1007\/978-3-642-36844-8_3"},{"key":"441_CR41","unstructured":"M\u00e9ndez D, S\u00e1nchez-Garc\u00eda RJ (2020) A directed persistent homology theory for dissimilarity functions. arXiv preprint arXiv:2008.00711"},{"issue":"6","key":"441_CR42","doi-asserted-by":"publisher","first-page":"66506","DOI":"10.1371\/journal.pone.0066506","volume":"8","author":"G Petri","year":"2013","unstructured":"Petri G, Scolamiero M, Donato I, Vaccarino F (2013) Topological strata of weighted complex networks. PLoS ONE 8(6):66506","journal-title":"PLoS ONE"},{"key":"441_CR43","unstructured":"Polanco L, Perea J (2019) Coordinatizing data with lens spaces and persistent cohomology. In: Proceedings of the 31st Canadian conference on computational geometry (CCCG), pp 49\u201357"},{"issue":"12","key":"441_CR44","doi-asserted-by":"publisher","first-page":"123055","DOI":"10.1088\/1367-2630\/16\/12\/123055","volume":"16","author":"M P\u00f3sfai","year":"2014","unstructured":"P\u00f3sfai M, H\u00f6vel P (2014) Structural controllability of temporal networks. New J Phys 16(12):123055","journal-title":"New J Phys"},{"issue":"2","key":"441_CR45","doi-asserted-by":"publisher","first-page":"026112","DOI":"10.1103\/PhysRevE.67.026112","volume":"67","author":"E Ravasz","year":"2003","unstructured":"Ravasz E, Barab\u00e1si A-L (2003) Hierarchical organization in complex networks. Phys Rev E 67(2):026112","journal-title":"Phys Rev E"},{"key":"441_CR46","doi-asserted-by":"publisher","first-page":"48","DOI":"10.3389\/fncom.2017.00048","volume":"11","author":"MW Reimann","year":"2017","unstructured":"Reimann MW, Nolte M, Scolamiero M, Turner K, Perin R, Chindemi G, D\u0142otko P, Levi R, Hess K, Markram H (2017) Cliques of neurons bound into cavities provide a missing link between structure and function. Front Comput Neurosci 11:48","journal-title":"Front Comput Neurosci"},{"key":"441_CR47","unstructured":"Shajii AR (2013) Digraph homology. https:\/\/github.com\/arshajii\/digraph-homology"},{"key":"441_CR48","unstructured":"Singh G, M\u00e9moli F, Carlsson G (2007) Topological methods for the analysis of high dimensional data sets and 3d object recognition. In: Eurographics symposium on point-based graphics, vol 2"},{"issue":"3","key":"441_CR49","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1162\/netn_a_00073","volume":"3","author":"AE Sizemore","year":"2019","unstructured":"Sizemore AE, Phillips-Cremins JE, Ghrist R, Bassett DS (2019) The importance of the whole: topological data analysis for the network neuroscientist. Netw Neurosci 3(3):656\u2013673","journal-title":"Netw Neurosci"},{"key":"441_CR50","unstructured":"Slawinski M (2013) Digraph homology. https:\/\/github.com\/gtownrocks\/digraph_homology"},{"issue":"12","key":"441_CR51","doi-asserted-by":"publisher","first-page":"1907","DOI":"10.1093\/bioinformatics\/btx056","volume":"33","author":"IY Smoly","year":"2017","unstructured":"Smoly IY, Lerman E, Ziv-Ukelson M, Yeger-Lotem E (2017) Motifnet: a web-server for network motif analysis. Bioinformatics 33(12):1907\u20131909","journal-title":"Bioinformatics"},{"key":"441_CR52","doi-asserted-by":"crossref","unstructured":"Tausczik YR, Kittur A, Kraut RE (2014) Collaborative problem solving: a study of mathoverflow. In: Proceedings of the 17th ACM conference on computer supported cooperative work & social computing, pp 355\u2013367","DOI":"10.1145\/2531602.2531690"},{"issue":"3","key":"441_CR53","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.2140\/agt.2019.19.1135","volume":"19","author":"K Turner","year":"2019","unstructured":"Turner K (2019) Rips filtrations for quasimetric spaces and asymmetric functions with stability results. Algebraic Geometric Topol 19(3):1135\u20131170","journal-title":"Algebraic Geometric Topol"},{"key":"441_CR54","unstructured":"Vincent-Cuaz C, Vayer T, Flamary R, Corneli M, Courty N (2021) Online graph dictionary learning. In: Meila M, Zhang T (eds) Proceedings of the 38th international conference on machine learning. Proceedings of machine learning research, vol 139. PMLR, pp 10564\u201310574. https:\/\/proceedings.mlr.press\/v139\/vincent-cuaz21a.html"},{"key":"441_CR55","doi-asserted-by":"crossref","unstructured":"Viswanath B, Mislove A, Cha M, Gummadi KP (2009) On the evolution of user interaction in facebook. In: Proceedings of the 2nd ACM workshop on online social networks, pp 37\u201342","DOI":"10.1145\/1592665.1592675"},{"key":"441_CR56","doi-asserted-by":"crossref","unstructured":"Xu H (2020) Gromov-Wasserstein factorization models for graph clustering. In: Proceedings of the AAAI conference on artificial intelligence, vol 34, pp 6478\u20136485","DOI":"10.1609\/aaai.v34i04.6120"},{"key":"441_CR57","unstructured":"Yutin M (2020) Performant path homology. https:\/\/github.com\/SteveHuntsmanBAESystems\/PerformantPathHomology"},{"key":"441_CR58","unstructured":"Yutin M (2019) Personal communication"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00441-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-021-00441-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00441-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T10:05:00Z","timestamp":1641463500000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-021-00441-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,6]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["441"],"URL":"https:\/\/doi.org\/10.1007\/s41109-021-00441-z","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2022,1,6]]},"assertion":[{"value":"31 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"4"}}