After experimenting with using a graph's Laplacian on its own adjacency matrix in a straightforward way, I found that it was doing the blurring operation I want on the tail end of each graph edge, but not on the head ends. I designed a new operation that works on both ends of each edge.
I call this double operation "Laplacianoid" because it's made of two Laplacian operations, not one:
Note is not a product of two matrices; it's the operation of linear operator on matrix . Given an matrix , is a linear operator on the space of matrices. If both and are symmetric, then is also symmetric.
Note: I am also studying a stochastic process based on the Laplacianoid operation: see Laplacian Experiments/Stochastic for the analysis of that process.
Simulation indicates that this tends to equilibrium at a multiple of the complete graph, that is at
Q: Are there other equilibria? Which are stable?
Linear algebra of ℒ
Let's assume that is symmetric here (or equivalently, that the graph is undirected), so that . Since is a linear operator on the -dimensional space of matrices, it has eigenvalues, and an eigenmatrix (rather than eigenvector) for each. If are the eigenvectors of with eigenvalues , the eigenmatrices of are with eigenvalues :
When is symmetric, has nonnegative eigenvalues, so the only zero eigenvalues of come from zero eigenvalues of . If is connected, the only zero eigenvector of the Laplacian is the vector of all ones, , so the only zero eigenmatrix of is .
If the graph is not connected, it's a union of disjoint subgraphs with adjacency matrices with . The null space of contains orthogonal eigenvectors with . It follows that the nullspace of is -dimensional and the corresponding eigenmatrices are constructed from pairs of these as above.
We know already that because it's zero for each provided is symmetric, and by the same process on each , so in the ODE the sum of all edge weights is conserved. If the equilibrium matrix is connected, then, it must be that .
This can be plugged in to give us the Laplacianoid operation we know:
In this way we can think of the Laplacianoid as a sort of hypermatrix - an object with four indices that operates on matrices the way a matrix operates on vectors.
The Jacobian of the dynamics
To assess the stability of the ODE's equilibria, we need to look at its Jacobian. Since
As with a regular vector dynamical system, if is an equilibrium, a point near the equilibrium has derivative , and we want to know if there is any such that grows rather than shrinking. This really is a regular vector dynamical system, notwithstanding the fact that the state variables are written in a square rather than a column, so all the linear theory applies, including the fact that is hyperbolically stable if and only if all the eigenvalues of the Jacobian are negative.
So let's look at the quadratic form associated with the Jacobian, because if we can show that the quadratic form is never positive (that is, if it's a negative definite or negative semidefinite form) we can conclude that the eigenvalues of the Jacobian are all negative or non-positive. Because the ODE is restricted to symmetric matrices as long as the initial value is symmetric, we can restrict ourselves to the action of the Jacobian on symmetric perturbations . The quadratic form is
Let's investigate the complete-graph equilibrium, since I think it ought to be stable. In this case
this works for the third term of the above expression as well as for the second, so we conclude that
and so it is negative semidefinite. is zero when for all ; for symmetric this condition implies that all entries of are equal: . These are the zero eigenmatrices of the Jacobian, and all other eigenvalues are negative.
Consequently this is a hyperbolically stable fixed point, except that it's neutral to the addition of a constant to all entries of the matrix. The dynamics conserves the sum of all matrix entries, so in fact it's entirely stable.
The linearized system is
A positive eigenmatrix
Given an equilibrium matrix made of multiple disjoint cliques, let us choose two distinct cliques and , and let except that is for every edge connecting and , for every edge within and for every edge within .
So if this is going to be an eigenmatrix we must have
and given this we require
(Note that is not a graph's adjacency matrix itself, it's a perturbation to , so it's fine for it to have negative entries. It adds weight to edges that are zero, and subtracts from edges that are positive.)
A corrected Laplacianoid
Here's a variation on the Laplacianoid, with a correction term so that it does the same thing but doesn't create loops, i.e. nonzero . The Laplacanoid equation does, because of lots of terms like . So to remove those:
should conserve the sum of edge weights, and hopefully will go to all edges equal, but with no loops.
This is also a linear operator. I haven't done any simulations or analysis on it yet...