Computing K-Cores in Large Uncertain Graphs: An Index-based Optimal Approach
| Autor: | Lu Qin, Bohua Yang, Rong-Hua Li, Lijun Chang, Ying Zhang, Dong Wen |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Vertex (graph theory)
Structure (mathematical logic) Theoretical computer science Index (economics) Degree (graph theory) Computer science Time optimal Graph Computer Science Applications Computational Theory and Mathematics Bounded function 08 Information and Computing Sciences Auxiliary memory Information Systems |
| Zdroj: | IEEE Transactions on Knowledge and Data Engineering. :1-1 |
| ISSN: | 2326-3865 1041-4347 |
| DOI: | 10.1109/tkde.2020.3023925 |
| Popis: | Uncertain graph management and analysis have attracted many research attentions. Among them, computing k-cores in uncertain graphs (aka, (k,)-cores) is an important problem and has emerged in many applications. Given an uncertain graph, the (k,)-cores can be derived by iteratively removing the vertex with an -degree of less than k and updating the -degrees of its neighbors. However, the results heavily depend on the two input parameters k and, and the settings for these parameters are unique to the specific graph structure and the user's subjective requirements. Additionally, computing and updating the -degree for each vertex is costly. To overcome these drawbacks, we have developed an index-based solution for computing (k,)-cores in this paper. The size of the index is well bounded by O(m), where m is the number of edges in the graph. Based on this index, queries 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, when the uncertain graph cannot be entirely loaded in memory. We conduct extensive experiments on eight real-world datasets to practically evaluate the performance of all the proposed algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|