Conditional reliability in uncertain graphs
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 con...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2019
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/103688 http://hdl.handle.net/10220/48596 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-103688 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1036882020-03-07T11:50:49Z Conditional reliability in uncertain graphs Khan, Arijit Bonchi, Francesco Gullo, Francesco Nufer, Andreas School of Computer Science and Engineering Reliability DRNTU::Engineering::Computer science and engineering Uncertain Graphs 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 conditional reliability , that is, assessing reliability when edge-existence probabilities depend on a set of conditions. In particular, we study the problem of determining the top- k 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 NP -hard, does not admit any PTAS , 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. MOE (Min. of Education, S’pore) Accepted version 2019-06-07T03:32:05Z 2019-12-06T21:17:58Z 2019-06-07T03:32:05Z 2019-12-06T21:17:58Z 2018 Journal Article Khan, A., Bonchi, F., Gullo, F., & Nufer, A. Conditional reliability in uncertain graphs. IEEE Transactions on Knowledge and Data Engineering, 30(11), 2078-2092. doi:10.1109/TKDE.2018.2816653 1041-4347 https://hdl.handle.net/10356/103688 http://hdl.handle.net/10220/48596 10.1109/TKDE.2018.2816653 en IEEE Transactions on Knowledge and Data Engineering © 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/10.1109/TKDE.2018.2816653 14 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
country |
Singapore |
collection |
DR-NTU |
language |
English |
topic |
Reliability DRNTU::Engineering::Computer science and engineering Uncertain Graphs |
spellingShingle |
Reliability DRNTU::Engineering::Computer science and engineering Uncertain Graphs Khan, Arijit Bonchi, Francesco Gullo, Francesco Nufer, Andreas Conditional reliability in uncertain graphs |
description |
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 conditional reliability , that is, assessing reliability when edge-existence probabilities depend on a set of conditions. In particular, we study the problem of determining the top- k 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 NP -hard, does not admit any PTAS , 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. |
author2 |
School of Computer Science and Engineering |
author_facet |
School of Computer Science and Engineering Khan, Arijit Bonchi, Francesco Gullo, Francesco Nufer, Andreas |
format |
Article |
author |
Khan, Arijit Bonchi, Francesco Gullo, Francesco Nufer, Andreas |
author_sort |
Khan, Arijit |
title |
Conditional reliability in uncertain graphs |
title_short |
Conditional reliability in uncertain graphs |
title_full |
Conditional reliability in uncertain graphs |
title_fullStr |
Conditional reliability in uncertain graphs |
title_full_unstemmed |
Conditional reliability in uncertain graphs |
title_sort |
conditional reliability in uncertain graphs |
publishDate |
2019 |
url |
https://hdl.handle.net/10356/103688 http://hdl.handle.net/10220/48596 |
_version_ |
1681037093591056384 |