Determining Probability from a Graph

Question

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

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?

Answer 1

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:

^[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.