Accelerating (k,l,η)-Core Query Processing in Directed Uncertain Graphs

Abstract

Uncertain graphs are commonly used to model the uncertain relationships between entities that arise from experimental or measurement errors. In recent years, the analysis of uncertain graphs has attracted significant research attention, with the computation of (k,η)-cores emerging as a fundamental problem. However, existing studies on (k,η)-cores often neglect edge directions, resulting in weak correlations among vertices in the resulting subgraph. To address this limitation, we propose a direction-aware (k,l,η)-core model. Specifically, a (k,l,η)-core is defined as a maximal connected subgraph in which every vertex has a probability of at least η of having in-degree ≥k and out-degree ≥l. We first present an online algorithm based on a peeling strategy to compute (k,l,η)-cores. To improve query performance, we develop two indexing mechanisms, DUCS-E and DUCS, that accelerate query processing. DUCS-E stores probability information for all possible (k,l,η)-cores, enabling it to completely avoid redundant computations during query processing, but at the cost of large storage space. To mitigate this issue, we propose the lightweight DUCS index, which stores directional probability information separately, reducing storage overhead while still pruning many irrelevant vertices; however, it requires additional verification. To balance efficiency and storage, we further design a hybrid index that combines the strengths of both approaches. Finally, experimental evaluations on real-world datasets demonstrate the effectiveness of the proposed (k,l,η)-core model as well as the efficiency and scalability of our methods.