5
$\begingroup$

Lets say I have node A that connects to 10 other nodes. 6 of those nodes have Property 1 and the other 4 have Property 2. How can I easily determining the probability of landing on a node with property 1 randomly while traversing the graph?

Abstract Example

To clarify this problem, I'm trying to choose the most probable path.

I have a node $v$ with 10 edges going out, and 6 of the nodes on the other end have a certain property $A$, while 4 have a certain property $B$. Now, each of the 10 nodes also has 10 edges going out, and at the end there are 10 nodes, some with property $A$, some with property $B$. The key here is that each property denotes an occurrence of something. Using multiple nodes here is basically a replacement for weighted edges. Rather than having an edge with weight 6 leading to $A$, I have 6 occurrences of $A$. I know this sounds counterintuitive, but this is actually a smaller part of a much, much large problem.

I want to find the most likely sequence of something occurring. We can see that there is a 0.6 probability of $A$ occurring. How can I easily determine that?

Basicslly, the question comes down to how can I traverse a graph of probabilities made from a graph of occurrences without having to completely generate a new graph. The brute force method to this would be to start at $v$, count the number of occurrences of $A$ and the number of occurrences of $B$, determine the probability of each, and then on a new graph have an edge from $v$ to $A$ with a weight 0.6. Adter that, you would then go to each occurrence of A, make a list of the difference occurrences branching from that, find the probability of each (with the many occurrences of $A$ acting as one node), then on the new graph, add an edge to each occurrence.

This may seem like a lot of work, but with the algorithm that I am designing, each node may have a dozen properties. I want to be able to quickly traverse the graph taking the most likely path through certain properties, which could be different for each property of every combination of properties.

Applied Example

The basic graph.

Now, let's say that each node on this graph represents an event. Each event can have 9 different properties, and each event is dependent on the last one. For the sake of argument, let's that that the property being considered here is property 4. That doesn't really matter, I'm only noting it to point out that different properties lead to different simplified graphs (more below).

On Level 0 of the first graph (the black graph), we have event 1 takes occurs. Causing event 1 to occur causes a set of 13 other events to occur on Level 1, $\{A,A,A,A,A,A,B,B,B,B,C,C,D\}$. We can see that out of all of the events, $A$ is the most common result for property 4.

Now that we know what property to look for, we can look at the events on Level 2. The first occurrence of $A$ causes a set of events where property 4 is $\{E,G,G\}$, the second occurrence of $A$ causes a set of events where property 4 is $\{E,F,G\}$, and so on. Now, we have all these separate nodes, but we can pretend that they are actually one big node since we are only looking at one property.

Because of this, the set of property 4 of events that occur on Level 2 is $\{E,G,G,E,F,G,G,H,I,G,G,G,G,E,F,G\}$. The highest probability of the next event is that of $G$ where the probability is $9/16$.

This yields us the simplified graph shown below:

This shows us the most likely value of property 4 after we initiate event 1 and allow it to go two steps. If event 1 occurs, the most likely value for property 4 will be $A$. After another event in the chain reaction occurs, the most likely value of property 4 will be $G$.

And before you ask, no, a longest-path algorithm is not appropriate for this application. It would take another 3 pages to explain why that is, but basically, it doesn't matter if $D$ has the lowest probability but the events after it all have very high probabilities, we need to look at each edge independently.

Methods that Won't Work

One possible method I could use would be to render a graph for each separate property, but that would just be too much. I could generate the graph for property 4 and yield the graph in the second image, but if I added one more occurrence anywhere in the original graph, I would have to regenerate the graph for every single property, which is too much work when you are dealing with tens or hundreds of thousands of nodes.

So, the question remains: is there a tried and true algorithm for calculating probabilities for the next level as I move along the graph, or will I have to develop something on my own?

$\endgroup$
28
  • 2
    $\begingroup$ I think he means "Property A" and "Property B" when he speaks of characteristics, and that "Property B" is (without loss of generality) the logical negation of "Property A". @Nick Anderegg: if this is correct, I would strongly suggest you adopy this wording instead, as others are quite likely to think that 'characteristic' is meant to refer to some previously-defined property (something like the [characteristic of a ring](en.wikipedia.org/wiki/Characteristic_(algebra) or the characteristic of a topological space). $\endgroup$ Jul 23, 2012 at 13:46
  • 1
    $\begingroup$ @NickAnderegg I find your question pretty confusing. I think you should concentrate on making it clearer. For example, is your graph directed or k-regular? Try to be as precise and as exact as possible. Just take a few breaths, and perhaps even draw a picture if it makes explaining easier :-) $\endgroup$
    – Juho
    Jul 23, 2012 at 15:42
  • 2
    $\begingroup$ No, I think it will be just fine here. After people really understand what the problem is about, I don't think it will turn out to be too difficult. In either case, you should wait a good while before crossposting to TCS, and even then, do it only if you haven't received a satisfactory answer here. $\endgroup$
    – Juho
    Jul 23, 2012 at 15:51
  • 1
    $\begingroup$ @NickAnderegg, by graph of occurrences, I'm assuming you mean you have a graph where edges are labeled with counts, is this correct? If so it should be trivial to convert these counts into probabilities. As for the traversal, it sounds like you're searching for a dynamic programming approach, but I'm just guessing as it isn't very clear. Perhaps you should describe the actual problem, rather than some poorly generalized version of it using non-standard terminology. $\endgroup$
    – alto
    Jul 23, 2012 at 16:09
  • 1
    $\begingroup$ @NickAnderegg, I think my (and possibly others) confusion might be due to your use of the word property. It seems you might be better off saying $A \subseteq V$, i.e. $A$ is the set of all vertices with some property. Also, "I want to find the most likely sequence of something occurring" doesn't clear much up. Do you mean you want to find the probability that a random walk on your graph encounters a vertex with with property $A$. Again, I think it might help if you described your actual problem. $\endgroup$
    – alto
    Jul 23, 2012 at 16:40

1 Answer 1

5
$\begingroup$

Let me first rephrase your problem as I understand it. You have a tree of random events. Every event consists of choosing one of a set of child events; every child has the same probability but may have different child events of their own. The children are grouped by some classifier. You want to have efficient access to the group reached by the most likely path of groups, not individual children.

I suggest you stick to your idea of the compressed tree of groups but keep it around and maintain it. In a sense, you use it as overlay over the actual graph:

enter image description here [source]

The dotted lines represent the original tree, the solid green ones the overlay tree, weighted by the number of original child nodes of the respective group. Note that you can have access to both if you keep references to both roots. You find the desired group ("property" in your notation) by greedily following the edge with maximum weight among all outgoing edges, starting in $I$.

Maintaining this overlay tree is easy: upon adding a node on some level, add it to the appropriate group, adjust the weights and proceed recursively. In pseudo code, this is what the overlay tree might look like:

class Node {
  val label : String
  val children : List[Node]
}

class OverlayNode {
  val label : String
  val internal : List[Node]
  val children : Map[String,OverlayNode]

  def weight = children.size

  def insert(n : Node) {
    assert n.label == this.label
    internal ++ n
    foreach ( c in n.children ) {
      if ( children hasKey c.label )
        children(c.label).insert(c)
      else
        children ++ (new OverlayNode(c.label, c))
    }
  }

  def find_max {
    if ( children.size == 0 )
      return this
    else
      return (children argmax {c => c.weight}).find_max
  }
}

Note that the whole thing does not yield correct probabilities, anyway; you count nodes on every level, assuming they occur with the same probability, but that is not correct as siblings can have different amount of children. In the example, the probability to get $C$ if you had $A$ in the first round is not $0.5$ as your method determines -- two $C$ are child of them same $A$ and thus compete over the same slot! The precise formula is

$\qquad \displaystyle \begin{align} \operatorname{Pr}(C \mid A) &= \frac{\sum_{u \text{ type } A} \sum_{v \text{ of type }C \text{ under } u} \operatorname{Pr}(u)\operatorname{Pr}(v \mid u)}{\operatorname{Pr}(A)} \\ &= \frac{\frac{1}{5}\cdot\frac{1}{3} + \frac{1}{5}\cdot\frac{1}{3} + \frac{1}{5}\cdot\frac{1}{2}}{\frac{3}{5}} \\ &= \frac{7}{18} \end{align}$

This is more complicated to compute than raw counting, but you can still use the idea of the overlay tree. Maintenance will be more expensive but that is something you can not get around without further assumptions on the trees. Note that using the precise formula enables you to switch to non-uniform child distributions without too much hassle.

$\endgroup$
1
  • $\begingroup$ This is pretty much a solution to my problem. I am aware that it doesn't yield correct probabilities, and it's not supposed to. It would be a three page paper to explain why, so I'll just hope you take my work for it. It doesn't make sense in my general application, but it does in the real application. However, I figured out an even better way to solve my problem... a week ago... I even wrote it down. If I move properties to the edges and have the edges point to the same object, that solves the problem. I just drew the diagram incorrectly in my notes. This is still a valid solution, however. $\endgroup$ Jul 24, 2012 at 19:17

Your Answer

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

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