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…
Best Answer
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)