Estimating nodes and paths in directed acyclic graphs by random walks
Estimating the number of nodes and paths in a DAG by following a random path
Data Structures and Algorithms
Summary
Counting all the points and routes in a network that flows in one direction without loops can be very hard. The authors talk about an old simple way to estimate the number of points by following a random route from start to end. They also tweak this method to estimate how many paths exist between starting and ending points. They improve the method by having many walkers work together, making the estimate better and connecting several past approaches into one.
What this means in practice
- •For software engineers: Estimate the size of complex workflow graphs when full enumeration is infeasible by using coordinated random path sampling.
- •For bioinformatics analysts: Approximate counts of source-to-sink pathways in biological networks to assist in pathway analysis.
Authors
Günter Rote
Abstract
We investigate a simple method to compute an unbiased estimate of the number of nodes of a directed acyclic graph (DAG) by following a random directed path. This method is due to Leonard Pitt from 1987, and it generalizes a method of D. E. Knuth from the 1960s for estimating the size of a rooted tree. A slight variation makes it possible to estimate the number of source-sink paths. We extend the algorithm to use many "agents" that walk cooperatively through the graph. This extension unifies and generalizes several methods that have been proposed for approximately counting the nodes of a tree.