Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a graph $G=(V,E)$ where to each vertex $v$ I have associated a value, $\hat{v}$ (ie I have a "network" in the terminology here http://snap.stanford.edu/snap/index.html ).

Let $\phi : \hat{V} \rightarrow \hat{V}$ be the function which takes the value associated to each node and replaces it with median of the values of the adjacent nodes.

Empirically, iterating $\phi$ converges. Why?

share|improve this question
    
What if you have a two-point connected graph? Then iteration would just switch the assigned value of the two vertices. –  user27126 Jan 12 '13 at 2:55
    
Uh, semi-empirically it's converging. –  dranxo Jan 12 '13 at 2:57
    
My graph is large and the data are [0,1] iid. –  dranxo Jan 12 '13 at 2:58
    
The graph is large, but fixed throughout the iteration. Only the values change. –  dranxo Jan 12 '13 at 2:59
1  
@Sanchez Certainly any bipartite graph will have the same problem. –  Erick Wong Jan 12 '13 at 4:26

1 Answer 1

The following works for the mean of vertices, not quite the median. This will more or less work for medians if your vertices are distributed in a symmetric way so that the mean is roughly the median. I suspect that barring some pathological cases, after enough applications of $\phi$, the distribution of vertex values will smooth out so that the median and means are very close to each other.

Write out the vertices of your graph as a vector $v=(v_1,v_2,\ldots,v_n)$. The action of a $\phi$ which averages neighboring vertices can be represented by a matrix $A$, in the sense that the $i$'th row of $A$ consists of $1/d_i$'s and the rest are zeros, where the locations correspond to how the vertices are connected and $d_i$ is the degree of vertex $i$. By Gereshgorin circle theorem, the eigenvalues must have absolute value less than d_i(1/d_i)=1, i.e. $|\lambda_i|\leq 1$. This hints that convergence may be possible.

More succinctly, you can view $A$ as a row stochastic matrix, or more bluntly as a Markov chain, which is guruanteed to have the above eigenvalue restraints. Moreover, every stochastic matrix has at least one stationary distribution $\pi$ which satisifes $\pi A=\pi$, the uniqueness of $\pi$ will depend on whether or not $A$ is irreducible. Whether or not $A^n$ applied to any vector converges to $\pi$ depends on the periodicity of $A$. In the example that Sanchez gave above, the two point connected graph has periodicity 2 and hence will not have convergence to any stationary distribution and will oscillate forever.

Roughly speaking if your graph is very large and pretty well connected, it likely will not be periodic so you'll see convergence to a fixed distribution of some kind, which may even be the same for any choice of initial vertex values.

share|improve this answer
    
Hmmm, this is interesting. But isn't your $A$ computing a weighted mean? –  dranxo Jan 12 '13 at 4:14
    
@rcompton: I've added a slight edit at the top. I can't think of any obvious reasoning how to carry everything strictly over to medians. –  Alex R. Jan 12 '13 at 4:25
    
Thanks, I noticed the edit. This is indeed an interesting approach but not quite the same problem. I did some looking around and think my question might very close to "$k$-medians". –  dranxo Jan 12 '13 at 4:26

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.