I'm currently running a simulation on a bunch of randomly generated points, each with two randomly selected 'partners' from the set of points. In the simulation the points try to move such that they are equidistant from both of their partners. I want to relate the #iterations to convergence with some quantity related to the distribution of points.


I realize that the set of points is effectively a weighted di-graph where the edges/weights represent the connections/distances between partners. I was wondering whether the adjacency matrix of this graph could give me a quantity to plot against #iterations. The Eigenvalues seem like a good candidate.


I know that for linear transformations, Eigenvalues describe the amount an Eignevector scales, but what do they represent with weighted di-graphs?


Any help/clarity would be appreciated!



Significance of the Eigenvalues of the adjacency matrix of a weighted di-graph
Your idea is pretty much spot on; this is the area of [spectral graph theory](https://en.wikipedia.org/wiki/Spectral_graph_theory). Often the graph Laplacian is used rather than its adjacency matrix -- the Laplacian is defined as $L = D - A$ where $A$ is the adjacency matrix and $D$ is a diagonal matrix whose $(i,i)$ entry is the sum of the weights of edges out of vertex $i$.


The smallest eigenvalue of the Laplacian is $0$ (consider the all-$1$ vector), and the second-smallest eigenvalue is a measure of the "expansion" or mixability of the graph. So when taking a random walk on a graph, the higher its second eigenvalue, the faster its provable convergence to a stationary distribution. One also considers the normalized Laplacian. 


This is related to [Cheeger's inequality](https://en.wikipedia.org/wiki/Cheeger_constant) (also search the web), [expander graphs](https://en.wikipedia.org/wiki/Expander_graph) and [Ramanujan graphs](https://en.wikipedia.org/wiki/Ramanujan_graph), which have "largest-possible" second eigenvalues, and generally convergence of random walks and Markov chains.


I guess you have something a little different here, because the graph changes every iteration, but it should give you plenty to read about!


