Shortest paths and centrality in uncertain networks

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