The following paper has been accepted at EDBT 2014, to be held March 24-28, 2014 in Athens, Greece.
Title: Fast Reliability Search in Uncertain Graphs
Authors: Arijit Khan (ETH), Francesco Bonchi (Yahoo!), Aristides Gionis (Aalto University), and Francesco Gullo (Yahoo!)
Abstract: Given an uncertain graph with probabilities on edges, we propose efficient indexing methods to find all nodes reachable from a query node with probability no less than an input probability threshold. Such reachability queries can be useful in influence maximization in social networks, predicting co-complex memberships in protein-interaction networks, and computing packet delivery probability between a pair of nodes in mobile ad-hoc networks.