Originally posted here: <https://math.stackexchange.com/questions/276167/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?


**edit**: The graph is large and follows this model: <http://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model> . Also, for ~1% of nodes, $\phi$ is the identity. There is some related work here: <http://www.cs.cmu.edu/~zhuxj/pub/CMU-CALD-02-107.pdf>


**edit**: Looks like I can just replace the $P(j \rightarrow i)$ in the label propagation paper with $P(j \rightarrow i) = 1\; if \; \text{j is the median, }0 \text{ else}$, then I can copy their convergence result.


**edit**: Wait, no. If I do that then P changes each step so it's not a direct copy...



Fixed point theorem on graphs?
If I am not mistaken, this problem was discussed in the article


Zbl 0194.13702
Lyubich, Yu.I.; Tabachnikov, M.I. Subharmonic functions on a directed graph.
Siberian Math. J. 10, 432-442 (1969).


(unfortunately in Russian; I don't know whether there is an English translation)


