Recent Advances in Efficient Dynamic Graph Processing
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 m...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-05-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/15/11/6003 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850129116019294208 |
|---|---|
| author | Zi Chen Keke Liang Long Yuan Wenjie Zhang Zhengyi Yang |
| author_facet | Zi Chen Keke Liang Long Yuan Wenjie Zhang Zhengyi Yang |
| author_sort | Zi Chen |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-e8ed5d5564b049ffaa676eeafd9a870c |
| institution | OA Journals |
| issn | 2076-3417 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-e8ed5d5564b049ffaa676eeafd9a870c2025-08-20T02:33:06ZengMDPI AGApplied Sciences2076-34172025-05-011511600310.3390/app15116003Recent Advances in Efficient Dynamic Graph ProcessingZi Chen0Keke Liang1Long Yuan2Wenjie Zhang3Zhengyi Yang4School of Computer Science and Artificial Intelligence, Wuhan University of Technology, Wuhan 430070, ChinaCollege of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, ChinaSchool of Computer Science and Artificial Intelligence, Wuhan University of Technology, Wuhan 430070, ChinaSchool of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, AustraliaSchool of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, AustraliaGraph 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.https://www.mdpi.com/2076-3417/15/11/6003graph analysisdynamic graph algorithmsfully graph updatesystem |
| spellingShingle | Zi Chen Keke Liang Long Yuan Wenjie Zhang Zhengyi Yang Recent Advances in Efficient Dynamic Graph Processing Applied Sciences graph analysis dynamic graph algorithms fully graph update system |
| title | Recent Advances in Efficient Dynamic Graph Processing |
| title_full | Recent Advances in Efficient Dynamic Graph Processing |
| title_fullStr | Recent Advances in Efficient Dynamic Graph Processing |
| title_full_unstemmed | Recent Advances in Efficient Dynamic Graph Processing |
| title_short | Recent Advances in Efficient Dynamic Graph Processing |
| title_sort | recent advances in efficient dynamic graph processing |
| topic | graph analysis dynamic graph algorithms fully graph update system |
| url | https://www.mdpi.com/2076-3417/15/11/6003 |
| work_keys_str_mv | AT zichen recentadvancesinefficientdynamicgraphprocessing AT kekeliang recentadvancesinefficientdynamicgraphprocessing AT longyuan recentadvancesinefficientdynamicgraphprocessing AT wenjiezhang recentadvancesinefficientdynamicgraphprocessing AT zhengyiyang recentadvancesinefficientdynamicgraphprocessing |