{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:41:51Z","timestamp":1773895311308,"version":"3.50.1"},"reference-count":80,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T00:00:00Z","timestamp":1569369600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T00:00:00Z","timestamp":1569369600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61622202"],"award-info":[{"award-number":["61622202"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61732003"],"award-info":[{"award-number":["61732003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61572119"],"award-info":[{"award-number":["61572119"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["N150402005"],"award-info":[{"award-number":["N150402005"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A time-dependent graph is, informally speaking, a graph structure dynamically changes with time. In such graphs, the weights associated with edges dynamically change over time, that is, the edges in such graphs are activated by sequences of time-dependent elements. Many real-life scenarios can be better modeled by time-dependent graphs, such as bioinformatics networks, transportation networks, and social networks. In particular, the time-dependent graph is a very broad concept, which is reflected in the related research with many names, including temporal graphs, evolving graphs, time-varying graphs, historical graphs, and so on. Though static graphs have been extensively studied, for their time-dependent generalizations, we are still far from a complete and mature theory of models and algorithms. In this paper, we discuss the definition and topological structure of time-dependent graphs, as well as models for their relationship to dynamic systems. In addition, we review some classic problems on time-dependent graphs, e.g., route planning, social analysis, and subgraph problem (including matching and mining). We also introduce existing time-dependent systems and summarize their advantages and limitations. We try to keep the descriptions consistent as much as possible and we hope the survey can help practitioners to understand existing time-dependent techniques.<\/jats:p>","DOI":"10.1007\/s41019-019-00105-0","type":"journal-article","created":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T11:23:17Z","timestamp":1569410597000},"page":"352-366","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":84,"title":["Time-Dependent Graphs: Definitions, Applications, and Algorithms"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3373-7060","authenticated-orcid":false,"given":"Yishu","family":"Wang","sequence":"first","affiliation":[]},{"given":"Ye","family":"Yuan","sequence":"additional","affiliation":[]},{"given":"Yuliang","family":"Ma","sequence":"additional","affiliation":[]},{"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,25]]},"reference":[{"key":"105_CR1","unstructured":"Batz GV, Sanders P (2012) Time-dependent route planning with generalized objective functions. In: European symposium on algorithms. Springer, pp 169\u2013180"},{"issue":"4","key":"105_CR2","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/s007780050028","volume":"5","author":"B Becker","year":"1996","unstructured":"Becker B, Gschwind S, Ohler T, Seeger B, Widmayer P (1996) An asymptotically optimal multiversion B-tree. VLDB J Int J Very Large Data Bases 5(4):264\u2013275","journal-title":"VLDB J Int J Very Large Data Bases"},{"issue":"1","key":"105_CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman R (1958) On a routing problem. Q Appl Math 16(1):87\u201390","journal-title":"Q Appl Math"},{"key":"105_CR4","doi-asserted-by":"crossref","unstructured":"Bhadra S, Ferreira A (2003) Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In: International conference on ad-hoc networks and wireless. Springer, pp 259\u2013270","DOI":"10.1007\/978-3-540-39611-6_23"},{"issue":"4","key":"105_CR5","doi-asserted-by":"crossref","first-page":"1461","DOI":"10.1093\/mnras\/282.4.1461","volume":"282","author":"SP Bhavsar","year":"1996","unstructured":"Bhavsar SP, Splinter RJ (1996) The superiority of the minimal spanning tree in percolation analyses of cosmological data sets. Mon Not R Astron Soc 282(4):1461\u20131466","journal-title":"Mon Not R Astron Soc"},{"issue":"7","key":"105_CR6","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom BH (1970) Space\/time trade-offs in hash coding with allowable errors. Commun ACM 13(7):422\u2013426","journal-title":"Commun ACM"},{"key":"105_CR7","doi-asserted-by":"crossref","unstructured":"Bogdanov P, Mongiov\u00ec M, Singh AK (2011) Mining heavy subgraphs in time-evolving networks. In: 2011 IEEE 11th international conference on data mining. IEEE, pp 81\u201390","DOI":"10.1109\/ICDM.2011.101"},{"key":"105_CR8","volume-title":"Modern graph theory","author":"B Bollob\u00e1s","year":"2013","unstructured":"Bollob\u00e1s B (2013) Modern graph theory, vol 184. Springer, Berlin"},{"key":"105_CR9","doi-asserted-by":"crossref","unstructured":"Braha D, Bar-Yam Y (2009) Time-dependent complex networks: dynamic centrality, dynamic motifs, and cycles of social interactions. In: Adaptive networks. Springer, pp 39\u201350","DOI":"10.1007\/978-3-642-01284-6_3"},{"key":"105_CR10","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2891565","author":"J Byun","year":"2019","unstructured":"Byun J, Woo S, Kim D (2019) ChronoGraph: enabling temporal graph traversals for efficient information diffusion analysis over time. IEEE Trans Knowl Data Eng. https:\/\/doi.org\/10.1109\/TKDE.2019.2891565","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"105_CR11","doi-asserted-by":"crossref","unstructured":"Carrasco B, Lu Y, da\u00a0Trindade JM (2011) Partitioning social networks for time-dependent queries. In: Proceedings of the 4th workshop on social network systems. ACM, p\u00a02","DOI":"10.1145\/1989656.1989658"},{"key":"105_CR12","doi-asserted-by":"crossref","unstructured":"Carroll KP, McClaran SR, Nelson EL, Barnett DM, Friesen DK, William GN (1992) AUV path planning: an A* approach to path planning with consideration of variable vehicle speeds and multiple, overlapping, time-dependent exclusion zones. In: Proceedings of the 1992 symposium on autonomous underwater vehicle technology. IEEE, pp 79\u201384","DOI":"10.1109\/AUV.1992.225191"},{"key":"105_CR13","doi-asserted-by":"crossref","unstructured":"Cattuto C, Quaggiotto M, Panisson A, Averbuch A (2013) Time-varying social networks in a graph database: a Neo4j use case. In: First international workshop on graph data management experiences and systems. ACM, p\u00a011","DOI":"10.1145\/2484425.2484442"},{"issue":"1","key":"105_CR14","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1109\/6979.994796","volume":"3","author":"I Chabini","year":"2002","unstructured":"Chabini I, Lan S (2002) Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks. IEEE Trans Intell Transp Syst 3(1):60\u201374","journal-title":"IEEE Trans Intell Transp Syst"},{"issue":"2","key":"105_CR15","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s10844-016-0437-0","volume":"49","author":"X Chen","year":"2017","unstructured":"Chen X, Zhang C, Ge B, Xiao W (2017) Temporal query processing in social network. J Intell Inf Syst 49(2):147\u2013166","journal-title":"J Intell Inf Syst"},{"issue":"3","key":"105_CR16","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1016\/0022-247X(66)90009-6","volume":"14","author":"KL Cooke","year":"1966","unstructured":"Cooke KL, Halsey E (1966) The shortest route through a network with time-dependent internodal transit times. J Math Anal Appl 14(3):493\u2013498","journal-title":"J Math Anal Appl"},{"key":"105_CR17","doi-asserted-by":"crossref","unstructured":"Cordella LP, Foggia P, Sansone C, Vento M (1999) Performance evaluation of the VF graph matching algorithm. In: Proceedings 10th international conference on image analysis and processing. IEEE, pp 1172\u20131177","DOI":"10.1109\/ICIAP.1999.797762"},{"key":"105_CR18","doi-asserted-by":"crossref","unstructured":"Dehne F, Omran MT, Sack JR (2009) Shortest paths in time-dependent FIFO networks using edge load forecasts. In: Proceedings of the second international workshop on computational transportation science. ACM, pp 1\u20136","DOI":"10.1145\/1645373.1645374"},{"issue":"1\u20132","key":"105_CR19","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/s00453-010-9461-6","volume":"62","author":"F Dehne","year":"2012","unstructured":"Dehne F, Omran MT, Sack JR (2012) Shortest paths in time-dependent FIFO networks. Algorithmica 62(1\u20132):416\u2013435","journal-title":"Algorithmica"},{"key":"105_CR20","doi-asserted-by":"crossref","unstructured":"Delling D, Wagner D (2009) Time-dependent route planning. In: Robust and online large-scale optimization. Springer, pp 207\u2013230","DOI":"10.1007\/978-3-642-05465-5_8"},{"key":"105_CR21","doi-asserted-by":"crossref","unstructured":"Demiryurek U, Banaei-Kashani F, Shahabi C, Ranganathan A (2011) Online computation of fastest path in time-dependent spatial networks. In: International symposium on spatial and temporal databases. Springer, pp 92\u2013111","DOI":"10.1007\/978-3-642-22922-0_7"},{"key":"105_CR22","doi-asserted-by":"crossref","unstructured":"Ding B, Yu JX, Qin L (2008) Finding time-dependent shortest paths over large graphs. In: Proceedings of the 11th international conference on extending database technology: advances in database technology. ACM, pp 205\u2013216","DOI":"10.1145\/1353343.1353371"},{"key":"105_CR23","doi-asserted-by":"crossref","unstructured":"Disser Y, M\u00fcller-Hannemann M, Schnee M (2008) Multi-criteria shortest paths in time-dependent train networks. In: International workshop on experimental and efficient algorithms. Springer, pp 347\u2013361","DOI":"10.1007\/978-3-540-68552-4_26"},{"key":"105_CR24","doi-asserted-by":"crossref","unstructured":"Foschini L, Hershberger J, Suri S (2011) On the complexity of time-dependent shortest paths. In: Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms. SIAM, pp 327\u2013341","DOI":"10.1137\/1.9781611973082.27"},{"key":"105_CR25","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.cor.2015.06.001","volume":"64","author":"M Gendreau","year":"2015","unstructured":"Gendreau M, Ghiani G, Guerriero E (2015) Time-dependent routing problems: a review. Comput Oper Res 64:189\u2013197","journal-title":"Comput Oper Res"},{"key":"105_CR26","unstructured":"Gonzalez JE, Xin RS, Dave A, Crankshaw D, Franklin MJ, Stoica I (2014) GraphX: graph processing in a distributed dataflow framework. In: 11th USENIX symposium on operating systems design and implementation (OSDI 14), pp 599\u2013613"},{"key":"105_CR27","doi-asserted-by":"crossref","unstructured":"Gunturi V, Shekhar S, Bhattacharya A (2010) Minimum spanning tree on spatio-temporal networks. In: International conference on database and expert systems applications. Springer, pp 149\u2013158","DOI":"10.1007\/978-3-642-15251-1_11"},{"issue":"6995","key":"105_CR28","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/nature02555","volume":"430","author":"JDJ Han","year":"2004","unstructured":"Han JDJ, Bertin N, Hao T, Goldberg DS, Berriz GF, Zhang LV, Dupuy D, Walhout AJ, Cusick ME, Roth FP et al (2004) Evidence for dynamically organized modularity in the yeast protein\u2013protein interaction network. Nature 430(6995):88","journal-title":"Nature"},{"key":"105_CR29","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1214\/09-EJS548","volume":"4","author":"S Hanneke","year":"2010","unstructured":"Hanneke S, Fu W, Xing EP et al (2010) Discrete temporal models of social networks. Electron J Stat 4:585\u2013605","journal-title":"Electron J Stat"},{"issue":"1","key":"105_CR30","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1137\/1024022","volume":"24","author":"J Hartmanis","year":"1982","unstructured":"Hartmanis J (1982) Computers and intractability: a guide to the theory of NP-completeness. SIAM Rev 24(1):90","journal-title":"SIAM Rev"},{"issue":"6","key":"105_CR31","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M Held","year":"1970","unstructured":"Held M, Karp RM (1970) The traveling-salesman problem and minimum spanning trees. Oper Res 18(6):1138\u20131162","journal-title":"Oper Res"},{"issue":"2","key":"105_CR32","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.socnet.2004.01.007","volume":"26","author":"P Holme","year":"2004","unstructured":"Holme P, Edling CR, Liljeros F (2004) Structure and time evolution of an internet dating community. Soc Netw 26(2):155\u2013174","journal-title":"Soc Netw"},{"issue":"3","key":"105_CR33","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme P, Saram\u00e4ki J (2012) Temporal networks. Phys Rep 519(3):97\u2013125","journal-title":"Phys Rep"},{"key":"105_CR34","doi-asserted-by":"crossref","unstructured":"Huang H, Song J, Lin X, Ma S, Huai J (2016) TGraph: a temporal graph data management system. In: Proceedings of the 25th ACM international on conference on information and knowledge management. ACM, pp 2469\u20132472","DOI":"10.1145\/2983323.2983335"},{"key":"105_CR35","doi-asserted-by":"crossref","unstructured":"Huang S, Fu AWC, Liu R (2015) Minimum spanning trees in temporal graphs. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data. ACM, pp 419\u2013430","DOI":"10.1145\/2723372.2723717"},{"key":"105_CR36","doi-asserted-by":"crossref","unstructured":"Huo W, Tsotras VJ (2014) Efficient temporal shortest path queries on evolving social graphs. In: Proceedings of the 26th international conference on scientific and statistical database management. ACM, p\u00a038","DOI":"10.1145\/2618243.2618282"},{"issue":"2","key":"105_CR37","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/S0377-2217(02)00147-9","volume":"144","author":"S Ichoua","year":"2003","unstructured":"Ichoua S, Gendreau M, Potvin JY (2003) Vehicle dispatching with time-dependent travel times. Eur J Oper Res 144(2):379\u2013396","journal-title":"Eur J Oper Res"},{"key":"105_CR38","doi-asserted-by":"crossref","first-page":"692","DOI":"10.1016\/j.procs.2017.05.379","volume":"109","author":"A Idri","year":"2017","unstructured":"Idri A, Oukarfi M, Boulmakoul A, Zeitouni K, Masri A (2017) A new time-dependent shortest path algorithm for multimodal transportation network. Procedia Comput Sci 109:692\u2013697","journal-title":"Procedia Comput Sci"},{"issue":"4","key":"105_CR39","doi-asserted-by":"crossref","first-page":"820","DOI":"10.1006\/jcss.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe D, Kleinberg J, Kumar A (2002) Connectivity and inference problems for temporal networks. J Comput Syst Sci 64(4):820\u2013842","journal-title":"J Comput Syst Sci"},{"key":"105_CR40","unstructured":"Khoa VD, Pham TV, Nguyen HT, Van\u00a0Hoai T (2015) Multi\u2013criteria route planning in bus network. In: IFIP international conference on computer information systems and industrial management. Springer, pp 535\u2013546"},{"key":"105_CR41","doi-asserted-by":"crossref","unstructured":"Khurana U, Deshpande A (2013) Efficient snapshot retrieval over historical graph data. In: 2013 IEEE 29th international conference on data engineering (ICDE). IEEE, pp 997\u20131008","DOI":"10.1109\/ICDE.2013.6544892"},{"key":"105_CR42","doi-asserted-by":"crossref","unstructured":"K\u00f6hler E, Langkau K, Skutella M (2002) Time-expanded graphs for flow-dependent transit times. In: European symposium on algorithms. Springer, pp 599\u2013611","DOI":"10.1007\/3-540-45749-6_53"},{"key":"105_CR43","doi-asserted-by":"crossref","unstructured":"Kollmitz M, Hsiao K, Gaa J, Burgard W (2015) Time dependent planning on a layered social cost map for human-aware robot navigation. In: 2015 European conference on mobile robots (ECMR). IEEE, pp 1\u20136","DOI":"10.1109\/ECMR.2015.7324184"},{"issue":"4","key":"105_CR44","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1007\/s00453-015-0003-0","volume":"74","author":"S Kontogiannis","year":"2016","unstructured":"Kontogiannis S, Zaroliagis C (2016) Distance oracles for time-dependent networks. Algorithmica 74(4):1404\u20131434","journal-title":"Algorithmica"},{"issue":"1","key":"105_CR45","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1186\/1752-0509-4-130","volume":"4","author":"S Lebre","year":"2010","unstructured":"Lebre S, Becq J, Devaux F, Stumpf MP, Lelandais G (2010) Statistical inference of the time-varying structure of gene-regulation networks. BMC Syst Biol 4(1):130","journal-title":"BMC Syst Biol"},{"issue":"2","key":"105_CR46","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1109\/TMC.2004.10","volume":"3","author":"D Li","year":"2004","unstructured":"Li D, Jia X, Liu H (2004) Energy efficient broadcast routing in static ad hoc wireless networks. IEEE Trans Mob Comput 3(2):144\u2013151","journal-title":"IEEE Trans Mob Comput"},{"issue":"1\u20132","key":"105_CR47","doi-asserted-by":"crossref","first-page":"723","DOI":"10.14778\/1920841.1920934","volume":"3","author":"Z Li","year":"2010","unstructured":"Li Z, Ding B, Han J, Kays R (2010) Swarm: mining relaxed temporal moving object clusters. Proc VLDB Endow 3(1\u20132):723\u2013734","journal-title":"Proc VLDB Endow"},{"issue":"8","key":"105_CR48","doi-asserted-by":"crossref","first-page":"716","DOI":"10.14778\/2212351.2212354","volume":"5","author":"Y Low","year":"2012","unstructured":"Low Y, Bickson D, Gonzalez J, Guestrin C, Kyrola A, Hellerstein JM (2012) Distributed GraphLab: a framework for machine learning and data mining in the cloud. Proc VLDB Endow 5(8):716\u2013727","journal-title":"Proc VLDB Endow"},{"key":"105_CR49","doi-asserted-by":"crossref","unstructured":"Ma S, Hu R, Wang L, Lin X, Huai J (2017) Fast computation of dense temporal subgraphs. In: 2017 IEEE 33rd international conference on data engineering (ICDE). IEEE, pp 361\u2013372","DOI":"10.1109\/ICDE.2017.95"},{"issue":"3","key":"105_CR50","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1287\/trsc.26.3.185","volume":"26","author":"C Malandraki","year":"1992","unstructured":"Malandraki C, Daskin MS (1992) Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. Transp Sci 26(3):185\u2013200","journal-title":"Transp Sci"},{"key":"105_CR51","doi-asserted-by":"crossref","unstructured":"Malewicz G, Austern MH, Bik AJ, Dehnert JC, Horn I, Leiser N, Czajkowski G (2010) Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD international conference on management of data. ACM pp 135\u2013146","DOI":"10.1145\/1807167.1807184"},{"issue":"19","key":"105_CR52","doi-asserted-by":"crossref","first-page":"2903","DOI":"10.1093\/bioinformatics\/btw347","volume":"32","author":"M Marchetti-Bowick","year":"2016","unstructured":"Marchetti-Bowick M, Yin J, Howrylak JA, Xing EP (2016) A time-varying group sparse additive model for genome-wide association studies of dynamic complex traits. Bioinformatics 32(19):2903\u20132910","journal-title":"Bioinformatics"},{"issue":"1","key":"105_CR53","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K Menger","year":"1927","unstructured":"Menger K (1927) Zur allgemeinen kurventheorie. Fundam Math 10(1):96\u2013115","journal-title":"Fundam Math"},{"issue":"4","key":"105_CR54","doi-asserted-by":"crossref","first-page":"1416","DOI":"10.1007\/s00453-018-0478-6","volume":"81","author":"GB Mertzios","year":"2019","unstructured":"Mertzios GB, Michail O, Spirakis PG (2019) Temporal network optimization subject to connectivity constraints. Algorithmica 81(4):1416\u20131449","journal-title":"Algorithmica"},{"issue":"4","key":"105_CR55","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1080\/15427951.2016.1177801","volume":"12","author":"O Michail","year":"2016","unstructured":"Michail O (2016) An introduction to temporal graphs: an algorithmic perspective. Internet Math 12(4):239\u2013280","journal-title":"Internet Math"},{"issue":"10","key":"105_CR56","doi-asserted-by":"crossref","first-page":"108701","DOI":"10.1103\/PhysRevLett.114.108701","volume":"114","author":"A Moinet","year":"2015","unstructured":"Moinet A, Starnini M, Pastor-Satorras R (2015) Burstiness and aging in social temporal networks. Phys Rev Lett 114(10):108701","journal-title":"Phys Rev Lett"},{"key":"105_CR57","doi-asserted-by":"crossref","unstructured":"Nannicini G, Delling D, Liberti L, Schultes D (2008) Bidirectional A* search for time-dependent fast paths. In: International workshop on experimental and efficient algorithms. Springer, pp 334\u2013346","DOI":"10.1007\/978-3-540-68552-4_25"},{"issue":"2","key":"105_CR58","doi-asserted-by":"crossref","first-page":"023101","DOI":"10.1063\/1.3697996","volume":"22","author":"V Nicosia","year":"2012","unstructured":"Nicosia V, Tang J, Musolesi M, Russo G, Mascolo C, Latora V (2012) Components in time-varying graphs. Chaos Interdiscip J Nonlinear Sci 22(2):023101","journal-title":"Chaos Interdiscip J Nonlinear Sci"},{"issue":"3","key":"105_CR59","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/79147.214078","volume":"37","author":"A Orda","year":"1990","unstructured":"Orda A, Rom R (1990) Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J ACM (JACM) 37(3):607\u2013625","journal-title":"J ACM (JACM)"},{"issue":"1","key":"105_CR60","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1093\/bib\/bbp057","volume":"11","author":"TM Przytycka","year":"2010","unstructured":"Przytycka TM, Singh M, Slonim DK (2010) Toward the dynamic interactome: it\u2019s about time. Brief Bioinform 11(1):15\u201329","journal-title":"Brief Bioinform"},{"key":"105_CR61","first-page":"2","volume":"12","author":"E Pyrga","year":"2008","unstructured":"Pyrga E, Schulz F, Wagner D, Zaroliagis C (2008) Efficient models for timetable information in public transportation systems. J Exp Algorithmics (JEA) 12:2\u20134","journal-title":"J Exp Algorithmics (JEA)"},{"issue":"24","key":"105_CR62","doi-asserted-by":"crossref","first-page":"2054","DOI":"10.1016\/j.physleta.2016.04.025","volume":"380","author":"X Qiu","year":"2016","unstructured":"Qiu X, Zhao L, Wang J, Wang X, Wang Q (2016) Effects of time-dependent diffusion behaviors on the rumor spreading in social networks. Phys Lett A 380(24):2054\u20132063","journal-title":"Phys Lett A"},{"key":"105_CR63","first-page":"7","volume":"2007","author":"A Rao","year":"2007","unstructured":"Rao A, Hero AO III, Engel JD et al (2007) Inferring time-varying network topologies from gene expression data. EURASIP J Bioinform Syst Biol 2007:7","journal-title":"EURASIP J Bioinform Syst Biol"},{"key":"105_CR64","unstructured":"Redmond U, Cunningham P (2016) Subgraph isomorphism in temporal networks. arXiv preprint arXiv:1605.02174"},{"issue":"3","key":"105_CR65","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1093\/jurban\/78.3.446","volume":"78","author":"CS Riolo","year":"2001","unstructured":"Riolo CS, Koopman JS, Chick SE (2001) Methods and measures for the description of epidemiologic contact networks. J Urban Health 78(3):446\u2013457","journal-title":"J Urban Health"},{"issue":"1","key":"105_CR66","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1109\/TKDE.2018.2823754","volume":"31","author":"K Semertzidis","year":"2019","unstructured":"Semertzidis K, Pitoura E (2019) Top-$$k$$ durable graph pattern queries on temporal graphs. IEEE Trans Knowl Data Eng 31(1):181\u2013194","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"105_CR67","doi-asserted-by":"crossref","unstructured":"Steinbauer M, Anderst-Kotsis G (2016) Dynamograph: a distributed system for large-scale, temporal graph processing, its implementation and first observations. In: Proceedings of the 25th international conference companion on world wide web. International World Wide Web Conferences Steering Committee, pp 861\u2013866","DOI":"10.1145\/2872518.2889293"},{"issue":"4","key":"105_CR68","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1016\/S0010-2180(98)00023-6","volume":"115","author":"S Subramaniam","year":"1998","unstructured":"Subramaniam S, Pope S (1998) A mixing model for turbulent reactive flows based on euclidean minimum spanning trees. Combust Flame 115(4):487\u2013514","journal-title":"Combust Flame"},{"key":"105_CR69","doi-asserted-by":"crossref","unstructured":"Sun X, Tan Y, Wu Q, Wang J (2017) Hasse diagram based algorithm for continuous temporal subgraph query in graph stream. In: 2017 6th international conference on computer science and network technology (ICCSNT). IEEE, pp 241\u2013246","DOI":"10.1109\/ICCSNT.2017.8343695"},{"key":"105_CR70","doi-asserted-by":"crossref","unstructured":"Tang J, Musolesi M, Mascolo C, Latora V (2009) Temporal distance metrics for social network analysis. In: Proceedings of the 2nd ACM workshop on online social networks. ACM, pp 31\u201336","DOI":"10.1145\/1592665.1592674"},{"key":"105_CR71","doi-asserted-by":"crossref","unstructured":"van\u00a0der Tuin MS, de\u00a0Weerdt M, Batz GV (2018) Route planning with breaks and truck driving bans using time-dependent contraction hierarchies. In: Proceedings of the twenty-eighth international conference on automated planning and scheduling, ICAPS 2018, Delft, The Netherlands, June 24\u201329, 2018, pp 356\u2013365","DOI":"10.1609\/icaps.v28i1.13912"},{"key":"105_CR72","doi-asserted-by":"crossref","unstructured":"Wang C, Tang J, Sun J, Han J (2011) Dynamic social influence analysis through time-dependent factor graphs. In: 2011 International conference on advances in social networks analysis and mining. IEEE, pp 239\u2013246","DOI":"10.1109\/ASONAM.2011.116"},{"key":"105_CR73","doi-asserted-by":"crossref","unstructured":"Wang S, Lin W, Yang Y, Xiao X, Zhou S (2015) Efficient route planning on public transportation networks: a labelling approach. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data. ACM, pp 967\u2013982","DOI":"10.1145\/2723372.2749456"},{"key":"105_CR74","doi-asserted-by":"crossref","unstructured":"Wang W, Yang L, Liao Q, Zhu X, Zhang Q (2015) TiSA: time-dependent social network advertising. In: 2015 IEEE international conference on communications (ICC). IEEE, pp 1188\u20131193","DOI":"10.1109\/ICC.2015.7248484"},{"issue":"9","key":"105_CR75","doi-asserted-by":"crossref","first-page":"721","DOI":"10.14778\/2732939.2732945","volume":"7","author":"H Wu","year":"2014","unstructured":"Wu H, Cheng J, Huang S, Ke Y, Lu Y, Xu Y (2014) Path problems in temporal graphs. Proc VLDB Endow 7(9):721\u2013732","journal-title":"Proc VLDB Endow"},{"issue":"11","key":"105_CR76","doi-asserted-by":"crossref","first-page":"2927","DOI":"10.1109\/TKDE.2016.2594065","volume":"28","author":"H Wu","year":"2016","unstructured":"Wu H, Cheng J, Ke Y, Huang S, Huang Y, Wu H (2016) Efficient algorithms for temporal path computation. IEEE Trans Knowl Data Eng 28(11):2927\u20132942","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"105_CR77","doi-asserted-by":"crossref","unstructured":"Xu Y, Huang J, Liu A, Li Z, Yin H, Zhao L (2017) Time-constrained graph pattern matching in a large temporal graph. In: Asia-Pacific web (APWeb) and web-age information management (WAIM) joint conference on web and big data. Springer, pp 100\u2013115","DOI":"10.1007\/978-3-319-63579-8_9"},{"key":"105_CR78","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.trb.2016.11.012","volume":"96","author":"L Yang","year":"2017","unstructured":"Yang L, Zhou X (2017) Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: linear mixed integer programming reformulations. Transp Res Part B Methodol 96:68\u201391","journal-title":"Transp Res Part B Methodol"},{"key":"105_CR79","doi-asserted-by":"crossref","unstructured":"Yang Y, Yan D, Wu H, Cheng J, Zhou S, Lui J (2016) Diversified temporal subgraph pattern mining. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1965\u20131974","DOI":"10.1145\/2939672.2939848"},{"key":"105_CR80","doi-asserted-by":"crossref","unstructured":"Zhao Q, Tian Y, He Q, Oliver N, Jin R, Lee WC (2010) Communication motifs: a tool to characterize social communications. In: Proceedings of the 19th ACM international conference on Information and knowledge management. ACM, pp 1645\u20131648","DOI":"10.1145\/1871437.1871694"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-019-00105-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41019-019-00105-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-019-00105-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T21:45:35Z","timestamp":1664487935000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s41019-019-00105-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,25]]},"references-count":80,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["105"],"URL":"https:\/\/doi.org\/10.1007\/s41019-019-00105-0","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,25]]},"assertion":[{"value":"1 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 September 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Informed consent was obtained from all individual participants.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed consent"}}]}}