Back to Search
Start Over
Computing K-Cores in Large Uncertain Graphs: An Index-Based Optimal Approach.
- Source :
- IEEE Transactions on Knowledge & Data Engineering; Jul2022, Vol. 34 Issue 7, p3126-3138, 13p
- Publication Year :
- 2022
-
Abstract
- Uncertain graph management and analysis have attracted many research attentions. Among them, computing $k$ k -cores in uncertain graphs (aka, $(k,\eta)$ (k , η) -cores) is an important problem and has emerged in many applications such as community detection, protein-protein interaction network analysis and influence maximization. Given an uncertain graph, the $(k,\eta)$ (k , η) -cores can be derived by iteratively removing the vertex with an $\eta$ η -degree of less than $k$ k . However, the results heavily depend on the two input parameters $k$ k and $\eta$ η . The settings for these parameters are unique to the specific graph structure and the user's subjective requirements. In addition, computing and updating the $\eta$ η -degree for each vertex is the most costly component in the algorithm, and the cost is high. To overcome these drawbacks, we propose an index-based solution for computing $(k,\eta)$ (k , η) -cores. The size of the index is well bounded by $O(m)$ O (m) , where $m$ m is the number of edges in the graph. Based on the index, queries for any $k$ k and $\eta$ η can be answered in optimal time. We propose an algorithm for index construction with several different optimizations. We also propose a new algorithm for index construction in external memory. We conduct extensive experiments on eight real-world datasets to practically evaluate the performance of all proposed algorithms. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10414347
- Volume :
- 34
- Issue :
- 7
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Knowledge & Data Engineering
- Publication Type :
- Academic Journal
- Accession number :
- 157258597
- Full Text :
- https://doi.org/10.1109/TKDE.2020.3023925