Efficient probabilistic k-core computation on uncertain graphs

Publication Type:
Conference Proceeding
Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, 2018, pp. 1204 - 1207
Issue Date:
Full metadata record
© 2018 IEEE. As uncertainty is inherent in a wide spectrum of graph applications such as social network and brain network, it is highly demanded to re-visit classical graph problems in the context of uncertain graphs. Driven by real-Applications, in this paper, we study the problem of k-core computation on uncertain graphs and propose a new model, namely (k,θ )-core, which consists of nodes with probability at least θ to be kcore member in the uncertain graph. We show the computation of (k,θ )-core is NP-hard, and hence resort to sampling based methods. Effective and efficient pruning techniques are proposed to significantly reduce the candidate size. To further reduce the cost of k-core computation on multiple sampled graphs, we design a k-core membership check algorithm following a novel expansion-based search paradigm. Extensive experiments on reallife graphs demonstrate the effectiveness and efficiency of our proposed techniques.
Please use this identifier to cite or link to this item: