## 3 Proposed Dynamic Graph Processing Scheme
### Scheduling Method  
Before transmitting the divided graph partitions to the GPU, it is essential to determine their loading order, a process referred to as scheduling. The Scheduling Manager efficiently organizes and coordinates operations for each partition of the subdivided graph. This  
Figure 2: Overall processing structure of the proposed scheme. involves prioritizing partitions and determining the optimal sequence for loading them onto the GPU. Additionally, the scheduler considers the dynamic nature of graphs to establish and manage schedules that adapt to graph changes in real time. Figure 3 illustrates the process of partitioning and scheduling snapshots of a dynamic graph. Over time intervals t1 to t4, snapshots G1, G2, G3, and G4 are generated. If a snapshot exceeds the GPU's global memory capacity, it is further divided into multiple partitions. These partitions are then enqueued in the Scheduler Queue based on their priority, ensuring efficient processing on the GPU. This paper proposes an optimized method for determining the loading order to enhance the efficiency of dynamic graph processing on GPUs. Partitions generated through graph partitioning are assigned priorities to ensure optimal scheduling. Updated partitions are prioritized for processing first, while partitions that appear in multiple snapshots are also loaded into the GPU's global memory earlier to minimize redundant computations. Additionally, this study considers not only active vertices but also potentially active vertices that may become active in subsequent processing. By incorporating these factors into priority assignment, the proposed method improves GPU resource utilization and enhances overall processing efficiency. Equation (2) represents \(N(Pi)\), which refers to the number of snapshots required to process Pi when an update occurs. Active(Pi) denotes the number of active vertices within the partition, and Potential(Pi) refers to the potential active vertices, i.e., the tentative active vertices within the partition. S represents the set of all snapshots in the dynamic graph, while Ssubt refers to the subset of snapshots that contain partition Pi. Since a partition may appear in multiple snapshots, the priority calculation considers the influence of each relevant snapshot. K varies depending on whether an update has occurred. If an update occurs in the partition, \(K\) is set to 1. If no update occurs, it is set to 0, and the priority is adjusted accordingly. \(\alpha\) and \(\beta\) are scaling factors set during preprocessing to emphasize the impact of certain values. This priority formula ensures that partitions are efficiently loaded into the GPU. \[Val(P_{i})=N(P_{i})+\alpha\frac{\sum_{S_{\mathit{sult}}\in S}Active(P_{i},\ \ S_{\mathit{sult}})}{|S|}+\beta\frac{\sum_{S_{\mathit{sult}}\in S} Potential(P_{i},\ \ S_{\mathit{sult}})}{|S|}+K \tag{2}\]  
We apply the following priority-driven scheduling function step-by-step. Figure 3: Dynamic graph scheduling. Determine the priority of each partition by computing the number of snapshots it appears in, the number of active vertices, and the number of potential active vertices. 2. Apply an update flag to increase priority when a partition has been updated. This ensures that recently modified partitions are processed earlier. 3. Compute the priority values for all partitions using the given formula, sort them in descending order, and process them on the GPU accordingly to maximize computational efficiency and minimize redundant operations. By following the scheduling strategy, the proposed method optimally allocates GPU resources, reduces unnecessary computations, and improves dynamic graph processing performance. Figure 4 illustrates an example of active and potentially active vertices during dynamic graph processing when an edge between two vertices V2 and V3 is deleted. Figure 4a shows a scenario where the edge between vertices V2 and V3 in partition P3 is deleted. Figure 4b depicts the activation process, where V2 and V3 become active vertices due to the edge deletion.