Computing K-Cores in Large Uncertain Graphs: An Index-Based Optimal Approach

Uncertain graph management and analysis have attracted many research attentions. Among them, computing k-cores in uncertain graphs (aka, (k, eta-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)-cores can be derived by iteratively removing the vertex with an eta-degree of less than k. However, the results heavily depend on the two input parameters 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)-cores. The size of the index is well bounded by O(m), where m is the number of edges in the graph. Based on the index, queries for any 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.