SCIENCE@home

Conditional Reliability in Uncertain Graphs

Arijit Khan,F. Bonchi,Francesco Gullo,A. Nufer

Published 2016 in IEEE Transactions on Knowledge and Data Engineering

ABSTRACT

Network reliability is a well-studied problem that requires to measure the probability that a target node is reachable from a source node in a probabilistic (or uncertain) graph, i.e., a graph where every edge is assigned a probability of existence. Many approaches and problem variants have been considered in the literature, with the majority of them assuming that edge-existence probabilities are fixed. Nevertheless, in real-world graphs, edge probabilities typically depend on external conditions. In metabolic networks, a protein can be converted into another protein with some probability depending on the presence of certain enzymes. In social influence networks, the probability that a tweet of some user will be re-tweeted by her followers depends on whether the tweet contains specific hashtags. In transportation networks, the probability that a network segment will work properly or not, might depend on external conditions such as weather or time of the day. In this paper, we overcome this limitation and focus on <italic>conditional reliability</italic>, that is, assessing reliability when edge-existence probabilities depend on a set of conditions. In particular, we study the problem of determining the top-<inline-formula> <tex-math notation="LaTeX">$k$</tex-math><alternatives><inline-graphic xlink:href="khan-ieq1-2816653.gif"/> </alternatives></inline-formula> conditions that maximize the reliability between two nodes. We deeply characterize our problem and show that, even employing polynomial-time reliability-estimation methods, it is <inline-formula> <tex-math notation="LaTeX">$\mathbf {NP}$</tex-math><alternatives><inline-graphic xlink:href="khan-ieq2-2816653.gif"/> </alternatives></inline-formula>-hard, does not admit any <inline-formula><tex-math notation="LaTeX">$\mathbf {PTAS}$ </tex-math><alternatives><inline-graphic xlink:href="khan-ieq3-2816653.gif"/></alternatives></inline-formula>, and the underlying objective function is non-submodular. We then devise a practical method that targets both accuracy and efficiency. We also study natural generalizations of the problem with multiple source and target nodes. An extensive empirical evaluation on several large, real-life graphs demonstrates effectiveness and scalability of our methods.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-38 of 38 references · Page 1 of 1

CITED BY

Showing 1-33 of 33 citing papers · Page 1 of 1