2
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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? $\endgroup$
    – Bati
    Commented Jul 4, 2013 at 13:02
  • 1
    $\begingroup$ 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... $\endgroup$
    – Joseph O'Rourke
    Commented Jul 4, 2013 at 18:36
  • 1
    $\begingroup$ 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! $\endgroup$
    – xzhh
    Commented Jul 5, 2013 at 6:31
  • 1
    $\begingroup$ 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! $\endgroup$
    – xzhh
    Commented Jul 5, 2013 at 6:32
  • $\begingroup$ 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. $\endgroup$
    – user25199
    Commented Jul 12, 2013 at 9:51

0

Reset to default

You must log in to answer this question.