EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Xian Tang, Guo Chen, Junfeng Zhou

Electronics · 07.08.2026 · 15 (16) · 3508

DOI: 10.3390/electronics15163508 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Electronics, online erschienen am 07.08.2026. Verfasst von Xian Tang und 2 weiteren Autor:innen. Die Arbeit nennt 39 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Tang, X., Chen, G., & Zhou, J. (2026). Accelerating (k,l,η)-Core Query Processing in Directed Uncertain Graphs. Electronics, 15(16), 3508. https://doi.org/10.3390/electronics15163508

Vancouver

Tang X, Chen G, Zhou J. Accelerating (k,l,η)-Core Query Processing in Directed Uncertain Graphs. Electronics. 2026;15(16):3508. doi:10.3390/electronics15163508

BibTeX
@article{Tang2026,
  author = {Tang, Xian and Chen, Guo and Zhou, Junfeng},
  title = {Accelerating (k,l,η)-Core Query Processing in Directed Uncertain Graphs},
  journal = {Electronics},
  year = {2026},
  volume = {15},
  number = {16},
  pages = {3508},
  doi = {10.3390/electronics15163508}
}
Kostenlos starten →