# Fixed point theorem on graphs?

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?

-
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
@Sanchez Certainly any bipartite graph will have the same problem. –  Erick Wong Jan 12 '13 at 4:26

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.
Hmmm, this is interesting. But isn't your $A$ computing a weighted mean? –  dranxo Jan 12 '13 at 4:14
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