0
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Wow, don't know why I didn't realize how easy this was. Thanks! $\endgroup$ Apr 19, 2016 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.