Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
2  
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
1  
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: –  xzhh Jul 5 '13 at 6:21
1  
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
1  
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.