<p>Not very practical, but you can sample from a the polytope of feasible flows using the well-known random walk techniques, see for example this <a href="http://ad.bolyai.hu/~miki/KLSVol5.pdf" rel="nofollow">classical paper</a> by Kannan, Lovasz and Simonovits. These algorithms allow you to sample in polynomial time (in the dimension) from a distribution which is arbitrarily close to uniform in $L_1$ distance. </p>

CC BY-SA 3.0
2014-07-24T22:33:25.727Z
2014-07-24T22:33:25.727Z
Sasho Nikolov
<p>A <a href="http://en.wikipedia.org/wiki/Flow_network" rel="nofollow">flow network</a> is a directed graph in which each edge has a capacity. A flow through this network is an assignment of a value to each edge that is less or equal to the edge capacity, and such that the net incoming flow to every node balances with the net outcoming flux at that node. Two special nodes are exempted from this last restriction: the source (which can output a net non-zero flux) and the sink (which can receive a net non-zero flux).</p>

<p>There are algorithms to find the maximum net flow from source to sink in such a network (for example, <a href="http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm" rel="nofollow">Ford-Fulkerson algorithm</a>).</p>

<p>I am looking for algorithms that generate <em>pseudo-random</em> admissible flows through such a network. Hopefully the space of admissible flows should be sampled as uniformly as possible. What methods are available here?</p>

CC BY-SA 3.0
2014-07-24T13:24:30.837Z
What properties should a *"pseudo-random admissible flow"* have? One easy way to get some kind of random flow: take a maximum flow, break it up into paths, and choose a random linear combination of these paths. Is this sufficient for your purposes?
Peter Shor 
CC BY-SA 3.0
2014-07-24T13:28:51.577Z
@PeterShor The pseudo-random generator should explore as uniformly as possible the space of all flows. I think that starting with a maximum flow is very biased and many flows will never appear.
a06e
CC BY-SA 3.0
2014-07-24T13:54:43.940Z
What is *"uniformly as possible"*? I assume you want the flows to be close to the uniform distribution when restricted to the space of all admissible flows. You should probably add this criterion to your question. The word *"pseudo-random"* is quite vague, except in cryptographic applications.
Peter Shor 
CC BY-SA 3.0
2014-07-24T13:58:50.750Z
@PeterShor I edited the question.
a06e
CC BY-SA 3.0
2014-07-24T20:39:55.220Z
idea: randomly change edge capacities to less than their max values, and find a maximum flow for that modified network. this paper also seems like it may have some relevant theory? [Random Sampling in Cut, Flow, and Network Design Problems (1994)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.2225) Karger
vzn
CC BY-SA 3.0
2014-07-25T02:27:12.630Z
The Metropolis algorithm might actually work well in this case. Choose a random "augmenting path" (so you can go along edges both backwards and forwards), figure out the largest amounts of flow you can push backwards and forwards along this path and still stay admissible, and choose a random value between these two extremes. Metropolis says this converges eventually to the uniform distribution on feasible flows. The only question is: how fast?
Peter Shor 
<pseudorandom-generators><flow-problems>
Random flows through fixed network
a06e
# Random flows through fixed network

(Asked by: username_0 on 2014-07-24)

A [flow network](http://en.wikipedia.org/wiki/Flow_network) is a directed graph in which each edge has a capacity. A flow through this network is an assignment of a value to each edge that is less or equal to the edge capacity, and such that the net incoming flow to every node balances with the net outcoming flux at that node. Two special nodes are exempted from this last restriction: the source (which can output a net non-zero flux) and the sink (which can receive a net non-zero flux).

There are algorithms to find the maximum net flow from source to sink in such a network (for example, [Ford-Fulkerson algorithm](http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm)).

I am looking for algorithms that generate *pseudo-random* admissible flows through such a network. Hopefully the space of admissible flows should be sampled as uniformly as possible. What methods are available here?

**Tags:** pseudorandom-generators, flow-problems

> **Comments:**
> **username_1**: What properties should a *"pseudo-random admissible flow"* have? One easy way to get some kind of random flow: take a maximum flow, break it up into paths, and choose a random linear combination of these paths. Is this sufficient for your purposes?  
> **username_0**: @PeterShor The pseudo-random generator should explore as uniformly as possible the space of all flows. I think that starting with a maximum flow is very biased and many flows will never appear.  
> **username_1**: What is *"uniformly as possible"*? I assume you want the flows to be close to the uniform distribution when restricted to the space of all admissible flows. You should probably add this criterion to your question. The word *"pseudo-random"* is quite vague, except in cryptographic applications.  
> **username_0**: @PeterShor I edited the question.  
> **username_2**: idea: randomly change edge capacities to less than their max values, and find a maximum flow for that modified network. this paper also seems like it may have some relevant theory? [Random Sampling in Cut, Flow, and Network Design Problems (1994)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.2225) Karger  
> **username_1**: The Metropolis algorithm might actually work well in this case. Choose a random "augmenting path" (so you can go along edges both backwards and forwards), figure out the largest amounts of flow you can push backwards and forwards along this path and still stay admissible, and choose a random value between these two extremes. Metropolis says this converges eventually to the uniform distribution on feasible flows. The only question is: how fast?  

---

## 1 answers

### Answer by username_3 on 2014-07-24. Score: 4

Not very practical, but you can sample from a the polytope of feasible flows using the well-known random walk techniques, see for example this [classical paper](http://ad.bolyai.hu/~miki/KLSVol5.pdf) by Kannan, Lovasz and Simonovits. These algorithms allow you to sample in polynomial time (in the dimension) from a distribution which is arbitrarily close to uniform in $L\_1$ distance.


---

