Timeline for Reachability in graphs using adjacent matrix
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 13, 2013 at 9:45 | comment | added | xzhh | I'd like to explain the physical meaning of the problem. The graph is a dynamic random graph(nodes are always moving). At any moment, a snapshot of the graph may be un-connected. However， a node can find a path to another node far from itself as time goes by. $A_i$ is the adjacent matrix of the snapshot of the graph. $(i,j)-th$ element of $A_i^{[\infty]}$ equals $1$ iff there is a path between $i,j$ at the moment. By the operation $\circ$ we can calculate the path in time domain. I hope I had explained it clearly. | |
| Sep 13, 2013 at 9:36 | comment | added | xzhh | Right! $s$ is a variable and the result is related to $s$. We can figure that there are more elements of the result equal to $1$ as $s$ get larger. How many elements of the result are equal to $1$? This is a question. | |
| Sep 13, 2013 at 8:59 | comment | added | Untitled | $s$ is the number of edges added or removed. It is the index of last matrix in the statement of the question. | |
| Sep 13, 2013 at 8:57 | comment | added | Untitled | I assume by randomly you mean uniformly with respect to $x$ and $y$ coordinates. right? | |
| Sep 13, 2013 at 4:46 | comment | added | xzhh | All the $N$ nodes are distributed randomly in the $L*L$ area and there is an edge between a node pair iff the distance between them is equal to or less than $R$. $A_0$ is not hard to be obtained. What's the meaning of $s$? | |
| Sep 13, 2013 at 4:33 | comment | added | Untitled | So you are saying that the edges are selected uniformly at random, and you want to calculate the probability distribution of $A_0^{[\infty]} \circ \cdots \circ A_s^{[\infty]}$, right? Well, we also need to know the nature of $A_0$ and $s$ for that. What about them? | |
| Sep 13, 2013 at 3:17 | comment | added | xzhh | Thank you very much for your reply. I have got a better understanding of the problem. If I reduce $A_0^{[\infty]} \circ A_1^{[\infty]} \circ A_2^{[\infty]} \circ \cdots \circ A_s^{[\infty]}$ to $B_0^{[\infty]} \circ B_1^{[\infty]} \circ B_2^{[\infty]} \circ \cdots \circ B_t^{[\infty]}$, $A_i^{[\infty]} \circ\cdots A_{i+x}^{[\infty]}$-> $B_?^{\infty}$ if there is only addition of edges, then there is only removal of an extra edge from $B_i$ to $B_{i+1}$. If we choose randomly with the same probabilty from all the node pairs and change its state 0<->1, can we calculate the result? | |
| Sep 12, 2013 at 6:50 | history | answered | Untitled | CC BY-SA 3.0 |