Index-based optimal algorithm for computing k-cores in large uncertain graphs
- Publication Type:
- Conference Proceeding
- Citation:
- Proceedings - International Conference on Data Engineering, 2019, 2019-April pp. 64 - 75
- Issue Date:
- 2019-04-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Index-based Optimal Algorithm for Computing K-Cores in Large Uncertain Graphs.pdf | Published version | 338.96 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 2019 IEEE. Uncertainty in graph data occurs for a variety of reasons, such as noise and measurement errors. Recently, 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, for example, community detection, protein-protein interaction network analysis and influence maximization. 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 the most costly component of the algorithm, and that cost is high. 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 for any k and η can be answered in optimal time. Further, the method is accompanied by several different optimizations to speed up construction of the index. We conduct extensive experiments on eight real-world datasets to practically evaluate the performance of all the proposed algorithms. The results demonstrate that this index-based approach is several orders of magnitude faster at processing queries than the traditional online approaches.?
Please use this identifier to cite or link to this item: