Fast One-to-Many Reliability Estimation for Uncertain Graphs

Uncertain graphs commonly represent noisy and unreliable real-world datasets in various applications. One fundamental primitive on uncertain graphs is reliability, which evaluates the connection robustness between two specific nodes. Although reliability is helpful to analyzeuncertain graphs, it is computationally expensive because (1) the reliability estimation is #P-hard problem and (2) many applications require reliability computations among all possible pairs of nodes. To overcome the aforementioned problems, we present a novel algorithm called Sharing RCSS+, which efficiently computes the reliability among all possible pairs of nodes. Our extensive experiments on both real-world and synthetic uncertain graphs clarified that Sharing RCSS+ achieves a more efficient estimation than the state-of-the-art methods.