Reliability Maximization in Uncertain Graphs
Reliability Maximization in Uncertain Graphs A summary of the IEEE TKDE 2020 research paper by Xiangyu Ke, Arijit Khan, Mohammad Al Hasan, and Rojin Rezvansangsari [Background] Rich expressiveness of probabilistic graphs and their utility to model the inherent uncertainty in a wide range of applications have prompted a large number of research works on probabilistic graphs by the data management research communities [1]. In an uncertain graph setting, Network Reliability is a well-studied problem [2], [3], which requires to measure the probability that a target node is reachable from a source node. Reliability has been widely studied in device networks, i.e., networks whose nodes are electronic devices and the (physical) links between such devices have a probability of failure [4]. More recently, the attention has been shifted to social, communication, transportation, genomic, and logistic networks [5]–[7]. Figure 1: Reliability in a sensor network