Accelerating (k,l,η)-Core Query Processing in Directed Uncertain Graphs
Open Access
- 7 August 2026
- journal article
- research article
- Published by MDPI AG in Electronics
- Vol. 15 (16) , 3508
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 -cores emerging as a fundamental problem. However, existing studies on -cores often neglect edge directions, resulting in weak correlations among vertices in the resulting subgraph. To address this limitation, we propose a direction-aware -core model. Specifically, a -core is defined as a maximal connected subgraph in which every vertex has a probability of at least of having in-degree and out-degree . We first present an online algorithm based on a peeling strategy to compute -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 -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 -core model as well as the efficiency and scalability of our methods.
Keywords
Funding Information
- National Natural Science Foundation of China (62372101)
This publication has 32 references indexed in Scilit:
- A Vertex Partitioning Algorithm for Large‐Scale Uncertain GraphsConcurrency and Computation: Practice and Experience, 2026
- Computing the center of uncertain points on cactus graphsTheoretical Computer Science, 2026
- The k-center problem of uncertain points on graphsInformation Processing Letters, 2026
- Topic-aware most influential community search in social networksNeurocomputing, 2025
- Truss community search in uncertain graphsKnowledge and Information Systems, 2024
- Butterfly counting and bitruss decomposition on uncertain bipartite graphsThe VLDB Journal, 2023
- Truss decomposition of uncertain graphsKnowledge and Information Systems, 2016
- ParK: An efficient algorithm for k-core decomposition on multicore processors2014
- D-cores: measuring collaboration of directed graphs based on degeneracyKnowledge and Information Systems, 2012
- Network structure and minimum degreeSocial Networks, 1983