Distributed Core Decomposition in Probabilistic Graphs

This paper initializes distributed algorithm studies for core decomposition in probabilistic graphs. Core decomposition has been proven to be a useful primitive for a wide range of graph analyses, but it has rarely been studied in probabilistic graphs, especially in a distributed environment. In this work, under a distributed model underlying Pregel and live distributed systems, we present the first known distributed solutions for core decomposition in probabilistic graphs, where there is an existence probability for each edge. In the scenario that the existence probability of edges are known to nodes, the proposed algorithm can get the exact coreness of nodes with a high probability guarantee. The proposed algorithm can also be used to efficiently update the coreness of nodes in dynamic graphs, where a set of edges are inserted/deleted into/from the graph. In the harsher case that the existence probability is unknown, we present a novel method to estimate the existence probability of edges, based on which the coreness of nodes with small approximation ratio guarantee can be computed. Extensive experiments are conducted on different types of real-world graphs and synthetic graphs. The results illustrate that the proposed algorithms exhibit good efficiency, stability and scalability.