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.

Using trajectories of moving objects and performing contact event query during disease transmission is an effective method of prevention and control. Existing contact query processing algorithms only consider single-source (one-to-one) contact event and thus can not discover multi-source (n-to-one) contact events. In this paper, we propose efficient multi-source contact event query processing methods that are capable of querying multi-source contact events. The definition of multi-source contact events is first formulated. Then, a baseline multi-source contact event query processing algorithm is presented, which adopts the idea of sliding window-based sequential scanning. To improve the query efficiency, the 2-dimensional bitmap filter and the anchor time point scanning are designed and used in the optimized query processing algorithm. Comprehensive experiments on real-world data demonstrate that the proposed algorithms can find more potential contact events and have good performance in the manner of query time cost.

Using the trajectory data of moving objects to analyze and study the infection mode of viruses or germs has practical application value. The definition of infection pattern in existing works only considers one-to-one infection mode rather than many-to-one mode, and thus some infection events could be ignored. This paper presents multi-source infection pattern mining algorithms oriented to moving objects for the first time. The multi-source infection event (MSIE) is defined. On the basis of MSIE, the multi-source infection pattern mining algorithm (MIPM) is proposed, which uses sliding window mechanism. The sliding window is used to record the set of candidate infection source that may infect each normal object at each time point, and then the determined infection events are mined. To improve performance, an optimized mining algorithm (MIPM+) based on the R-tree index is proposed, which can reduce the number of objects to be detected at each time point. The experimental results show that our proposed multi-source infection pattern mining algorithms can mine more potential infection events.