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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .