Efficient $\eta$-Threshold Maintenance in Dynamic Uncertain Graphs
Yu Chen, Qing Liu, Yifan Zhu, Yunjun Gao · 2025
The$\eta$-threshold decomposition in uncertain graphs, which calculates the$\eta$-thresholds for each vertex, is a fundamental problem for graph analysis. While existing studies on$\eta$-threshold decomposition primarily focus on static uncertain graphs, numerous real-world scenarios involve highly dynamic uncertain graphs. It is costly to recompute all$\eta$-thresholds from scratch whenever the uncertain graphs face update operations, e.g., edge insertion and deletion, and the modifications on edge probability. Motivated by this, we introduce efficient$\eta$-threshold maintenance algorithms tailored for dynamic uncertain graphs in this paper. Firstly, we investigate the impact of edge insertion and deletion on$\eta$-thresholds. Building upon this analysis, we introduce the maintenance algorithms designed to adjust the$\eta$thresholds for edge insertions or deletions within the uncertain graphs. Our approaches involve identifying a compact subgraph encompassing all vertices necessitating$\eta$-threshold updates, followed by an iterative process of vertex deletion to complete the$\eta$-threshold updates. To improve the efficiency, we devise three optimizations to further reduce the number of candidate$\eta$-thresholds requiring adjustment. Moreover, we extend the proposed algorithms to handle the$\eta$-threshold maintenance for edge probability change. Extensive experiments on both real and synthetic datasets demonstrate the efficiency of the proposed algorithms. The results reveal that our proposed algorithms consistently outperform the baselines, exhibiting improvements ranging from at least three orders of magnitude to as high as seven orders of magnitude.