The Reachability Query over Distributed Uncertain Graphs

Reachability, one of the most fundamental queries over uncertain graphs, which asks the probability that two given query vertices are reachable over an uncertain graph. Although this problem has been widely studied, the existing works are all processed in a single server. However, as graph data becomes larger, it usually cannot be stored in a single server. Moreover, processing probabilistic reachability queries is #P-complete, so the calculation is very expensive even on small graphs. Thus, in this paper, our purpose is to develop efficient distributed strategies to firstly pick out all the maximal subgraphs whose reachability probabilities can be calculated in polynomial time efficiently. After this step, only a small graph remains, and we provide an approximate method. Extensive experimental studies show that our distributed algorithms are efficient and have a low communication cost.