Time-Dependent Graphs: Definitions, Applications, and Algorithms

作     者：Wang, Yishu Yuan, Ye Ma, Yuliang Wang, Guoren 

作者机构：Northeastern Univ Sch Comp Sci & Engn Shenyang Peoples R China Beijing Inst Technol Sch Comp Sci & Technol Beijing Peoples R China 

出 版 物：《DATA SCIENCE AND ENGINEERING》 (Data Sci. Eng.)

年 卷 期：2019年第4卷第4期

页      面：352-366页

基　　金：National Natural Science Foundation of China for Excellent Young Scientists National Natural Science Foundation of China [61732003, 61572119] Fundamental Research Funds for the Central Universities [N150402005] 

主　　题：Time-dependent network Graph data management Network analysis Graph system 

摘      要：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.