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?
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.