# Recent Advances in Efficient Dynamic Graph Processing
## 1 Introduction
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multicolumn{1}{c}{**Problem**} & \multicolumn{1}{c}{**Fully Dynamic**} & \multicolumn{1}{c}{**Incremental Dynamic**} & \multicolumn{1}{c}{**Decremental Dynamic**} & \multicolumn{1}{c}{**Streaming Dynamic**} & \multicolumn{1}{c}{**Single Update**} & \multicolumn{1}{c}{**Batch Update**} \\ \hline \multirow{5}{*}{Centrality} & Betweenness & [17; 25; 26; 37; 38; 39] & [17; 18; 25; 26; 39] & [17; 25; 26; 37; 39] & [18; 26; 42] & [17; 26; 38; 43] & [17; 26; 38; 39; 43] & [25; 37; 41] \\  & Centrality & Closeness & [37; 44; 45; 37; 46; 47] & [37; 44; 45; 37; 44; 45; 46; 47] & [45] & [44; 46; 47] & [37] \\ \cline{2-8}  & Eccentricity & [48] & [48] & [48] & - & [48] & - \\ \hline \multirow{3}{*}{Graph Coloring} & Vertex & [49; 50; 51] & [49; 51; 52; 53] & [49; 50; 53] & - & [49; 52; 53; 54] & [50; 51] \\  & Coloring & [55] & [54; 55; 56; 57; 58; 59; 60; 61] & - & [54; 55; 56; 59; 60; 61] & - & [54; 55; 56; 57; 58; 61] & [59; 60] \\ \hline \multirow{5}{*}{Cohesive Subgraph} & Clique & [62] & [16; 62; 63; 65; 64; 66; 67] & [62; 63; 65] & - & [65] & [16; 62; 64; 66; 67; 68; 69; 62; 64] \\ \cline{2-8}  & Biclique & - & [66; 67] & - & - & [67] & [66] \\ \cline{2-8}  & \(k\)-core & - & [19; 20; 68; 69; 70; 71; 72; 73; 74; 75; 76] & - & [70; 74] & [19; 20; 68; 69; 71; 72; 73; 75; 76] \\ \cline{2-8}  & \(k\)-truss & - & [21; 77; 78; 79; 81; 82] & [21; 77; 79; 81; 82] & - & [21; 79; 80; 82] & [77; 78; 79; 81] \\ \cline{2-8}  & Community & [83] & [83; 84; 87; 85; 86; 87; 88] & [83; 84; 87] & [89] & [84; 89] & [83; 85; 86; 87; 88] \\ \hline \multirow{5}{*}{Path Traversal} & DFS & [90; 91; 92; 93; 94] & [90; 91; 92; 94] & [90; 93; 94; 98] & - & [90; 91; 92] & [91; 93; 94; 99; 95; 96; 97; 98] \\  & Shortest Distance & [99; 100; 101; 91; 92; 93; 94; 99; 95; 96; 97; 98; 99; 100; 99; 101; 99; 102; 99; 103; 94; 104; 105; 106; 107; 108] & - & [100; 103; 105, 106; 109] & [99; 101; 106; 107; 108] \\ \cline{2-8}  & Reachability & - & [110] & - & - & [110] & - \\ \hline \multirow{3}{*}{Graph Separation} & Graph & [111; 112; 113; 114] & [24; 11; 113; 115; 114] & [111; 112; 114; 115; 116; 117] & [111] & [112; 113; 115] \\  & Partition & [118] & [118; 119; 120] & [118] & - & [118; 120] & [119] \\ \hline \multirow{2}{*}{Systems} & Systems & - & [121] & - & [122; 123; 124] & - & - \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Classification of recent works in dynamic graphs. Graph SeparationGraph separation aims to separate the graph into many partitions or clusters. One is to divide the whole graph into several partitions which is important in distributed graph computing systems. Another is to find dense clusters in graphs, for instance, SCAN is the most representative algorithm for clustering. Existing related surveys focus either on dynamic graph representation and embedding in the field of machine learning [11; 12] or on particular dynamic graph problems such as pattern mining [13], anomaly detection [125], and GPU based processing [126]. For other surveys, they do not focus on dynamic graphs. Among them, [127] is the most similar with our survey which also focuses on dynamic graph algorithms. However, Ref. [127] only focuses on the algorithms on fully dynamic graphs, ignoring not only massive partial dynamic algorithms but also the parallel and distributed algorithms. Motivated by this, to fill the gap in the existing reviews, we cover a broader range by surveying papers for dynamic graphs in different graph problem categories, including fully dynamic algorithms, incremental dynamic algorithms, and streaming dynamic algorithms. Moreover, we detail how each algorithm handles updates, distinguishing among serial update, parallel update and distributed update. Additionally, for each class of algorithms, we analyze the advances of existing works and offer a clear comparison of the theoretical complexity across them.