# Reachability in dynamic random graphs

There has been some advice on how to ask questions. So I reask my question.I have a problem related to graph theory, random graphs or random geometric graphs in special that really confuses me. Assuming Graph G with node set V={x1,x2,…,xn}, all the nodes are moving in R2 space. There is an edge between xi and xj if and only if the Euclidean distance is less than r(r is a constant). If the distance is larger than r due to the movement, the edge breaks. Edges emerge and break as a result of nodes movement. Assuming the movement is modeled by Brownian motion, I would like to analysis the property of reachability. Given a time threshold T and the speed of node movement , how can I analysis the probability of that one node can find a path to any node during T from time dimension? The key is the movement of nodes and edges break and emerge with time passing. How to compute the orobability of reachiabiliy?Thanks very much!

-
Does each particle move as an independent Brownian motion? Are you looking for the probability at a fixed time $t$ you have a connection between $x_1$ and $x_2$? Or the probability that $x_1$ and $x_2$ were ever connected during the interval $[0,T]$? What are the initial conditions of the positions? –  Bati Jul 4 '13 at 13:02
You might find some literature under "dynamic ad-hoc wireless networks," because unit-distance graphs (UDGs) are a prevalent model for such networks. I don't know this literature well enough to point you to something specific... –  Joseph O'Rourke Jul 4 '13 at 18:36
Response to Bati: Each particle moves as an independent Brownian motion. I'm looking for the probability of reachability that x1 can reach x2 during a fixed timeslot T. "Reach" means that x1 can find a path to x2 in time dimension as edges emerge and disappear as a result of nodes movement. At the very first, nodes are randomly distributed as a Possion. Respond to Joseph O'Rourke: I have read many papers related to dynamic ad-hoc wireless networks, but most of them do simulation instead of theoretical analysis. Thanks all the same! –  xzhh Jul 5 '13 at 6:31
Respond to Joseph O'Rourke: I have read many papers related to dynamic ad-hoc wireless networks, but most of them do simulation instead of theoretical analysis. Thanks all the same! –  xzhh Jul 5 '13 at 6:32
I think it is best to specialise to particular limits - high and low density, for example. At high density, reachability is complete except for a few isolated nodes. At low density, it is probably related to extreme value theory of the Brownian motion. –  Carl Jul 12 '13 at 9:51