Graph eigenvalues and connectivity
Keith Briggs
[Link]@[Link]
[Link]
2003 July 07 1500
typeset 2003 July 8 9:13 in pdfLATEX on a linux system
Graph eigenvalues and connectivity 1 of 11
Adjacency matrix
Let Γ be an arbitrary graph with n nodes
Let A be the adjacency matrix of Γ
Example:
0 1 0 0
3 4
1 0 1 1
A= 0 1 0 0
0 1 0 0
Keith Briggs Graph eigenvalues and connectivity 2 of 11
Determining connectivity
Let B be the adjacency matrix with all zeroes replaced by ∞
• for k = 1, . . . , n
• for i = 1, . . . , n
• for j = i+1, . . . , n
• bij = min(bik +bkj , bij )
The graph is connected iff all elements bij (i 6= j) are < ∞
We would like to use this for very large graphs, but it takes
time O(n3) and space O(n2)!
Keith Briggs Graph eigenvalues and connectivity 3 of 11
Graph eigenvalues
Let Γ be an arbitrary graph with n nodes
Let A be the adjacency matrix of Γ
Let ∆ be the diagonal matrix with ∆ii the degree of node i
Let Q ≡ ∆−A be the Laplacian matrix
Let J be the matrix of all ones
Then the number of spanning trees of Γ is κ = det (J +Q)/n2
Let the spectrum of Q be 0 = µ0 6 µ1 6 µ2 6 · · · 6 µn−1
Qn−1
Then we also have nκ = i=1 µi
Thus Γ is connected iff µ1 > 0
Keith Briggs Graph eigenvalues and connectivity 4 of 11
Example 1
1 1 −1 0 0
−1 2 −1 0
Q = 0 −1 2 −1
0 0 −1 1
2
det(J +Q) = 16
3
µ = [0, 0.5858, 2, 3.4142]
4 κ = 1 from determinant formula
κ = 1 from eigenvalue formula
Keith Briggs Graph eigenvalues and connectivity 5 of 11
Example 2
1 −1 0 0
−1 1 0 0
1 3 Q= 0 0 1 −1
0 0 −1 1
det(J +Q) = 0
µ = [0, 0, 2, 2]
2 4
κ = 0 from determinant formula
κ = 0 from eigenvalue formula
Keith Briggs Graph eigenvalues and connectivity 6 of 11
Example 3
1
1 −1 0 0
−1 3 −1 −1
Q = 0 −1 1 0
0 −1 0 1
2
det(J +Q) = 16
µ = [0, 1, 1, 4]
3 4 κ = 1 from determinant formula
κ = 1 from eigenvalue formula
Keith Briggs Graph eigenvalues and connectivity 7 of 11
Example 4
1
2 −1 0 −1
−1 2 −1 0
Q = 0 −1 2 −1
2
−1 0 −1 2
det(J +Q) = 64
3
µ = [0, 2, 2, 4]
4 κ = 4 from determinant formula
κ = 4 from eigenvalue formula
Keith Briggs Graph eigenvalues and connectivity 8 of 11
My new idea! (2003 July 02)
If µ1 > 0, the graph is connected, so we need to find only the
two smallest eigenvalues, and bound µ1 away from zero
We can find the two smallest eigenvalues by an inverse QR
iteration method: let there be n nodes, let Y0 by an n×2
matrix with a 2×2 identity matrix at the top, then iterate for
k = 1, 2, 3, . . .
• QZ = Yk−1 (solve for Z )
• Zk = Yk Rk (QR factorization)
this should work because:
• we can use a sparse representation for Q, and solve for Z with a sparse iterative
technique [see references];
• the QR factorization will be very fast for a 2-column matrix
thus, the element R22 will converge to the desired µ1
Keith Briggs Graph eigenvalues and connectivity 9 of 11
Problems!
Q is singular. But we can instead use Q0 = J +Q, where J is a
matrix of all ones. The eigenvalues of Q0 are n, µ1, µ2, . . . , so
we now have: G is connected iff Q0 is nonsingular
Equivalently, G is connected iff Q0 is positive definite.
Inverse QR now works, but probably better methods are avail-
able:
• Lanczos iteration (tridiagonalization)
• Arnoldi iteration (ARPACK++)
• SuperLU
the space requirement is now O(n)
the time requirement is now O(n2) ?
challenge:
what is the fastest way to determine whether Q0 is singular?
Keith Briggs Graph eigenvalues and connectivity 10 of 11
References
N. Biggs, Algebraic graph theory, CUP 1993
B. Bollobás, Modern graph theory, Springer-Verlag 2002
R. Diestel, Graph theory, Springer-Verlag 2000
sparse-blas: [Link]
sparse 1.3: [Link]
other sparse codes: [Link]
D2a4/
Keith Briggs Graph eigenvalues and connectivity 11 of 11