Partial differential equations on graphs

Partial differential equations on graphs

During the summer and fall of 2016, Annie Rak did some URAF (a program formerly called HCRP) on partial differential equations on graphs. It led to a senior thesis in the applied mathematics department. Here is a project page and here [PDF] were some notes from the summer. The research of Annie mostly dealt with advection models on directed graphs (digraphs).

As partial differential equations in general relate to diffusion process, this happens also here. The stochastic process is the Markov dynamics defined on the graphs. The advection model for a directed graph G is u' = -Lu, where L={\rm div} V {\rm grad}_0 u is the directed Laplacian. As in the usual Laplacian L=d^*d for undirected graphs which leads to the heat equation u' = -Lu, the advection Laplacian uses difference operators: the modification of the gradient {\rm grad}_0 which is the minimum of {\rm grad} and 0. The divergence {\rm div}=d^* as well as {\rm grad}=d are defined by the usual exterior derivative d. The consensus model is the situation, where the graph G is replaced by its reverse graph G^T, where all directions are reversed. One can therefore easily focus on advection. The advection dynamics relates to Markov chains: If L=D-A, then M=A D^{-1} is a left stochastic matrix, a Markov operator, which maps probability vectors to probability vectors. The kernel of L is related to the fixed points of M. Assume L D^{-1} u=0, then (D-A) D^{-1} u=0 and u=A D^{-1} u = Mu. Perron-Frobenius allows to study the structure of the equilibria or equivalently the kernel of L.

Lets look at the kite graph. The Laplacian of G is L=B-A=  \left[ \begin{matrix} 3 & -1 & -1 & -1 \\ -1 & 2 & 0 & -1 \\ -1 & 0 & 2 & -1 \\ -1 & -1 & -1 & 3  \end{matrix} \right] = \left[ \begin{matrix} 3 & 0 &  0 & 0  \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \\ \end{matrix} \right]\left[ \begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 &  0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{matrix} \right], where A is the incidence matrix. When equipped with an orientation G is a digraph. Given the orientation, the incidence matrix is the 4 \times 5 matrix ${\rm div} = D_{a,e(b)}$ which is 1 if the arrow between a,b points towards a and -1 else. It is the discrete analogue of the divergence. The 5 \times 4 matrix {\rm grad} = D^* is the gradient. Now, {\rm div} \circ {\rm grad} is the Laplacian: \left[ \begin{matrix} -1 & 0 & 1 &  & 1 \\ 1 &-1&0&0&0 \\ 0&1&-1&-1&0 \\ 0&0&0&1&-1 \\ \end{matrix} \right] \left[ \begin{matrix}  -1 & 1 &  0 &0 \\ 0 & -1 & 1 & 0 \\ 1&0&-1&0 \\ 0 &0&-1&1 \\ 1&0&0&-1 \\ \end{matrix} \right] =\left[ \begin{matrix} 3&-1&-1&-1 \\ -1&2&-1&0 \\ -1&-1&3&-1 \\ -1&0&-1&2 \\ \end{matrix} \right].

The gradient of the directed graph contains only the incoming 1 entries. The modified Laplacian is L_0={\rm div} \circ {\rm grad}_0. Again it is of the form B-A, where B is the diagonal incoming vertex degree diagonal matrix and A is the adjacency matrix A_{ij}=1 if i \to j.
Both matrices L and L_0 have the property that the sum of each column entries is constant 0. This means that L^T, L_0^T have the eigenvector \langle 1, \dots 1 \rangle with eigenvalue 0. So, also L_0 has an eigenvalue 0.

We can write L_0 = B_0 - A_0, where B_0 is the diagonal part and A_0 the off diagonal part. Now, in the case when all incoming vertex degrees are nonzero, we can invert B_0 and form M_0 = -A_0 B_0^{-1}. This is a stochastic matrix in the sense that all entries are non-negative in [0,1] and that the sum over all column entries is equal to 1. These are now transition probabilities.

The heat equation is u' = -L u. The wave equation is u''=-L u. The advection equation is u'=-L_0 u. Now, while L is symmetric and has non-negative real eigenvalues, the matrix L_0 can have complex eigenvalues. In the kite example, the eigenvalues of L are $\{4,4,2,0 \}$, the eigenvalues of the directed graph with a loop L_1 are \{ 0,(3 + i \sqrt{3})/2,(3 - i \sqrt{3})/2,2 \}, the spectrum of L_2 is \{ 3,1,1,0 \}.