Consider the graph $(V,E)$ with vertex set $V=\{v\_1,...,v\_n\}$ and edge set $E\subset V\times V$. Further, assume that $\forall v\_i\in V, (v\_i,v\_i)\in E$. 


Assume that each vertex has an $\textit{initial value}$ (i.e. there is a function $\phi\_0:V\rightarrow\mathbb{R}$). We will think of these values as changing with time as I describe below.


Also assume that there each edge as an associated $\textit{weight}$. By this I mean that is a function $\omega:E\rightarrow[0,1]$ such that


1.) $\forall$ $i\in\{1,...,n\}$ $\omega(v\_i,v\_i) > 0$


2.) $\forall i$ we have that the following holds:


$$\sum\_{(v\_i,v\_j)\in E}\omega(v\_i,v\_j)=1$$.


Finally, we define a discrete time dynamical system by letting 


$$\phi\_k(v\_i)=\sum\_{(v\_i,v\_j)\in E}\omega(v\_i,v\_j)\phi\_{k-1}(v\_j).$$


So to sum up the situation we have a graph with elements of $\mathbb{R}$ assigned to each vertex, and we have a dynamical system that for each time interval it averages the values of a vertex with all adjacent vertices, where the average is a weighted average with weights given by $\omega$. Note that $\omega$ does not depend on $k$. We also assume that the vertex itself is a non-zero component of the average. 


I am generally interested in the behavior of this type of dynamical system. Specific types of questions that I'm interested in are:


1.)What is the long term behavior of this system? Are the functions $\phi\_k$ asymptotically constant? What properties must exist on $\omega$ or $\phi\_0$ to either guarantee this or guarantee that it does not happen (ignoring the trivial case where $\phi\_0$ is constant.)


2.) What assumptions can we put on $\omega$ and $\phi\_0$ such that the $\phi\_k$ approach a non-constant steady state (ie such that $\phi\_k\rightarrow \phi$ pointwise where $\phi$ is non-constant.) My feeling is that this always happens since we are taking averages then the images of all $\phi\_k$ should lie inside some compact subset of $\mathbb{R}^n$. 


3.) Are there any way to determine the speed of either of the convergences above.


I realize that the setup is fairly general so I'm willing to add additional assumptions if needed. Any thoughts would be greatly appreciated!



Long term behavior of a certain discrete time dynamical system on graphs
Just set matrix $A = [\omega(v\_i, v\_j)]$ and $\mathbf{x}\_k = [\phi\_k(v\_i)]$. Then the linear dynamic system is $\mathbf{x}\_{k+1} = A\mathbf{x}\_k$. $A$ has property that $A\mathbf{1} = \mathbf{1}$, where $\mathbf{1}$ is all-one vector.


The dynamics system has close form as: $\mathbf{x}\_k = A^k\mathbf{x\_0}$. Basically you can analyze the eigen structure of A to understand the behavior of $\mathbf{x}$. Usually if $r$ is the eigenvalue with biggest module, then $\mathbf{x}\_\infty / r^k$ converges to its associated eigenvector $v$. "Usually" means $x\_0\cdot v \neq 0$. 


From your description, A could be identity matrix and $\mathrm{x}\_\infty$ will just be $\mathbf{x}\_0$. In general, if all element of $A$ is greater than $0$, then you can refer to Perron-Frobenius theorem. Ccombined with $A\mathbf{1} = \mathbf{1}$, the single largest eigenvalue is 1 with $\mathbf{1}$ as its eigenvector. So the system you mentioned will converge to a constant solution. 


<https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem>


