Shortest paths and centrality in uncertain networks

Computing the shortest path between a pair of nodes is a funda-
mental graph primitive, which has critical applications in vehicle
routing, finding functional pathways in biological networks, surviv-
able network design, among many others. In this work, we study
shortest-path queries over uncertain networks, i.e., graphs where
every edge is associated with a probability of existence. We show
that, for a given path, it is #P-hard to compute the probability of it
being the shortest path, and we also derive other interesting prop-
erties highlighting the complexity of computing the Most Probable
Shortest Paths (MPSPs). We thus devise sampling-based efficient
algorithms, with end-to-end accuracy guarantees, to compute the
MPSP. As a concrete application, we show how to compute a novel
concept of betweenness centrality in an uncertain graph using
MPSPs. Our thorough experimental results and rich real-world
case studies on sensor networks and brain networks validate the
effectiveness, efficiency, scalability, and usefulness of our solution