Effective Index Construction Algorithm for Optimal $(k,η)$-cores Computation
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916712693104640 |
|---|---|
| author | Sun, Shengli Xu, Peng Jiang, Guanming Yu, Philip S. Li, Yi |
| author_facet | Sun, Shengli Xu, Peng Jiang, Guanming Yu, Philip S. Li, Yi |
| contents | Computing $(k,η)$-cores from uncertain graphs is a fundamental problem in uncertain graph analysis. UCF-Index is the state-of-the-art resolution to support $(k,η)$-core queries, allowing the $(k,η)$-core for any combination of $k$ and $η$ to be computed in an optimal time. However, this index constructed by current algorithm is usually incorrect. During decomposition, the key is to obtain the $k$-probabilities of its neighbors when the vertex with minimum $k$-probability is deleted. Current method uses recursive floating-point division to update it, which can lead to serious errors. We propose a correct and efficient index construction algorithm to address this issue. Firstly, we propose tight bounds on the $k$-probabilities of the vertices that need to be updated, and the accurate $k$-probabilities are recalculated in an on-demand manner. Secondly, vertices partitioning and progressive refinement strategy is devised to search the vertex with the minimum $k$-probability, thereby reducing initialization overhead for each $k$ and avoiding unnecessary recalculations. Finally, extensive experiments demonstrate the efficiency and scalability of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_20795 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Effective Index Construction Algorithm for Optimal $(k,η)$-cores Computation Sun, Shengli Xu, Peng Jiang, Guanming Yu, Philip S. Li, Yi Data Structures and Algorithms Computing $(k,η)$-cores from uncertain graphs is a fundamental problem in uncertain graph analysis. UCF-Index is the state-of-the-art resolution to support $(k,η)$-core queries, allowing the $(k,η)$-core for any combination of $k$ and $η$ to be computed in an optimal time. However, this index constructed by current algorithm is usually incorrect. During decomposition, the key is to obtain the $k$-probabilities of its neighbors when the vertex with minimum $k$-probability is deleted. Current method uses recursive floating-point division to update it, which can lead to serious errors. We propose a correct and efficient index construction algorithm to address this issue. Firstly, we propose tight bounds on the $k$-probabilities of the vertices that need to be updated, and the accurate $k$-probabilities are recalculated in an on-demand manner. Secondly, vertices partitioning and progressive refinement strategy is devised to search the vertex with the minimum $k$-probability, thereby reducing initialization overhead for each $k$ and avoiding unnecessary recalculations. Finally, extensive experiments demonstrate the efficiency and scalability of our approach. |
| title | Effective Index Construction Algorithm for Optimal $(k,η)$-cores Computation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.20795 |