{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T08:26:38Z","timestamp":1772180798540,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,7,17]],"date-time":"2021-07-17T00:00:00Z","timestamp":1626480000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,17]],"date-time":"2021-07-17T00:00:00Z","timestamp":1626480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Temporal networks are graphs where each edge is associated with a timestamp denoting when two nodes interact. Temporal Subgraph Isomorphism (TSI) aims at retrieving all the subgraphs of a temporal network (called target) matching a smaller temporal network (called query), such that matched target edges appear in the same chronological order of corresponding query edges. Few algorithms have been proposed to solve the TSI problem (or variants of it) and most of them are applicable only to small or specific queries. In this paper we present <jats:italic>TemporalRI<\/jats:italic>, a new subgraph isomorphism algorithm for temporal networks with multiple contacts between nodes, which is inspired by RI algorithm. TemporalRI introduces the notion of temporal flows and uses them to filter the search space of candidate nodes for the matching. Our algorithm can handle queries of any size and any topology. Experiments on real networks of different sizes show that TemporalRI is very efficient compared to the state-of-the-art, especially for large queries and targets.<\/jats:p>","DOI":"10.1007\/s41109-021-00397-0","type":"journal-article","created":{"date-parts":[[2021,7,17]],"date-time":"2021-07-17T10:02:28Z","timestamp":1626516148000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["TemporalRI: subgraph isomorphism in temporal networks with multiple contacts"],"prefix":"10.1007","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4953-026X","authenticated-orcid":false,"given":"Giovanni","family":"Micale","sequence":"first","affiliation":[]},{"given":"Giorgio","family":"Locicero","sequence":"additional","affiliation":[]},{"given":"Alfredo","family":"Pulvirenti","sequence":"additional","affiliation":[]},{"given":"Alfredo","family":"Ferro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,17]]},"reference":[{"issue":"1","key":"397_CR1","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/2601412","volume":"47","author":"C Aggarwal","year":"2014","unstructured":"Aggarwal C, Subbian K (2014) Evolutionary network analysis: a survey. ACM Comput Surv (CSUR) 47(1):10","journal-title":"ACM Comput Surv (CSUR)"},{"key":"397_CR2","doi-asserted-by":"crossref","unstructured":"Bi F, Chang L, Lin X, Qin L, Zhang W (2016) Efficient subgraph matching by postponing cartesian products. SIGMOD \u201916, pp 1199\u20131214","DOI":"10.1145\/2882903.2915236"},{"issue":"1","key":"397_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1109\/TCBB.2016.2515595","volume":"14","author":"V Bonnici","year":"2017","unstructured":"Bonnici V, Giugno R (2017) On the variable ordering in subgraph isomorphism algorithms. IEEE\/ACM Trans Comput Biol Bioinform 14(1):193\u2013203","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"S13","key":"397_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-14-S13-S1","volume":"14","author":"V Bonnici","year":"2013","unstructured":"Bonnici V, Giugno R, Pulvirenti A, Shasha D, Ferro A (2013) A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinform 14(S13):1\u201313","journal-title":"BMC Bioinform"},{"key":"397_CR5","doi-asserted-by":"crossref","unstructured":"Carletti V, Foggia P, Saggese A, Vento M (2017) Introducing vf3: a new algorithm for subgraph isomorphism. In: Graph-based representations in pattern recognition, pp 128\u2013139","DOI":"10.1007\/978-3-319-58961-9_12"},{"issue":"4","key":"397_CR6","doi-asserted-by":"publisher","first-page":"1324","DOI":"10.1016\/j.dss.2006.04.003","volume":"43","author":"KM Carley","year":"2007","unstructured":"Carley KM, Diesner J, Reminga J, Tsvetovat M (2007) Toward an interoperable dynamic network analysis toolkit. Decis Support Syst 43(4):1324\u20131347","journal-title":"Decis Support Syst"},{"key":"397_CR7","doi-asserted-by":"crossref","unstructured":"Casteigts A, Flocchini P, Quattrociocchi W, Santoro N (2011) Time-varying graphs and dynamic networks. In: Ad-hoc, mobile, and wireless networks, pp 346\u2013359","DOI":"10.1007\/978-3-642-22450-8_27"},{"key":"397_CR8","unstructured":"Cohen WW (2009) Enron email dataset (2005). http:\/\/www.cs.cmu.edu\/enron"},{"issue":"10","key":"397_CR9","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella LP, Foggia P, Sansone C, Vento M (2004) A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal Mach Intell 26(10):1367\u20131372","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"5","key":"397_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0195993","volume":"13","author":"J Crawford","year":"2018","unstructured":"Crawford J, Milenkovic T (2018) Cluenet: clustering a temporal network based on topological similarity rather than denseness. PLoS ONE 13(5):1\u201325","journal-title":"PLoS ONE"},{"key":"397_CR11","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s00354-019-00065-z","volume":"38","author":"A Divakaran","year":"2020","unstructured":"Divakaran A, Mohan A (2020) Temporal link prediction: a survey. New Gener Comput 38:213\u2013258","journal-title":"New Gener Comput"},{"issue":"11","key":"397_CR12","first-page":"1","volume":"7","author":"M G\u00e9nois","year":"2018","unstructured":"G\u00e9nois M, Barrat A (2018) Can co-location be used as a proxy for face-to-face contacts? EPJ Data Sci 7(11):1\u201318","journal-title":"EPJ Data Sci"},{"key":"397_CR14","doi-asserted-by":"crossref","unstructured":"Han W, Lee J, Lee J-H (2013) Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: Proceedings of the 2013 ACM SIGMOD international conference on management of data. SIGMOD \u201913, pp 337\u2013348 ( 2013)","DOI":"10.1145\/2463676.2465300"},{"key":"397_CR13","doi-asserted-by":"crossref","unstructured":"Han M, Kim H, Gu G, Park K, Han W (2019) Efficient subgraph matching: harmonizing dynamic programming, adaptive matching order, and failing set together. In: Proceedings of the 2019 international conference on management of data. SIGMOD \u201919, pp 1429\u20131446","DOI":"10.1145\/3299869.3319880"},{"issue":"2","key":"397_CR15","doi-asserted-by":"publisher","first-page":"023073","DOI":"10.1103\/PhysRevResearch.2.023073","volume":"2","author":"T Hiraoka","year":"2020","unstructured":"Hiraoka T, Masuda N, Li A, Jo H (2020) Modeling temporal networks with bursty activity patterns of nodes and links. Phys Rev Res 2(2):023073","journal-title":"Phys Rev Res"},{"issue":"1","key":"397_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1140\/epjds5","volume":"1","author":"T Hogg","year":"2012","unstructured":"Hogg T, Lerman K (2012) Social dynamics of digg. EPJ Data Sci 1(1):1\u201326","journal-title":"EPJ Data Sci"},{"issue":"3","key":"397_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme P, Saramaki J (2012) Temporal networks. Phys Rep 519(3):97\u2013125","journal-title":"Phys Rep"},{"key":"397_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-23495-9","volume-title":"Temporal network theory","author":"P Holme","year":"2019","unstructured":"Holme P, Saramaki J (2019) Temporal network theory. Springer, Cham"},{"issue":"12","key":"397_CR19","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1093\/bioinformatics\/btv227","volume":"31","author":"Y Hulovatyy","year":"2015","unstructured":"Hulovatyy Y, Chen H, Milenkovic T (2015) Exploring the structure and function of temporal networks with dynamic graphlets. Bioinformatics 31(12):171\u2013180","journal-title":"Bioinformatics"},{"issue":"1","key":"397_CR20","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.jtbi.2010.11.033","volume":"271","author":"L Isella","year":"2011","unstructured":"Isella L, Stehl\u00e9 J, Barrat A, Cattuto C, Pinton JF, Van den Broeck W (2011) What\u2019s in a crowd? Analysis of face-to-face behavioral networks. J Theor Biol 271(1):166\u2013180","journal-title":"J Theor Biol"},{"key":"397_CR21","doi-asserted-by":"crossref","unstructured":"Kim K, Seo I, Han W, Lee J, Hong S, Chafi H, Shin H, Jeong G ( 2018) Turboflux: a fast continuous subgraph matching system for streaming graph data. In: Proceedings of the 2018 international conference on management of data. SIGMOD \u201918, pp 411\u2013426","DOI":"10.1145\/3183713.3196917"},{"issue":"11","key":"397_CR22","doi-asserted-by":"publisher","first-page":"11005","DOI":"10.1088\/1742-5468\/2011\/11\/P11005","volume":"2011","author":"L Kovanen","year":"2011","unstructured":"Kovanen L, Karsai M, Kaski K, Kert\u00e9sz J, Saramaki J (2011) Temporal motifs in time-dependent networks. J Stat Mech Theory Exp 2011(11):11005","journal-title":"J Stat Mech Theory Exp"},{"key":"397_CR23","doi-asserted-by":"crossref","unstructured":"Liu P, Benson AR, Charikar M (2019) Sampling methods for counting temporal motifs. In: Proceedings of the twelfth ACM international conference on web search and data mining. WSDM \u201919, pp 294\u2013302","DOI":"10.1145\/3289600.3290988"},{"key":"397_CR24","doi-asserted-by":"crossref","unstructured":"Locicero G, Micale G, Pulvirenti A, Ferro A (2021) TemporalRI: a subgraph isomorphism algorithm for temporal networks. In: Complex networks and their applications IX, pp 675\u2013687","DOI":"10.1007\/978-3-030-65351-4_54"},{"issue":"12","key":"397_CR25","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1016\/j.physleta.2019.01.041","volume":"383","author":"L Lv","year":"2019","unstructured":"Lv L, Zhang K, Zhang T, Bardou D, Zhang J, Cai Y (2019) Pagerank centrality for temporal networks. Phys Lett A 383(12):1215\u20131222","journal-title":"Phys Lett A"},{"key":"397_CR26","doi-asserted-by":"crossref","unstructured":"Mackey P, Porterfield K, Fitzhenry E, Choudhury S, Chin G (2018) A chronological edge-driven approach to temporal subgraph isomorphism. In: 2018 IEEE international conference on big data (big data), pp 3972\u20133979","DOI":"10.1109\/BigData.2018.8622100"},{"issue":"2","key":"397_CR27","doi-asserted-by":"publisher","first-page":"023163","DOI":"10.1103\/PhysRevResearch.2.023163","volume":"2","author":"N Masuda","year":"2020","unstructured":"Masuda N, Holme P (2020) Small inter-event times govern epidemic spreading on networks. Phys Rev Res 2(2):023163","journal-title":"Phys Rev Res"},{"key":"397_CR28","doi-asserted-by":"publisher","DOI":"10.1142\/q0268","volume-title":"A guide to temporal networks","author":"N Masuda","year":"2020","unstructured":"Masuda N, Lambiotte R (2020) A guide to temporal networks, 2nd edn. World Scientific, Singapore","edition":"2"},{"key":"397_CR29","unstructured":"Network Repository: an interactive scientific network data repository (2021). http:\/\/networkrepository.com. Accessed 4 Jan 2021"},{"key":"397_CR30","doi-asserted-by":"crossref","unstructured":"Paranjape A, Benson AR, Leskovec J (2017) Motifs in temporal networks. In: Proceedings of the tenth ACM international conference on web search and data mining. WSDM \u201917, pp 601\u2013610","DOI":"10.1145\/3018661.3018731"},{"issue":"5","key":"397_CR31","doi-asserted-by":"publisher","first-page":"052307","DOI":"10.1103\/PhysRevE.98.052307","volume":"98","author":"J Petit","year":"2018","unstructured":"Petit J, Gueuning M, Carletti T, Lauwens B, Lambiotte R (2018) Random walk on temporal networks with lasting edges. Phys Rev E 98(5):052307","journal-title":"Phys Rev E"},{"issue":"9","key":"397_CR32","doi-asserted-by":"publisher","first-page":"3715","DOI":"10.1016\/j.eswa.2012.12.077","volume":"40","author":"U Redmond","year":"2013","unstructured":"Redmond U, Cunningham P (2013a) A temporal network analysis reveals the unprofitability of arbitrage in the prosper marketplace. Expert Syst Appl 40(9):3715\u20133721","journal-title":"Expert Syst Appl"},{"key":"397_CR33","doi-asserted-by":"crossref","unstructured":"Redmond U, Cunningham P (2013b) Temporal subgraph isomorphism. In: Proceedings of the 2013 IEEE\/ACM international conference on advances in social networks analysis and mining. ASONAM \u201913, pp 1451\u20131452","DOI":"10.1145\/2492517.2492586"},{"key":"397_CR34","unstructured":"Redmond U, Cunningham P (2016) Subgraph isomorphism in temporal networks. arXiv:1605.02174"},{"issue":"5","key":"397_CR35","doi-asserted-by":"publisher","first-page":"052302","DOI":"10.1103\/PhysRevE.96.052302","volume":"96","author":"LEC Rocha","year":"2017","unstructured":"Rocha LEC, Masuda N, Holme P (2017) Sampling of temporal networks: methods and biases. Phys Rev E 96(5):052302","journal-title":"Phys Rev E"},{"issue":"2","key":"397_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3172867","volume":"51","author":"G Rossetti","year":"2018","unstructured":"Rossetti G, Cazabet R (2018) Community discovery in dynamic networks: a survey. ACM Comput Surv 51(2):1\u201337","journal-title":"ACM Comput Surv"},{"key":"397_CR37","unstructured":"Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. In: Proceedings of the twenty-ninth AAAI conference on artificial intelligence. AAAI\u201915, pp 4292\u20134293"},{"key":"397_CR38","doi-asserted-by":"publisher","first-page":"1945","DOI":"10.1109\/ACCESS.2019.2961936","volume":"8","author":"EA Singh","year":"2020","unstructured":"Singh EA, Cherifi H (2020) Centrality-based opinion modeling on temporal networks. IEEE Access 8:1945\u20131961","journal-title":"IEEE Access"},{"key":"397_CR41","first-page":"1","volume":"1","author":"S Sun","year":"2020","unstructured":"Sun S, Luo Q (2020) Subgraph matching with effective matching order and indexing. IEEE Trans Knowl Data Eng 1:1\u201314","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"397_CR39","doi-asserted-by":"publisher","first-page":"49778","DOI":"10.1109\/ACCESS.2019.2911181","volume":"7","author":"X Sun","year":"2019","unstructured":"Sun X, Tan Y, Wu Q, Chen B, Shen C (2019) Tm-miner: Tfs-based algorithm for mining temporal motifs in large temporal network. IEEE Access 7:49778\u201349789","journal-title":"IEEE Access"},{"issue":"10","key":"397_CR40","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.3390\/sym11101188","volume":"11","author":"X Sun","year":"2019","unstructured":"Sun X, Tan Y, Wu Q, Wang J, Shen C (2019) New algorithms for counting temporal graph pattern. Symmetry 11(10):1188","journal-title":"Symmetry"},{"issue":"6","key":"397_CR42","doi-asserted-by":"publisher","first-page":"062315","DOI":"10.1103\/PhysRevE.98.062315","volume":"98","author":"M Tizzani","year":"2018","unstructured":"Tizzani M, Lenti S, Ubaldi E, Vezzani A, Castellano C, Burioni R (2018) Epidemic spreading and aging in temporal networks with memory. Phys Rev E 98(6):062315","journal-title":"Phys Rev E"},{"key":"397_CR43","doi-asserted-by":"publisher","first-page":"7164","DOI":"10.1038\/s41598-020-63221-2","volume":"10","author":"M Torricelli","year":"2020","unstructured":"Torricelli M, Karsai M, Gauvin L (2020) weg2vec: event embedding for temporal networks. Sci Rep 10:7164","journal-title":"Sci Rep"},{"key":"397_CR44","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s41060-019-00189-x","volume":"9","author":"I Tsalouchidou","year":"2020","unstructured":"Tsalouchidou I, Baeza-Yates R, Bonchi F, Liao K, Sellis T (2020) Temporal betweenness centrality in dynamic graphs. Int J Data Sci Anal 9:257\u2013272","journal-title":"Int J Data Sci Anal"},{"issue":"4","key":"397_CR45","doi-asserted-by":"publisher","first-page":"043028","DOI":"10.1088\/1367-2630\/ab13fb","volume":"21","author":"OE Williams","year":"2019","unstructured":"Williams OE, Lillo F, Latora V (2019) Effects of memory on spreading processes in non-Markovian temporal networks. New J Phys 21(4):043028","journal-title":"New J Phys"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00397-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-021-00397-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00397-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,17]],"date-time":"2021-07-17T10:20:33Z","timestamp":1626517233000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-021-00397-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,17]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["397"],"URL":"https:\/\/doi.org\/10.1007\/s41109-021-00397-0","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,17]]},"assertion":[{"value":"3 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"55"}}