Uncertain Graphs [DRAFT]

(Parchas 2015): Write something about it.

Propabilistic graphs may be:

edge existential

where each edge is augmented with a probability value, which indicates the chance that the edge exists.

weight distribution

where each edge is associated with a probability distribution of weight values.

Evaluation of ST-queries is hard (#P-hard). You have to create all possible (non-probabilistic) words that correspond to the probabilistic graph and evaluate the query in each one.

To improve the efficiency sampling is employed, where possible worlds with high existential probabilities are extracted.

  • Can we take advantage of Ehab’s work to compute the samples?