Directional Probability Graph - Loop Reduction Algorithm?

Question

Consider a directed graph that goes from the first node 1 to some end nodes (which no longer have outgoing edges). Each edge in the graph has a probability associated with it. Summing up the probabilities for each possible path to all possible end nodes, return 1 . (This means that we are guaranteed to reach one of the end nodes in the end.)

The problem would be simple if cycles did not exist on the chart. Unfortunately, rather confusing loops can occur on the graph, which can go through infinitely many times (the probability, of course, is multiplicative with each loop round).

Is there a general algorithm for finding probabilities for each end node?

A particularly unpleasant example:

We can represent the edges in the form of a matrix (the probability of transition from the row (node) x to the row (node) y is in the record (x,y) )

 {{0, 1/2, 0, 1/14, 1/14, 0, 5/14}, {0, 0, 1/9, 1/2, 0, 7/18, 0}, {1/8, 7/16, 0, 3/16, 1/8, 0, 1/8}, {0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}} 

Or as a directed graph:

Start node 1 blue, end nodes 5,6,7 are green. All edges are labeled with the probability of their intersection, starting with the node where they occur.

It has eight different paths from running node 1 to end nodes:

 {{1/14, {1, 5}}, {5/14, {1, 7}}, {7/36, {1, 2, 6}}, {1/144, {1, 2, 3, 5}}, {1/144, {1, 2, 3, 7}}, {1/36, {1, 4, 2, 6}}, {1/1008, {1, 4, 2, 3, 5}}, {1/1008, {1, 4, 2, 3, 7}}} 

(The designation for each path is {probability, sequence of visited nodes})

And there are five different cycles:

 {{1/144, {2, 3, 1}}, {7/144, {3, 2}}, {1/2, {4, 2}}, {1/48, {3, 4, 2}}, {1/1008, {4, 2, 3, 1}}} 

(The designation for cycles is {the probability of a cycle once, the sequence of nodes visited}).

If only these loops could be resolved to produce an efficient tree, similar to a graph, the problem would be solved.

Any hint on how to handle this?

I am familiar with Java, C ++ and C, so suggestions in these languages ​​are preferable.

Answer 1

I am not an expert in the field of Markov chains, and although I think that probably the algorithms are known for the problem that you represent, it is difficult for me to find them.

If there is no help from this direction, you can consider turning your own. Here I see at least two different approaches:

• Simulation

Learn how the state of a system evolves over time, starting with a system in state 1 with 100% probability and performing many iterations in which you use the transition probabilities to calculate the state probabilities obtained after taking the step. If at least one final (“absorbing”) node can be reached (with nonzero probability) from each node, then at sufficiently high steps the probability that the system is in anything other than the final state will asymptotically decrease to zero. You can estimate the probability that the system will end in the final state S, as the probability that it is in state S after n steps, with the upper limit of error in this estimate given by the probability that the system is in an incomplete state after n steps.

In practical terms, this is the same as calculating Tr ⁿ where Tr is your transition probability matrix of edges with a probability of 100% for all final states.

2. Accurate calculation.

Consider a graph G as you describe. For two vertices i and f such that there is at least one path from i to f, and f does not have outgoing edges other than its own edges, we can divide the paths from i to f into classes characterized by the number of times they go to i until reaching f. There can be an infinite number of such classes, which I will denote C _if (n), where n represents the number of times the paths in C _if (n) revisit node i. In particular, C _ii (0) contains all the simple loops in G containing I ( clarification : like other ways).

The overall probability of ending on node f, provided that the system crosses the graph G starting with node i, is determined

Pr (f | i, G) = Pr ( C _if (0) | G) + Pr ( C _if (1) | G) + Pr ( C _if (2) | G) ...

Now note that if n> 0, then every path in C _if (n) has the form of a union of two paths c and t , where c belongs to C _ii (n-1) and t belongs to C _if (0). That is, c is the path starting with node i and ending with node i, passing through i n-1 times between them, and t is the path from i to f, which does not go through i again. We can use this to rewrite our probability formula:

Pr (f | i, G) = Pr ( C _if (0) | G) + Pr ( C _ii (0) | G) * Pr ( C _if (0) | G) + Pr ( C _ii (1 ) | G) * Pr ( C _{, if} (0) | G) + ...

But note that each path in C _ii (n) is a composition of n + 1 paths belonging to C _{iisub> (0). It follows that Pr ( C ii (n) | G) = Pr ( C ii (0) | G) ^{n + 1} therefore we obtain}

Pr (f | i) = Pr ( C _{, if} (0) | G) + Pr ( C _{ii <(0) | G) + Pr ( C ii / sub> (0) | G) ² * Pr ( C , if (0) | G) + ...}

And now a little algebra gives us

Pr (f | i, G) - Pr ( C _{, if} (0) | G) = Pr ( C _ii (0) | G) * Pr (f | i, G)

which we can solve for Pr (f | i, G) to get

Pr (f | i, G) = Pr ( C _{, if} (0) | G) / (1 - Pr ( C <sub> IIsub> (0) | G))

Thus, we reduced the problem to one in terms of paths that do not return to the original node, with the possible exception of their end node. This does not exclude paths that have loops that do not include the starting node, but we can, however, rewrite this problem in terms of several instances of the original task, calculated on the subgraph of the original graph.

In particular, let S (i, G) be the set of successors of the vertex i in the graph G, i.e. the set of vertices s such that there is an edge from i to s in G and X (G, i) is a subgraph of G formed by removing all edges starting with i. In addition, let p _{be the} probability associated with the edge (i, s) in G.

Pr ( C _{, if} (0) | G) = the sum over s in S (i, G) p _is * Pr (f | s, X (G, i))

In other words, the probability of reaching f from i to G, without reconsidering i between them, is the sum over all successors i of the product of the probability of reaching s from i in one step with the probability of reaching f from s through G, without crossing any edges coming out of i . This applies to all f in G, including i.

Now note that S (i, G) and all p _are , and that the computation problem Pr (f | s, X (G, i)) is a new, strictly smaller instance of the original problem. Thus, this calculation can be performed recursively, and such recursion will be completed. However, it can take a long time if your schedule is complicated, and it seems that the naive implementation of this recursive approach will scale exponentially in the number of nodes. There are ways to speed up the computation in exchange for higher memory usage (i.e. Memoization).

---

There are probably other possibilities. For example, I suspect that there may be a bottom-up approach to dynamic programming, but I have not been able to convince myself that the cycles in the graph do not present an insurmountable problem.

Answer 2

Clarification of the problem

The input data is a set of m rows of n probability columns, essentially m in the n matrix, where m = n = the number of vertices on the oriented graph. Rows are boundary sources, and columns are boundary sources. We will, based on the mention of cycles in the question that the graph is cyclic, there is at least one cycle in the graph.

Define the start vertex as s. Let also define the final vertex as a vertex for which there are no outgoing edges, and the set of them as the set T with size z. Therefore, we have z sets of routes from s to the top in T, and the sizes of the set can be infinite due to cycles ¹ . In this case, it cannot be concluded that the final peak will be reached at an arbitrarily large number of steps.

In the input data, the probabilities for rows that correspond to vertices not in T are normalized to a total of 1.0. We consider the Markov property that the probabilities at each vertex do not change with time. This eliminates the use of probability to prioritize routes in graphical search ² .

The final mathematical texts are sometimes called exemplary problems similar to this issue, like drunken random walks to emphasize the fact that the walker forgets the past, referring to the memory-free nature of Markov chains.

Applying Probability to Routes

The probability of hitting a final vertex can be expressed as an endless series of product sums.

P _t = lim _{s → & infin;} & Sigma; & Prod; P _{i, j} ,

where s is the step index, t is the final index of the vertex, i & isin; [1 .. m] and j & isinin; [1 .. n]

Decrease

When two or more cycles intersect (sharing one or more vertices), the analysis is complicated by an endless set of patterns associated with them. Apparently, after some analysis and review of the corresponding academic work , that obtaining the exact set of probabilities of arrival of finite vertices using modern mathematical tools can be performed using a converging algorithm.

Several initial abbreviations are possible.

• The first consideration is to list the end vertex, which is easy, since the corresponding lines have zero probabilities.

• The following consideration is to distinguish any further abbreviations from what academic literature calls irreducible subgraphs. The first depth depth algorithm remembers which peaks have already been visited during the construction of a potential route, so it can be easily modified to determine which peaks are involved in cycles. However, it is recommended that you use existing well-tested, peer-tested graph libraries to identify and characterize subgraphs as irreducible.

The mathematical reduction of the irreducible parts of the graph may or may not be believable. Consider the initial vertex A and the only final vertex B in the graph, represented as {A-> C, C-> A, A-> D, D-> A, C-> D, D-> C, C-> B , D-> B}.

Although it is possible to reduce the graph to probabilistic relations that are absent by cycles through the vertex A, the vertex A cannot be removed for further reduction without changing the probabilities of the vertices leaving C and D, or allowing the resulting probabilities of the edges leaving C and D to be less than 1.0.

Converging first pass width

The first bypass of the width, which ignores revision and allows loops, can iterate over the index of step s, and not some fixed s _max , but some rather stable and exact point in a convergent trend. This approach is especially called if the cycles overlap, creating bifurcations at a simpler periodicity caused by one cycle.

& Sigma; P <sub> ssub> ^{& Delta; h} .

To establish reasonable convergence with increasing s, it is necessary to determine the desired accuracy as a criterion for completing the convergence algorithm and a metric for measuring accuracy by looking at long-term trends in the results at all end vertices. Perhaps it is important to provide criteria in which the sum of the probabilities of the end vertices is close to unity in combination with the metric of convergence of the trend, both a compliance check and accuracy criteria. Almost four convergence criteria may be necessary ³ .

• At the terminal vertex of the probability of convergence of a triangle of a triangle
• High Delta Convergence Trends
• Convergence of the total probability per unit
• The total number of steps (to limit the depth for practical calculations)

Even outside of these four programs, you may need to maintain an interrupt trap that allows you to record and then analyze the output after a long wait without meeting all four of the criteria above.

Sample algorithm with a stable cycle depth

There is a more efficient algorithm than the following, but it is understandable enough, it compiles without warning with C ++ -Wall and creates the desired result for all finite and legitimate directed graphs, and you can also use start and end vertices ⁴ . It is easy to load the matrix in the form given in the question using the addEdge ⁵ method.

 #include <iostream> #include <list> class DirectedGraph { private: int miNodes; std::list<int> * mnpEdges; bool * mpVisitedFlags; private: void initAlreadyVisited() { for (int i = 0; i < miNodes; ++ i) mpVisitedFlags[i] = false; } void recurse(int iCurrent, int iDestination, int route[], int index, std::list<std::list<int> *> * pnai) { mpVisitedFlags[iCurrent] = true; route[index ++] = iCurrent; if (iCurrent == iDestination) { auto pni = new std::list<int>; for (int i = 0; i < index; ++ i) pni->push_back(route[i]); pnai->push_back(pni); } else { auto it = mnpEdges[iCurrent].begin(); auto itBeyond = mnpEdges[iCurrent].end(); while (it != itBeyond) { if (! mpVisitedFlags[* it]) recurse(* it, iDestination, route, index, pnai); ++ it; } } -- index; mpVisitedFlags[iCurrent] = false; } public: DirectedGraph(int iNodes) { miNodes = iNodes; mnpEdges = new std::list<int>[iNodes]; mpVisitedFlags = new bool[iNodes]; } ~DirectedGraph() { delete mpVisitedFlags; } void addEdge(int u, int v) { mnpEdges[u].push_back(v); } std::list<std::list<int> *> * findRoutes(int iStart, int iDestination) { initAlreadyVisited(); auto route = new int[miNodes]; auto pnpi = new std::list<std::list<int> *>(); recurse(iStart, iDestination, route, 0, pnpi); delete route; return pnpi; } }; int main() { DirectedGraph dg(5); dg.addEdge(0, 1); dg.addEdge(0, 2); dg.addEdge(0, 3); dg.addEdge(1, 3); dg.addEdge(1, 4); dg.addEdge(2, 0); dg.addEdge(2, 1); dg.addEdge(4, 1); dg.addEdge(4, 3); int startingNode = 2; int destinationNode = 3; auto pnai = dg.findRoutes(startingNode, destinationNode); std::cout << "Unique routes from " << startingNode << " to " << destinationNode << std::endl << std::endl; bool bFirst; std::list<int> * pi; auto it = pnai->begin(); auto itBeyond = pnai->end(); std::list<int>::iterator itInner; std::list<int>::iterator itInnerBeyond; while (it != itBeyond) { bFirst = true; pi = * it ++; itInner = pi->begin(); itInnerBeyond = pi->end(); while (itInner != itInnerBeyond) { if (bFirst) bFirst = false; else std::cout << ' '; std::cout << (* itInner ++); } std::cout << std::endl; delete pi; } delete pnai; return 0; } 

---

Notes

[1] Improperly processed loops in a directed graph algorithm will hang in an infinite loop. (Note the trivial case where the number of routes from A to B for an oriented graph represented as {A-> B, B-> A} is infinite.)

[2] Probabilities are sometimes used to reduce the cost of a search cycle. The probabilities, in this strategy, are the input values ​​of the meta rules in the priority queue in order to reduce the computational problem of very tedious searches (even for a computer). Early literature on production systems called the exponential nature of the uncontrollable major search for Raman explosions.

[3] It may be practically necessary to determine the probability width of the first probability at each vertex and indicate satisfactory convergence in terms of four criteria

• ? (? Sigma;? P) _t <=? _max ? forall; t
• & Sigma; _{t = 0} ^T ? (? Sigma;? P) _t / T <=? _prsub>
• | & Sigma; & Sigma; & prod; P - 1 | <= u _max , where u is the maximum permissible deviation from unity for the sum of the final probabilities
• s <s <sub> tahsub>

[4] Subject to the availability of sufficient computing resources to support data structures and sufficient time to obtain an answer to a given speed of the computing system.

[5] You can load DirectedGraph dg (7) with the input using two loops nested to iterate over the rows and columns listed in the question. The body of the inner loop would be just the addition of a conditional edge.

 if (prob != 0) dg.addEdge(i, j); 

The variable prob P _{m, n} . The existence of a route is associated only with a zero / non-zero status.

Answer 3

I understand this as the following problem:

Given that the initial distribution should be on each node as a vector b and matrix A, where the probability of a transition from node i to node j at each time step is preserved, somewhat resembling an adjacency matrix.

Then the distribution b_1 after one time step A x b. The distribution of b_2 after two time steps: A x b_1. Similarly, the distribution of b_n is A ^ nx b.

To approximate b_infinite, we can do the following:

 Vector final_probability(Matrix A, Vector b, Function Vector x Vector -> Scalar distance, Scalar threshold){ b_old = b b_current = A xb while(distance(b_old,b_current) < threshold){ b_old = b_current b_current = A x b_current } return b_current } 

(I used the names of mathematical variables for consensus)

In other words, we assume that the sequence of distributions converges well after a given threshold. Perhaps this is not so, but will usually work.

You might want to add the maximum number of iterations to it.

Euclidean distance should work well as a distance.

(The Markov chain concept is used here, but it is rather a pragmatic solution)