Fast Computation of Dense Temporal Subgraphs Shuai Ma, Renjun Hu, Luoshu Wang, Xuelian Lin, Jinpeng Huai SKLSDE Lab, beihang university china Beijing Advanced Innovation Center for Big Data and Brain Computing 北京航空航天大学 BEIHANGUNIVERSITY
Fast Computation of Dense Temporal Subgraphs Shuai Ma, Renjun Hu, Luoshu Wang, Xuelian Lin, Jinpeng Huai SKLSDE Lab, Beihang University, China Beijing Advanced Innovation Center for Big Data and Brain Computing 1
Graphs are dynamic The Soil Food Web OCIAL NETWORK A B C Aug 10 Oct 29 All images are downloaded from Google
Graphs are dynamic 2 *All images are downloaded from Google
Motivation Temporal graph: a continuous sequence of snapshots(each snapshot records the status of a graph at a specific timestamp) Dense temporal subgraph: a subgraph having heavy edge weights over a continuous time period Space M Space Mi Museu COLUMB Columbia K San-D Westfield Horton plaza Westfield Horton Plaza FTS Manchester Grand Live traffic, Faster Manchester Grand Live traffic Fastmmnn Hyatt San Diego a dense temporal subgraphs corresponds to a crowded area spanning over a continuous time period
Motivation 3 A dense temporal subgraphs corresponds to a crowded area spanning over a continuous time period. Temporal graph: a continuous sequence of snapshots (each snapshot records the status of a graph at a specific timestamp) Dense temporal subgraph: a subgraph having heavy edge weights over a continuous time period … … …
Outline The FDs problem: analyses and challenges a data-driven approach Experimental stud Summary
Outline ➢ The FDS problem: analyses and challenges ➢ A data-driven approach ➢ Experimental study ➢ Summary 4
Temporal graphs and subgraphs Temporal graph G(V, E, F)with T timestamps nodes and edges keep unchanged 235 edge weights constantly and regularly vary 叫252 with timestamps -7.-2 T snapshots: G,(V, E, F1, G2(V, E, F2) GT(V,E,F density(G)=36 Temporal subgraph H(Vs, Es, Fs, i, j time interval [,jc[1,T 7,5-2 subgraph (Vs, Es of (V,E denote H(V,, Fs,i, j as G[, j] density (H)=21 ohesive density density(G) sum of eage weights among all snapshots 5
Temporal graphs and subgraphs 5 Temporal graph G(V, E, F) with T timestamps • nodes and edges keep unchanged • edge weights constantly and regularly vary with timestamps • T snapshots: G1 (V, E, F1 ), G2 (V, E, F2 ), …, GT (V, E, FT) Temporal subgraph H(Vs , Es , Fs , i, j) • time interval [i, j] ⊆ [1, T] • subgraph (Vs , Es ) of (V, E) • denote H(V, E, Fs , i, j) as G[i, j] Cohesive density cdensity(G) • sum of edge weights among all snapshots cdensity(G)=36 cdensity(H)=21