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** is , where is the directed Laplacian. As in the usual Laplacian for undirected graphs which leads to the heat equation , the ** advection Laplacian** uses difference operators: the modification of the gradient which is the minimum of and . The divergence as well as are defined by the usual exterior derivative . The ** consensus model** is the situation, where the graph is replaced by its ** reverse graph** , where all directions are reversed. One can therefore easily focus on advection. The advection dynamics relates to Markov chains: If , then is a ** left stochastic matrix**, a Markov operator, which maps probability vectors to probability vectors. The kernel of is related to the fixed points of . Assume , then and . ** Perron-Frobenius** allows to study the structure of the equilibria or equivalently the kernel of .

Lets look at the kite graph. The Laplacian of is = – , where is the incidence matrix. When equipped with an orientation is a ** digraph**. Given the orientation, the incidence matrix is the matrix ${\rm div} = D_{a,e(b)}$ which is if the arrow between points towards and else. It is the discrete analogue of the divergence. The matrix is the gradient. Now, is the Laplacian: =.

The gradient of the directed graph contains only the incoming entries. The modified Laplacian is . Again it is of the form , where is the diagonal ** incoming vertex degree diagonal matrix** and is the adjacency matrix if .

Both matrices and have the property that the sum of each column entries is constant . This means that have the eigenvector with eigenvalue . So, also has an eigenvalue .

We can write , where is the diagonal part and the off diagonal part. Now, in the case when all incoming vertex degrees are nonzero, we can invert and form . This is a stochastic matrix in the sense that all entries are non-negative in and that the sum over all column entries is equal to . These are now transition probabilities.

The ** heat equation** is . The wave equation is . The advection equation is . Now, while is symmetric and has non-negative real eigenvalues, the matrix can have complex eigenvalues. In the kite example, the eigenvalues of are $\{4,4,2,0 \}$, the eigenvalues of the directed graph with a loop are , the spectrum of is .