Recent Advances in Efficient Dynamic Graph Processing
Source abstract
Abstract
Graph as one of the most fundamental and representative data structures has found a wide spectrum of emerging application domains such as social media, financial transactions, biology science, and road networks. Recently, with the proliferation of graph applications, graph processing has attracted much attention in both industry and academia. Among them, most existing works focus on the static graphs in which the vertices and edges are immutable. However, in the real world, graphs are constantly and dynamically changing, bringing tricky challenges to process such dynamic graphs. This paper surveys the recent advances in dynamic graph processing, including centrality, graph coloring, cohesive subgraph, path traversal, and graph separation. We summarize the computational complexity models for dynamic algorithm analysis, theoretically compare the efficiency of algorithms among different research topics. Moreover, we also explore the research opportunities for the future.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Graph Theory and Algorithms · Advanced Graph Neural Networks · Complex Network Analysis Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Computer Science and Artificial Intelligence, Wuhan University of Technology, Wuhan 430070, China
College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, Australia
Funding
Natural Science Foundation of Jiangsu Province · National Key R&D Program of China · National Natural Science Foundation of China
References (100+)
Show source-provided references
1. SNGPLDP: Social network graph generation based on personalised local differential privacy10.1504/IJAACS.2024.137062 ↗
2. Berners-Lee, T., and Fischetti, M. (2000). Weaving the Web—The Original Design and Ultimate Destiny of the World Wide Web by Its Inventor, HarperBusiness.
3. Brandão, M.A., Moro, M.M., Lopes, G.R., and de Oliveira, J.P.M. (2013, January 13–17). Using link semantics to recommend collaborations in academic social networks. Proceedings of the WWW, Rio de Janeiro, Brazil.10.1145/2487788.2488058 ↗
4. Mukhtar, S. (2023). Protein-Protein Interactions: Methods and Protocols, Springer. Methods in Molecular Biology.10.1007/978-1-0716-3327-4 ↗
5. Recent Advances in Graph Partitioning10.1007/978-3-319-49487-6_4 ↗
6. Aynaud, T., and Guillaume, J. (June, January 31). Static community detection algorithms for evolving networks. Proceedings of the WiOpt, Avignon, France.
7. Chen, Z., Yuan, L., Lin, X., Qin, L., and Yang, J. (2020, January 20–24). Efficient Maximal Balanced Clique Enumeration in Signed Networks. Proceedings of the WWW, Taipei, China.10.1145/3366423.3380119 ↗
8. Mittal, A., Jain, P., Mathur, S., and Bhatt, P. (2011, January 3–5). Graph Coloring with Minimum Colors: An Easy Approach. Proceedings of the International Conference on Communication Systems and Network Technologies, Katra, India.10.1109/CSNT.2011.137 ↗
9. Ghaffari, M., and Su, H.H. (2017, January 16–19). Distributed degree splitting, edge coloring, and orientations. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain.10.1137/1.9781611974782.166 ↗
10. Riedy, E.J., Meyerhenke, H., Ediger, D., and Bader, D.A. (2011, January 11–14). Parallel Community Detection for Massive Graphs. Proceedings of the PPAM, Torun, Poland.10.1007/978-3-642-31464-3_29 ↗
11. de Barros, C.D.T., Mendonça, M.R.F., Vieira, A.B., and Ziviani, A. (2023). A Survey on Embedding Dynamic Graphs. ACM Comput. Surv., 55.10.1145/3483595 ↗
12. Kazemi, S.M., Goel, R., Jain, K., Kobyzev, I., Sethi, A., Forsyth, P., and Poupart, P. (2020). Representation Learning for Dynamic Graphs: A Survey. J. Mach. Learn. Res., 21.
13. A survey of pattern mining in dynamic graphs10.1002/widm.1372 ↗
14. Monical, C., and Stonedahl, F. (2018, January 12–16). Static vs. dynamic populations in genetic algorithms for coloring a dynamic graph. Proceedings of the GECCO, Genetic and Evolutionary Computation Conference, Vancouver, BC, Canada.
15. Li, C., Han, J., He, G., Jin, X., Sun, Y., Yu, Y., and Wu, T. (2010, January 22–26). Fast computation of SimRank for static and dynamic information networks. Proceedings of the EDBT, Lausanne, Switzerland.10.1145/1739041.1739098 ↗
16. Das, A., Sanei-Mehri, S., and Tirthapura, S. (2020). Shared-memory Parallel Maximal Clique Enumeration from Static and Dynamic Graphs. ACM Trans. Parallel Comput., 7.10.1145/3380936 ↗
17. Lee, M., Lee, J., Park, J.Y., Choi, R.H., and Chung, C. (2012, January 16–20). QUBE: A quick algorithm for updating betweenness centrality. Proceedings of the WWW, Lyon, France.10.1145/2187836.2187884 ↗
18. Green, O., McColl, R., and Bader, D.A. (2012, January 3–5). A Fast Algorithm for Streaming Betweenness Centrality. Proceedings of the SocialCom/PASSAT, Amsterdam, The Netherlands.
19. Hierarchical Core Maintenance on Large Dynamic Graphs10.14778/3446095.3446099 ↗
20. Fast Core Maintenance in Dynamic Graphs10.1109/TCSS.2021.3064836 ↗
21. Zhang, Y., and Yu, J.X. (July, January 30). Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs. Proceedings of the SIGMOD, Amsterdam, The Netherlands.
22. Vieira, M.V., Fonseca, B.M., Damazio, R., Golgher, P.B., Reis, D.d.C., and Ribeiro-Neto, B. (2007, January 6–10). Efficient search ranking in social networks. Proceedings of the Sixteenth ACM Conference on Conference on Information and Knowledge Management, Lisbon, Portugal.10.1145/1321440.1321520 ↗
23. Daccer: Distributed assessment of the closeness centrality ranking in complex networks10.1016/j.comnet.2013.05.001 ↗
24. Nicoara, D., Kamali, S., Daudjee, K., and Chen, L. (2015, January 23–27). Hermes: Dynamic Partitioning for Distributed Social Network Graph Databases. Proceedings of the EDBT, Brussels, Belgium.
25. Efficient algorithms for updating betweenness centrality in fully dynamic graphs10.1016/j.ins.2015.07.053 ↗
26. Tripathy, A., and Green, O. (2018, January 25–27). Scaling betweenness centrality in dynamic graphs. Proceedings of the HPEC, Waltham, MA, USA.10.1109/HPEC.2018.8547518 ↗
27. Narayanan, S. (2005). The Betweenness Centrality of Biological Networks. [Ph.D. Thesis, Virginia Tech].
28. Efficient (α, β)-core computation in bipartite graphs10.1007/s00778-020-00606-9 ↗
29. Energy optimal real-time navigation system10.1109/MITS.2014.2324000 ↗
30. Weirdnodes: Centrality based anomaly detection on temporal networks for the anti-financial crime domain10.1007/s41109-025-00702-1 ↗
31. Li, X., Cao, X., Qiu, X., Zhao, J., and Zheng, J. (2017, January 13–16). Intelligent anti-money laundering solution based upon novel community detection in massive transaction networks on spark. Proceedings of the CBD, Shanghai, China.10.1109/CBD.2017.38 ↗
32. The application of social network analysis algorithms in a system supporting money laundering detection10.1016/j.ins.2014.10.015 ↗
33. Multi-Cluster Graph (MCG): A Novel Clustering-Based Multi-Relation Graph Neural Networks for Stock Price Forecasting10.1109/ACCESS.2024.3476159 ↗
34. Facebook (2025, February 20). Facebook Newsroom. Available online: https://about.fb.com/news/.
35. Twitter (2025, February 20). Twitter Blog. Available online: https://blog.twitter.com/.
36. Maximum and top-k diversified biclique search at scale10.1007/s00778-021-00681-6 ↗
37. Shukla, K., Regunta, S.C., Tondomker, S.H., and Kothapalli, K. (July, January 29). Efficient parallel algorithms for betweenness-and closeness-centrality in dynamic graphs. Proceedings of the ICS, Barcelona, Spain.
38. Fully Dynamic Betweenness Centrality Maintenance on Massive Networks10.14778/2850578.2850580 ↗
39. Parallel Algorithm for Incremental Betweenness Centrality on Large Graphs10.1109/TPDS.2017.2763951 ↗
40. Kas, M., Wachs, M., Carley, K.M., and Carley, L.R. (2013, January 25–28). Incremental algorithm for updating betweenness centrality in dynamically growing networks. Proceedings of the ASONAM, Niagara Falls, ON, Canada.10.1145/2492517.2492533 ↗
41. Bergamini, E., Meyerhenke, H., and Staudt, C. (2015, January 5). Approximating Betweenness Centrality in Large Evolving Networks. Proceedings of the ALENEX, San Diego, CA, USA.
42. Computing Betweenness Centrality in Link Streams10.7155/jgaa.00620 ↗
43. Goel, K., Singh, R.R., Iyengar, S., and Gupta, S. (2013, January 14–15). A Faster Algorithm to Update Betweenness Centrality after Node Alteration. Proceedings of the WAW, Cambridge, MA, USA.10.1007/978-3-319-03536-9_14 ↗
44. Kas, M., Carley, K.M., and Carley, L.R. (2013, January 25–28). Incremental closeness centrality for dynamically changing social networks. Proceedings of the ASONAM, Niagara Falls, ON, Canada.10.1145/2492517.2500270 ↗
45. Sariyüce, A.E., Saule, E., Kaya, K., and Çatalyürek, Ü.V. (2013, January 23–27). STREAMER: A distributed framework for incremental closeness centrality computation. Proceedings of the CLUSTER, Indianapolis, IN, USA.10.1109/CLUSTER.2013.6702680 ↗
46. Yen, C., Yeh, M., and Chen, M. (2013, January 7–10). An Efficient Approach to Updating Closeness Centrality and Average Path Length in Dynamic Networks. Proceedings of the ICDM, Dallas, TX, USA.10.1109/ICDM.2013.135 ↗
47. Shao, Z., Guo, N., Gu, Y., Wang, Z., Li, F., and Yu, G. (2020, January 24–27). Efficient closeness centrality computation for dynamic graphs. Proceedings of the DASFAA, Jeju, Republic of Korea.10.1007/978-3-030-59416-9_32 ↗
48. Eccentricities on small-world networks10.1007/s00778-019-00566-9 ↗
49. Improved dynamic graph coloring
50. Sallinen, S., Iwabuchi, K., Poudel, S., Gokhale, M.B., Ripeanu, M., and Pearce, R.A. (2016, January 13–18). Graph colouring as a challenge problem for dynamic graph processing on distributed systems. Proceedings of the SC, Salt Lake City, UT, USA.10.1109/SC.2016.29 ↗
51. ACODYGRA: An agent algorithm for coloring dynamic graphs
52. Dynamic Graph Coloring10.1007/s00453-018-0473-y ↗
53. Effective and Efficient Dynamic Graph Coloring10.14778/3157794.3157802 ↗
54. Bhattacharya, S., Chakrabarty, D., Henzinger, M., and Nanongkai, D. (2018, January 7–10). Dynamic algorithms for graph coloring. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA.10.1137/1.9781611975031.1 ↗
55. Fully-dynamic graph algorithms with sublinear time inspired by distributed computing10.1016/j.procs.2017.05.098 ↗
56. Huang, Z., Yuan, L., Sui, H., Chen, Z., Yang, S., and Yang, J. (2023, January 17–20). Edge Coloring on Dynamic Graphs. Proceedings of the DASFAA, Tianjin, China.10.1007/978-3-031-30675-4_10 ↗
57. Duan, R., He, H., and Zhang, T. (2019, January 6–9). Dynamic edge coloring with improved approximation. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, USA.10.1137/1.9781611975482.117 ↗
58. Christiansen, A.B.G. (2023, January 20–23). The power of multi-step vizing chains. Proceedings of the 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA.10.1145/3564246.3585105 ↗
59. Bhattacharya, S., Costa, M., Panski, N., and Solomon, S. (2024, January 7–10). Nibbling at long cycles: Dynamic (and static) edge coloring in optimal time. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria, VA, USA.10.1137/1.9781611977912.122 ↗
60. Bhattacharya, S., Costa, M., Panski, N., and Solomon, S. (2023). Arboricity-dependent algorithms for edge coloring. arXiv.
61. Christiansen, A.B. (2024). Deterministic Dynamic Edge-Colouring. arXiv.
62. Finding all maximal cliques in dynamic graphs10.1023/B:COAP.0000008651.28952.b6 ↗
63. Incremental maintenance of maximal cliques in a dynamic graph10.1007/s00778-019-00540-5 ↗
64. Incremental Maximal Clique Enumeration for Hybrid Edge Changes in Large Dynamic Graphs10.1109/TKDE.2023.3311398 ↗
65. Sun, S., Wang, Y., Liao, W., and Wang, W. (2017, January 19–22). Mining Maximal Cliques on Dynamic Graphs Efficiently by Local Strategies. Proceedings of the ICDE, San Diego, CA, USA.10.1109/ICDE.2017.53 ↗
66. Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph10.1109/TMSCS.2018.2802920 ↗
67. Wang, R., Liao, M., and Qin, C. (2019, January 20–22). An Efficient Algorithm for Enumerating Maximal Bicliques from a Dynamically Growing Graph. Proceedings of the ICNC-FSKD, Kunming, China.10.1007/978-3-030-32591-6_35 ↗
68. Distributed $k$ -Core View Materializationand Maintenance for Large Dynamic Graphs10.1109/TKDE.2013.2297918 ↗
69. Faster Parallel Core Maintenance Algorithms in Dynamic Graphs10.1109/TPDS.2019.2960226 ↗
70. Incremental k-core decomposition: Algorithms and evaluation10.1007/s00778-016-0423-8 ↗
71. Wang, N., Yu, D., Jin, H., Qian, C., Xie, X., and Hua, Q. (2017, January 5–8). Parallel Algorithm for Core Maintenance in Dynamic Graphs. Proceedings of the ICDCS, Atlanta, GA, USA.
72. Core Maintenance in Dynamic Graphs: A Parallel Approach Based on Matching10.1109/TPDS.2018.2835441 ↗
73. Aridhi, S., Brugnara, M., Montresor, A., and Velegrakis, Y. (2016, January 20–24). Distributed k-core decomposition and maintenance in large dynamic graphs. Proceedings of the DEBS, Irvine, CA, USA.10.1145/2933267.2933299 ↗
74. Efficient Core Maintenance in Large Dynamic Graphs10.1109/TKDE.2013.158 ↗
75. Parallel Core Maintenance of Dynamic Graphs10.1109/TKDE.2022.3219096 ↗
76. Guo, B., and Sekerinski, E. (2023, January 7–10). Parallel Order-Based Core Maintenance in Dynamic Graphs. Proceedings of the ICPP, Salt Lake City, UT, USA.10.1145/3605573.3605597 ↗
77. Batch Processing for Truss Maintenance in Large Dynamic Graphs10.1109/TCSS.2020.3026574 ↗
78. Exploring Truss Maintenance in Fully Dynamic Graphs: A Mixed Structure-Based Approach
79. Maximal D-truss Search in Dynamic Directed Graphs10.14778/3598581.3598592 ↗
80. Ebadian, S., and Huang, X. (2019, January 10–16). Fast Algorithm for K-Truss Discovery on Public-Private Graphs. Proceedings of the IJCAI, Macao, China.10.24963/ijcai.2019/313 ↗
81. Li, L., and Jiang, Y. (2023, January 17–21). Parallel Truss Maintenance of Dynamic Graphs. Proceedings of the ICPADS, Danzhou, China.
82. Huang, X., Cheng, H., Qin, L., Tian, W., and Yu, J.X. (2014, January 22–27). Querying k-truss community in large and dynamic graphs. Proceedings of the SIGMOD, Snowbird, UT, USA.10.1145/2588555.2610495 ↗
83. Sahu, S., Kothapalli, K., and Banerjee, D.S. (2024, January 27–31). Shared-Memory Parallel Algorithms for Community Detection in Dynamic Graphs. Proceedings of the IPDPS, San Francisco, CA, USA.10.1109/IPDPSW63119.2024.00063 ↗
84. Zakrzewska, A., and Bader, D.A. (2015, January 25–28). A dynamic algorithm for local community detection in graphs. Proceedings of the ASONAM, Paris, France.
85. Zakrzewska, A., and Bader, D.A. (2015, January 6–9). Fast incremental community detection on dynamic graphs. Proceedings of the PPAM, Krakow, Poland.10.1007/978-3-319-32149-3_20 ↗
86. Shang, J., Liu, L., Xie, F., Chen, Z., Miao, J., Fang, X., and Wu, C. (2014). A Real-Time Detecting Algorithm for Tracking Community Structure of Dynamic Networks. arXiv.
87. Nathan, E., Zakrzewska, A., Riedy, E.J., and Bader, D.A. (2017). Local Community Detection in Dynamic Graphs Using Personalized Centrality. Algorithms, 10.10.3390/a10030102 ↗
88. Duan, D., Li, Y., Jin, Y., and Lu, Z. (2009, January 6). Community mining on dynamic weighted directed graphs. Proceedings of the CIKM-CNIKM, Hong Kong, China.10.1145/1651274.1651278 ↗
89. Wang, C.D., Lai, J.H., and Yu, P.S. (2013, January 23–25). Dynamic community detection in weighted graph streams. Proceedings of the SDM, Suzhou, China.
90. Fully Dynamic Depth-First Search in Directed Graphs10.14778/3364324.3364329 ↗
91. Chen, L., Duan, R., Wang, R., Zhang, H., and Zhang, T. (2018, January 18–20). An Improved Algorithm for Incremental DFS Tree in Undirected Graphs. Proceedings of the SWAT, Malmö, Sweden.
92. Nakamura, K., and Sadakane, K. (2019). Space-Efficient Fully Dynamic DFS in Undirected Graphs. Algorithms, 12.10.3390/a12030052 ↗
93. Baswana, S., Gupta, S.K., and Tulsyan, A. (2018). Fault tolerant and fully dynamic DFS in undirected graphs: Simple yet efficient. arXiv.
94. Baswana, S., Chaudhury, S.R., Choudhary, K., and Khan, S. (2016, January 10–12). Dynamic DFS in undirected graphs: Breaking the O (m) barrier. Proceedings of the SODA, Arlington, VA, USA.10.1137/1.9781611974331.ch52 ↗
95. The Incremental Maintenance of a Depth-First-Search Tree in Directed Acyclic Graphs10.1016/S0020-0190(96)00202-5 ↗
96. Incremental algorithm for maintaining a DFS tree for undirected graphs10.1007/s00453-016-0204-1 ↗
97. Baswana, S., Goel, A., and Khan, S. (2018, January 7–10). Incremental DFS algorithms: A theoretical and experimental study. Proceedings of the SODA, New Orleans, LA, USA.10.1137/1.9781611975031.4 ↗
98. Baswana, S., and Choudhary, K. (2015, January 24–28). On dynamic DFS tree in directed graphs. Proceedings of the MFCS, Milan, Italy.10.1007/978-3-662-48054-0_9 ↗
99. Karczmarz, A., and Sankowski, P. (2023, January 10–14). Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs. Proceedings of the ICALP, Paderborn, Germany.
100. D’Angelo, G., D’Emidio, M., and Frigioni, D. (2019). Fully Dynamic 2-Hop Cover Labeling. ACM J. Exp. Algorithmics, 24.10.1145/3299901 ↗