# Recent Advances in Efficient Dynamic Graph Processing
## 1 Introduction  
A graph is a mathematical structure consisting of vertices and edges connecting certain pairs of them. Graphs have been widely used to represent the relationships of entities in real-world applications such as: social networks, in which a vertex represents a person and an edge between two vertices means two persons know each other [1]; World Wide Web, in which a vertex represents a web page and an edge stands for the hyperlink between two web pages [2]; collaborations networks, in which a vertex represents an author and an edge indicates the co-author relationship between two authors [3]; and protein-protein interaction of biology, in which a vertex indicates a protein and an edge means physical contacts of high specificity established between proteins [4]. With the proliferation of graph applications, research efforts have been devoted to many fundamental problems in managing and analyzing graph data [5]. Traditionally, researchers mainly focus on static graphs where vertices and edges are fixed and do not change over time [6, 7, 8, 9, 10]. However, real-world graphs change their topology over time. In a typical dynamic graph problem, one would like to answer queries on graphs that are undergoing a sequence of updates. The goal of a dynamic graph algorithm is to efficiently update the solution of the problem after dynamic changes, rather than having to recompute it from scratch each time. In the last decades, there has been a growing interest in such dynamically changing graphs [11, 12, 13]. It is not surprising thatdynamic algorithms and dynamic data structures are often more difficult to design and analyze [14; 15; 16]. **Applications. **: Specifically, dynamic graph processing has many real applications including:  
* _Social network analysis._ In a social network, users are connected by social relationships, such as friendships, professional collaborations, or online interactions. We can identify influential users through betweenness/closeness centrality [17; 18], which is crucial for targeted advertising and information diffusion. Besides, in platforms such as Facebook, Twitter, and Instagram, there are applications for community detection, aiming to find cohesive and tightly connected user groups [19; 20; 21]. The shortest path can also be used to measure the close relationship between users [22; 23]. Moreover, dynamic graph partitioning is an effective technique in social networks for balancing server workloads [24]. * _Biology science._ A biological network is a graph-based representation of interactions between biological entities, such as genes, proteins, cells, or organisms. In biological network analysis, centrality can pinpoint essential proteins/genes in Protein-Protein Interaction (PPI) networks [17; 25; 26; 27]. Moreover, cohesive subgraphs also play an important role in biological networks such as \(k\)-core/truss/clique. For example, they can be used to identify groups of genes with similar expression patterns, which may indicate shared functions between genes [28]. * _Transportation network._ A transportation network is a system of interconnected routes (roads, railways, airways, etc.) and nodes (intersections, stations, airports) that enable the movement of people and goods. In transportation networks, centrality can be used to identify critical transport hubs for infrastructure planning [26]. Besides, dynamic shortest path algorithms enable real-time navigation updates [29]. * _Financial data analysis._ A financial graph is a network representation of financial relationships, transactions, and dependencies between entities such as banks, companies, individuals, and assets. Dynamic centrality can identify suspicious transaction patterns [30]. Evolving community detection can reveal money laundering networks [31; 32]. Moreover, time-dependent financial graphs have risk. For risk assessment, dynamic cohesive subgraph or community can detect tightly coupled risky assets.For market analysis, dynamic graph clustering can be used to track evolving stock correlations [33].