0
$\begingroup$

We have an uncertain graph $G$ where each edge $(u,v)$ exists with a probability $p_{(u,v)} \in (0, 1]$. We want to assign a score in $[0, 1]$ to each pair of vertices $u$ and $v$ which represents the likelihood that they lie in the same connected component.

If the only possible scores were discrete $0$ and $1$, then this problem reduces to the connected components listing or graph reachability problem. Is there any work on uncertain graphs that can solve this problem?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Welcome to CS.SE! The problem is not well-defined. You haven't given us any basis for assigning an output score, or how the outputs should relate to the inputs; we could assign a score of 0.42 to every pair of vertices, and that would meet all of your requirements. $\endgroup$
    – D.W. ♦
    Mar 27, 2017 at 17:37
  • 1
    $\begingroup$ I suspect what you're going to need to do is to characterize the probabilistic process underlying this. Presumably, there is some random process that determines which vertices are in the same cluster; and some random process that describes how input scores (on edges) are generated, depending on the clustering. What are those processes? You'll need to figure that out and describe it in the question; with that information, one can start to consider algorithms. Until then, we can't answer your question without that kind of information. $\endgroup$
    – D.W. ♦
    Mar 27, 2017 at 17:38
  • $\begingroup$ @D.W.: It is indeed an open-ended problem. We are free to define reasonable metrics for similarity. I want to see what literature exists for DSUs on weighted graphs. $\endgroup$
    – pathikrit
    Mar 29, 2017 at 18:51
  • 1
    $\begingroup$ I think that you should change your question into either 1. formally define the probability of the vertices being in the same set in terms of the initial given vertex probabilities and ask for an efficient algorithm to compute this or 2. Ask for an useful formalization of the probability the vertices are in the same set given the initial vertex probabilities. Right now, it seems this question is asking both, which is simply not easily answerable in this format. Just question 1 is perfectly answerable in this format and although question 2 is a bit more vague, it should be doable. $\endgroup$
    – Discrete lizard ♦
    Mar 31, 2017 at 16:50
  • 1
    $\begingroup$ Also, "But, I am not sure what literature exists for probabilistic graphs" is not a question. It is better to be explicit in your question about whether you mainly want a reference to some literature (the tag 'reference-request' may help) or simply some possible 'original' ideas. $\endgroup$
    – Discrete lizard ♦
    Mar 31, 2017 at 16:51

1 Answer 1

Reset to default
5
+25
$\begingroup$

I edited your question to make it self-contained.

The literature on uncertain graphs is really rich for this problem. What you are looking for is "reachability in uncertain graphs", which has been studied extensively in database community [1].

Basically, you have an edge between two vertices $u$ and $v$ with probability $p_{uv} \in (0,1]$. You need to find whether two given vertices are reachable, therefore, lie in the same connected component or disjoint set. I suggest you take a look at the following paper as starting point, which describes the basics and can lead you to more works that have been done on this problem:

[1] Jin, Ruoming, et al. "Distance-constraint reachability computation in uncertain graphs." Proceedings of the VLDB Endowment 4.9 (2011): 551-562.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.