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

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?

share|improve this question
    
Is $A_0$ reflexive? –  Untitled Sep 12 '13 at 5:59
    
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. –  xzhh Sep 13 '13 at 2:40
    
Don't ask multiple questions in one post. It makes it hard to get a good answer. Post the new one separately. –  Untitled Sep 13 '13 at 4:36
add comment

1 Answer

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.

share|improve this answer
    
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? –  xzhh Sep 13 '13 at 3:17
    
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? –  Untitled Sep 13 '13 at 4:33
    
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$? –  xzhh Sep 13 '13 at 4:46
    
I assume by randomly you mean uniformly with respect to $x$ and $y$ coordinates. right? –  Untitled Sep 13 '13 at 8:57
    
$s$ is the number of edges added or removed. It is the index of last matrix in the statement of the question. –  Untitled Sep 13 '13 at 8:59
show 2 more comments

Your Answer

 
discard

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

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