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?