1
$\begingroup$

Assuming a graph $G$ with $N$ nodes distributed in a $\mathcal{L}\times\mathcal{L}$ area randomly. There is an edge between two nodes if and only if the Euler distance between them is equal or less than $\mathcal{R}$. The adjacent matrix is $A$. We define an operation on adjacent matrix "$\circ$". For adjacent matrix $A$ and $B$ $$C=A\circ B$$ $$ c_{ij}=\left\{ \begin{array}{rcl} 0 & & {\sum_{k=1}^{N}a_{ik}b_{kj}=0}\\ \\ 1 & & {\sum_{k=1}^{N}a_{ik}b_{kj}>0} \end{array} \right. $$ $A^{[1]}=A$, $A^{[i+1]}=A^{[i]}\circ A$. Define the intial adjacent matrix $A_0=A$. We select a pair of elements randomly from $A_i$ :$A_i(m,n)$ and $A_i(n,m)$. $A_{i+1}(m,n)=A_{i+1}(n,m)=1-A_{i}(m,n)=1-A_{i}(n,m)$. Other element of $A_{i+1}$ is equal to the corresponding element of $A_i$. Then we can get a series of matrix $A_0, A_1, \cdots, A_s$. There comes the question: $A_0^{[\infty]} \circ A_1^{[\infty]} \circ A_2^{[\infty]} \circ \cdots \circ A_s^{[\infty]}$=$?$ I have waited for more than a week? Could anyone help?

$\endgroup$
3
  • $\begingroup$ Is $A_0$ reflexive? $\endgroup$
    – Untitled
    Sep 12, 2013 at 5:59
  • $\begingroup$ Yes, but $A_0$ is uncertain matrix due to the random distribution of nodes. I know the meaning of the result. What I'm confused is how to calculate the result. $\endgroup$
    – xzhh
    Sep 13, 2013 at 2:40
  • $\begingroup$ Don't ask multiple questions in one post. It makes it hard to get a good answer. Post the new one separately. $\endgroup$
    – Untitled
    Sep 13, 2013 at 4:36

1 Answer 1

1
$\begingroup$

First, observe a few facts:

  1. $M_G^{[i]} = M_G^i$
  2. $M_G^{[\infty]} = M_G^\infty$ is the transitive closure of graph $G$.
  3. $(A\circ B)_{ij}=1$ if and only if $N_{G_A}(v_i) \cap N_{G_B}(v_j) \neq \emptyset$.
  4. $G_{A_{i+1}}$ is obtained from $G_{A_i}$ by addition or removal of exactly one edge.
  5. If the added/removed edge is not a bridge, then $A_i^{[\infty]}=A_{i+1}^{[\infty]}=A_i^{[\infty]} \circ A_{i+1}^{[\infty]}$.

All of the above are easily proven. Here we claim that if the added/removed edge is a bridge, then $A_i^{[\infty]} \circ A_{i+1}^{[\infty]}$ equals to the operand that corresponds to the graph with the extra edge. Now we prove the stronger proposition that if $G_B$ is obtained from $G_A$ by addition of some number of edges, then $A^{[\infty]} \circ B^{[\infty]} = B^{[\infty]}$. Let $v_i$ and $v_j$ be two arbitrary vertices. There are three cases for $v_i$ and $v_j$:

  1. $v_i$ and $v_j$ are in the same component of $G_A$ and in the same component of $G_B$. Then $(A^{[\infty]} \circ B^{[\infty]})_{ij} = 1$ because $v_i \in N_{G_A}(v_i) \cap N_{G_B}(v_j)$. Thus $(A^{[\infty]} \circ B^{[\infty]})_{ij}=B_{ij}^{[\infty]}=1$
  2. $v_i$ and $v_j$ are in different components of $G_A$ but in the same component of $G_B$. Then with the same argument $(A^{[\infty]} \circ B^{[\infty]})_{ij}=B_{ij}^{[\infty]}=1$.
  3. $v_i$ and $v_j$ are in different component in both $G_A$ and $G_B$. Then obviously $N_{G_A}(v_i) \cap N_{G_B}(v_j) = \emptyset$ and thus $(A^{[\infty]} \circ B^{[\infty]})_{ij}=B_{ij}^{[\infty]}=0$.

That completes the proof that $A^{[\infty]} \circ B^{[\infty]}=B^{[\infty]}$.

By this proposition, it can be proven by induction that $A_0^{[\infty]} \circ A_1^{[\infty]} \circ A_2^{[\infty]} \circ \cdots \circ A_s^{[\infty]}$ equal to the transitive closure of the graph that has every edge that any of the $G_{A_i}$ had. The exact value, of course, can not be evaluated without knowledge of $s$ and the way we choose the edges to be added/removed.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – xzhh
    Sep 13, 2013 at 3:17
  • $\begingroup$ 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? $\endgroup$
    – Untitled
    Sep 13, 2013 at 4:33
  • $\begingroup$ 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$? $\endgroup$
    – xzhh
    Sep 13, 2013 at 4:46
  • $\begingroup$ I assume by randomly you mean uniformly with respect to $x$ and $y$ coordinates. right? $\endgroup$
    – Untitled
    Sep 13, 2013 at 8:57
  • $\begingroup$ $s$ is the number of edges added or removed. It is the index of last matrix in the statement of the question. $\endgroup$
    – Untitled
    Sep 13, 2013 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.