User - MathOverflow

Answer by douglas-klein for Eigenvector centrality

2010-08-17T17:46:10Z

The wikipedia article quoted by Jon Bannon mentions using the power-iteration method as readily applicable -- and this is in my experience (for connected graphs, with degrees <5)quite efficient, say starting with the vector with weight 1 for every site. And this wikipedia article mentions several other choices for measuring centrality, besides the "eigenvector centrality". But it does not mention some choices indicated in D. J. Klein, "Centrality Measure in Graphs", J. Math. Chem. 47 (2010) 1209-1223. There centrality measure is suggested to be related to choice of metric or semimetric D on the graph. A couple choices for D yield centrality measures very similar to common measures, and a new "resistive centrality" is noted to result in connection with the choice of D as the "resistance distance" metric.

Answer by douglas-klein for What is the probability that two random walkers will meet?

2010-08-17T17:18:29Z

First, if the walks are on a Cartesian grid, then there is a bipartitioning of the network into 2 subsets (say A & B) of sites each consisting of the neighbors of others. The 2 walkers then remain on different sets A & B if they start on different sets, so that the probability of meeting on the same site is 0 -- as already noted by D. Zare above. If a non-bipartite grid (say the triangular grid) is used for the random walk, then this qualification would not apply.

Second, in 1 dim starting on the same (say even) subset of sites, the pair of walkers is equivalent to a single walk taking steps of -2, 0, or +2 with respective probabilities 1/4, 1/2, 1/4 -- and the question devolves to whether this new single walk will ever hit the origin (given that the initial distance from the origin is even). Polya's proof tells us that this new walk will eventually hit the origin with ultimate certainty.

Third, in 2 dim starting on the same subset of sites, the pair of (original) walkers is equivalent to a single walk taking steps of appropriate sizes -- if the step for original walker 1 is s(1) & for original walker 2 is s(2), with joint probability (1/4)x(1/4), then the new walk takes a step S with a probability which is 1/16 times the number of (ordered) pairs s(1) & s(2) which add to give S. Again Polya's proof tells us that the ultimate probability of the new walk hitting the origin is 1.

In higher dimensions the probability again following Polya is strictly less than 1.

The whole idea is that Polya's proof is robust under certain modifications to the random walk. In 2-dim the walk can be modified to have different probabilities for horizontal & vertical steps -- or diagonal steps can also be allowed (though then the "parity" considerations do not apply). Polya's proof however fails if the walk is given an "inversion-nonsymmetric" bias, say with different probabilities in the east & west (or north & south) directions. It also seems to me that if the walk is on a fractal grid, that the certain return should be for dim less than or equal to 2, while uncertain return should apply for dim 2+eps for all eps>0. Questions of what happens with a Cartesian grid for which edges are randomly deleted (with some probability p) also seems interesting -- and I think has perhaps been considered in connection with "percolation theory".

Answer by douglas-klein for The middle eigenvalues of an undirected graph

2010-08-16T22:12:19Z

First, regarding the mathematics of the middle-eigenvalue problem there are results for the case of a graph G with just a single perfect matching, especially if also the graph is bipartite. See D. J. Klein & A. Misra, Croat. Chim. Acta 77 (2002) 179-191, where a transform (called "Kekulean") from an original G with a single perfect matching is made to another graph G' with signed edge weights such that the adjacency matrix A(G') is the inverse of the original A(G). Circumstances are identified where the signs on G' may be eliminated to leave an ordinary unsigned graph G" still with eigenvalues inverse to those of G. Further circumstances are found where G & G" are isomorphic. Techniques for dealing with maximum eigenvalues (of A(G') or A(G")) are used to give information on the "middle" eigenvalues (of A(G)).

Second, some comments might be made on the chemical context. The adjacency-matrix eigenvalues nearest 0 are much considered in chemistry, as they locate the electrons most easily excited and the eigenvalue difference for middle eigenvalues gives an appropriate measure of the energy needed for excitation. In more detail, the eigenvalues of the adjacency matrix provide crude (Huckel-theoretic) estimates of 1-electron energies for the pi-electrons of conjugated carbon networks -- the other electrons being for the most part more tightly bound. A full N-electron energy is then just a sum over 1-electron energies each multiplied by an occupation number n(e) for that eigenvalue e -- the occupation numbers taking values 0, 1, or 2 and summing to N. For an electrically neutral conjugated-carbon network (as is a common circumstance), the total number N of such electrons matches the number of sites. Then the most favored N-electron state for N=even has the N/2 largest eigenvalues e each with n(e)=2 and all other eigenvalues e' with n(e')=0. For odd N=2k+1, the k largest e have n(e)=2, the next lowest eigenvalue e' has n(e')=1, and the k remaining lower eigenvalues e" have n(e")=0. The gap of interest is the least energy difference between a level not doubly occupied and another not empty. [A point of potential confusion is that the 1-electron eigenvalues are proportional to the eigenvalues with a proportionality which is negative; then the favorable ("ground-state") circumstance of occupying the largest eigenvalues corresponds to occupying the lowest energy 1-electron levels.] From all this commentary it can be seen that for bipartite graphs the "middle" eigenvalues of interest are those nearest 0, while for nonbipartite graphs this is not necessarily so. The chemical graphs of interest for conjugated-carbon networks have vertices just of degrees 1, 2, or 3.

Answer by douglas-klein for Spectral graph theory: Interpretability of eigenvalues and -vectors

2010-08-16T18:55:42Z

Another amusing case is that of the truncated icosahedral graph (chemically referred to as Buckminsterfullerene when realized as a 60-atom carbon cluster). Here the second eigenvalue is 3-fold degnerate, and if x, y, z denote 3 real equi-norm orthogonal eigenvectors for this eigenvalue, then the 60 triples of corresponding components locate the vertices as embedded in Euclidean space so as to manifest the icosahedral symmetry. See: D. E. Manopolous & P. W. Fowler, J. Chem. Phys. 96 (1992) 7603-7615 . In fact, these authors go on to similarly treat other "fullerenes" (which are polyhedra with degree-3 vertices and faces which are either pentagons or hexagons). In general the requisite eigenvalues are not degenerate, but are those which have eigenvectors with components dividing the graph into exactly 2 connected regions of different signs for the components -- also some scaling of the components by appropriate fuctions of the different eigenvalues is used. There has been some further work on such ideas for other suitable graphs - for the non-regular case the Laplaian matrix might plausibly be preferred over the adjacency matrix.
What is going on can be intuitively "understood", best in terms of the Laplacian, which is a discrete analog of the classical Laplacian from analysis. For this classical Laplacian, eigenvectors correspond to standing waves with energy corresponding to the eigenvalue. The long wave-length waves which have a single internal node partition the region (i.e., the graph in our analogy) with the amplitudes giving the distances from the node.
There is also W. T. Tutte's "classic" scheme for "drawing" the Schlegel diagram of a polyhedral graph: Proc. London Math. Soc. 13 (1963) 743-767. For a more recent survey on "Bridges between Geometry and Graph Theory" see T. Pisanski & M. Randic, pages 174-194 in Geopmetry at Work, ed. C. A. Gorini (MAA, Wash. DC, 2000).