Eigenvalues of Random Walk Matrices

Let $G$ be an undirected graph. Last week, we saw the definitions of the following graphs:

  • Adjacency matrix $A$
  • Degree matrix $D$
  • Random walk matrix $W = A D^{-1}$

Today, we will focus on properties of the random walk matrix $W$, and play with some toy examples of graphs to develop an intuition for what the spectrum of $W$ tells us.

We would like to investigate the eigenvalues and eigenvectors of $W$. However, I've mentioned before that not all $n \times n$ matrices will have $n$ real eigenvalues. But if you try to compute the eigenvalues of $W$ for the graphs in last week's homework, you'll realize that they do have $n$ real eigenvalues.

This is not a coincidence! We didn't just happen to be lucky in our choice of graphs. The random walk matrix $W$ of any graph with $n$ vertices will always have $n$ real eigenvalues. (These eigenvalues may not be distinct: there could be repeated eigenvalues corresponding to different eigenvectors. But there will always be $n$ of them, with $n$ corresponding eigenvectors.)

To see why this is the case, let's recall a fact that I told you a while back: if $M$ is a symmetric $n \times n$ matrix, then $M$ has $n$ real eigenvalues.

Unfortunately, we can't apply this fact to our walk graph $W$, because $W$ is not symmetric. But there is a symmetric matrix that is closely related to $W$.

Question 1

Let $N = D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$. This is sometimes called the normalized adjacency matrix.

a) Show that $N$ is symmetric i.e. show that $N^\top = N$, where $N^\top$ is the transpose of $N$. You may use the fact that $A$ and $D$ are symmetric, and that $(XY)^\top = Y^\top X^\top$ for any two matrices $X$ and $Y$.

This implies that $N$ has $n$ real eigenvalues.

b) Show that $N$ and $W$ are similar i.e. show that there is an invertible matrix $P$ such that $N = P^{-1} W P$.

c) Combine all the facts you know so far to show that $W$ has $n$ real eigenvalues.

There is another matrix associated with the random walk matrix, known as the lazy walk matrix:

$$ \hat{W} := \frac{1}{2}I + \frac{1}{2} W. $$

The interpretation of this matrix is as follows: at every node, we flip a coin - if it's heads, we stay on that node (we're lazy to move), and if it's tails, we randomly walk along one of the edges.

d) We saw last week that $W$ has an eigenvalue of $1$ (with eigenvector $d$). In fact, all eigenvalues of $W$ lie between $-1$ and $1$. Use this fact to show that the eigenvalues of the lazy walk matrix $\hat{W}$ lie between $0$ and $1$.

e) Explain why the lazy walk matrix $\hat{W}$ has the same eigenvalues as $\hat{N} := \frac{1}{2}I + \frac{1}{2} N$.

We sometimes consider the lazy walk matrix $\hat{W}$ instead of $W$, if we don't want to have to deal with negative eigenvalues. There are also other variants of the lazy walk matrix, where we stay on a node with some other probability. In those cases, we may not always be able to guarantee that the eigenvalues are non-negative.

Question 2

This is a programming question. You will define a function that takes in an undirected graph $G$ and returns a list of the eigenvalues of the random walk matrix of $G$.

We will do this in a slightly roundabout fashion by defining some intermediate functions, using the things we've learned from Question 1 above, and last week's homework.

For everything below, assume that you've run the following code (the last line is just to make printing numbers a bit nicer).

In [ ]:
import networkx as nx
import numpy as np
np.set_printoptions(formatter={'float': lambda x: "{0:0.2f}".format(x)})

You may make use of the following functions:

  • len(G) returns the number of nodes in a graph $G$
  • nx.adjacency_matrix(G) returns the adjacency matrix $A$ of $G$
  • np.diag(d) returns a square matrix with the vector d along the diagonal and zeros elsewhere
  • np.eye(n) returns the $n \times n$ identity matrix
  • np.ones(n) returns an all-ones vector of dimension $n$
  • np.linalg.inv(M) returns the inverse of a matrix $M$
  • np.sqrt(x) returns the square-root of every element of $x$ (which could be a constant, a vector or a matrix)
  • np.eigvals(M) returns the eigenvalues of a matrix $M$ (not sorted)
  • np.eigvalsh(M) returns the eigenvalues of a symmetric matrix $M$, sorted from smallest to largest
  • Use @ for matrix multiplication and * to multiply every entry in the matrix by a constant

Note which functions use nx and which ones use np. Also note the last 'h' in np.eigvalsh.

For your convenience, you may test your functions on this graph $G$ from last week. Of course, you may also test them on other graphs that you have defined.

In [ ]:
G = nx.Graph([(1,2),(1,3),(2,4),(1,5), (2,3)])
nx.draw(G,  with_labels = True, node_color = 'white')

a) Write a function that takes a graph $G$ and returns the random walk matrix $W$. I've provided some guides for this first part. (Hint: look at Questions 1c and 2b from last week)

In [ ]:
# Random walk matrix of a graph G
def W(G):
    n = ??? # number of nodes
    A = ??? # adjacency matrix
    d = ??? # degree vector
    D = ??? # degree matrix
    return ???

b) Write a function that takes a graph $G$ and returns the lazy random walk matrix $\hat{W}$.

In [ ]:
# Lazy random walk matrix of a graph G
def W_lazy(G):
    ???
    return ???

c) Write a function that takes a graph $G$ and returns the matrix $N$.

In [ ]:
# Normalized adjacency matrix of a graph G
def N(G):
    ???
    return ???

d) Write a function that takes a graph $G$ and returns the matrix $\hat{N}$.

In [ ]:
# "Lazy" normalized adjacency matrix of a graph G
def N_lazy(G):
    ???
    return ???

e) Write two functions that take a graph $G$ and returns the eigenvalues of the lazy random walk matrix $\hat{W}$. The first function should use W_lazy(G) and np.eigenvals while the second function should use N_lazy(G) and np.eigenvalsh.

In [ ]:
def lazy_eigs_direct(G): # use W_lazy(G), which is NOT symmetric, and np.eigenvals
    ???
    return ???
In [ ]:
def lazy_eigs(G): # use N_lazy(G), which is symmetric, and np.eigenvalsh
    ???
    return ???

Test your two functions on graph G defined above, and verify that they do indeed produce the same list of eigenvalues, but possibly in a different order.

In [ ]:
lazy_eigs_direct(G)
In [ ]:
lazy_eigs(G)

Some examples of graphs

In this question, we will see some toy examples of graphs, and compute the eigenvalues of lazy walks on those graphs using lazy_eigs. All of these graphs will have $10$ nodes to allow them to be compared more directly, but the actual number of nodes isn't that important.

First, run the cells below to see what the graphs look like:

Path graph

In [ ]:
P = nx.path_graph(10)
nx.draw(P, with_labels = True, node_color = 'white')

Cycle graph

In [ ]:
C = nx.cycle_graph(10)
nx.draw(C, with_labels = True, node_color = 'white')

Star graph

In [ ]:
S = nx.star_graph(9) # nx.star_graph(n) returns a graph with n+1 nodes
nx.draw(S, with_labels = True, node_color = 'white')

Wheel graph

In [ ]:
Wh = nx.wheel_graph(10) # I'm calling this Wh because we already used W for the walk matrix
nx.draw(Wh, with_labels = True, node_color = 'white')

Complete graph

In [ ]:
K = nx.complete_graph(10)
nx.draw(K, with_labels = True, node_color = 'white')

Barbell graph

In [ ]:
# nx.barbell(m,n) returns a graph with two complete graphs on m-nodes, 
# connected by a path passing through n additional nodes
B = nx.barbell_graph(4,2)
nx.draw(B, with_labels = True, node_color = 'white')

Question 3

a) Look at the graphs above, and sort them from "least connected" to "most connected". There is no right or wrong answer for this question. I just want to see what your intuition is.

b) Add a line to the cells above to also print out lazy_eigs for each of these graphs. Are there any patterns you notice about the eigenvalues? Does anything seem to agree with your intuition on which is most or least connected?

(Make sure that you've run the following line of code, for nicer formatting of the printed eigenvalues)

In [ ]:
np.set_printoptions(formatter={'float': lambda x: "{0:0.2f}".format(x)})