For a diagonalizable matrix A, we have C−1AC=D. Then we have A=CDC−1
We have A2=CDC−1CDC−1=CD2C−1An=CDC−1…CDC−1=CDnC−1.
Because the columns of C are eigenvectors, so we can say that the eigenvectors for A and An are the same if A is diagonalizable.
If x is an eigenvector of A with the corresponding eigenvalue λ, then x is also an eigenvector of An with the corresponding eigenvalue λn.
Login with LibreOne to run this code cell interactively.
If you have already signed in, please refresh the page.
# Here are some libraries you may need to use
%matplotlib inline
import numpy as np
import sympy as sym
import networkx as nx
import matplotlib.pyplot as plt
from urllib.request import urlretrieve
sym.init_printing(use_unicode=True)
urlretrieve('https://raw.githubusercontent.com/colbrydi/jupytercheck/master/answercheck.py',
'answercheck.py');
# Here are some libraries you may need to use
%matplotlib inline
import numpy as np
import sympy as sym
import networkx as nx
import matplotlib.pyplot as plt
from urllib.request import urlretrieve
sym.init_printing(use_unicode=True)
urlretrieve('https://raw.githubusercontent.com/colbrydi/jupytercheck/master/answercheck.py',
'answercheck.py');
Graph Random Walk
Define the following matrices:
I is the identity matrix
A is the adjacency matrix
D is diagonal matrix of degrees (number of edges connected to each node)
W=12(I+AD−1)
The lazy random walk matrix, W, takes a distribution vector of stuff, pt, and diffuses it to its neighbors:
pt+1=Wpt
For some initial distribution of stuff, p0, we can compute how much of it would be at each node at time, t, by powering W as follows:
pt=Wtp0
Plugging in the above expression yields:
pt=(12(I+AD−1))tp0
Do This
Using matrix algebra, show that 12(I+AD−1) is similar to I−12N, where N=D−12(D−A)D−12 is the normalized graph Laplacian.
Random Walk on Barbell Graph
To generate the barbell graph, run the following cell.
Login with LibreOne to run this code cell interactively.
If you have already signed in, please refresh the page.
n = 60 # number of nodes
B = nx.Graph() # initialize graph
## initialize empty edge lists
edge_list_complete_1 = []
edge_list_complete_2 = []
edge_list_path = []
## generate node lists
node_list_complete_1 = np.arange(int(n/3))
node_list_complete_2 = np.arange(int(2*n/3),n)
node_list_path = np.arange(int(n/3)-1,int(2*n/3))
## generate edge sets for barbell graph
for u in node_list_complete_1:
for v in np.arange(u+1,int(n/3)):
edge_list_complete_1.append((u,v))
for u in node_list_complete_2:
for v in np.arange(u+1,n):
edge_list_complete_2.append((u,v))
for u in node_list_path:
edge_list_path.append((u,u+1))
# G.remove_edges_from([(3,0),(5,7),(0,7),(3,5)])
## add edges
B.add_edges_from(edge_list_complete_1)
B.add_edges_from(edge_list_complete_2)
B.add_edges_from(edge_list_path)
## draw graph
pos=nx.spring_layout(B) # positions for all nodes
### nodes
nx.draw_networkx_nodes(B,pos,
nodelist=list(node_list_complete_1),
node_color='c',
node_size=400,
alpha=0.8)
nx.draw_networkx_nodes(B,pos,
nodelist=list(node_list_path),
node_color='g',
node_size=200,
alpha=0.8)
nx.draw_networkx_nodes(B,pos,
nodelist=list(node_list_complete_2),
node_color='b',
node_size=400,
alpha=0.8)
### edges
nx.draw_networkx_edges(B,pos,
edgelist=edge_list_complete_1,
width=2,alpha=0.5,edge_color='c')
nx.draw_networkx_edges(B,pos,
edgelist=edge_list_path,
width=3,alpha=0.5,edge_color='g')
nx.draw_networkx_edges(B,pos,
edgelist=edge_list_complete_2,
width=2,alpha=0.5,edge_color='b')
plt.axis('off')
plt.show() # display
n = 60 # number of nodes
B = nx.Graph() # initialize graph
## initialize empty edge lists
edge_list_complete_1 = []
edge_list_complete_2 = []
edge_list_path = []
## generate node lists
node_list_complete_1 = np.arange(int(n/3))
node_list_complete_2 = np.arange(int(2*n/3),n)
node_list_path = np.arange(int(n/3)-1,int(2*n/3))
## generate edge sets for barbell graph
for u in node_list_complete_1:
for v in np.arange(u+1,int(n/3)):
edge_list_complete_1.append((u,v))
for u in node_list_complete_2:
for v in np.arange(u+1,n):
edge_list_complete_2.append((u,v))
for u in node_list_path:
edge_list_path.append((u,u+1))
# G.remove_edges_from([(3,0),(5,7),(0,7),(3,5)])
## add edges
B.add_edges_from(edge_list_complete_1)
B.add_edges_from(edge_list_complete_2)
B.add_edges_from(edge_list_path)
## draw graph
pos=nx.spring_layout(B) # positions for all nodes
### nodes
nx.draw_networkx_nodes(B,pos,
nodelist=list(node_list_complete_1),
node_color='c',
node_size=400,
alpha=0.8)
nx.draw_networkx_nodes(B,pos,
nodelist=list(node_list_path),
node_color='g',
node_size=200,
alpha=0.8)
nx.draw_networkx_nodes(B,pos,
nodelist=list(node_list_complete_2),
node_color='b',
node_size=400,
alpha=0.8)
### edges
nx.draw_networkx_edges(B,pos,
edgelist=edge_list_complete_1,
width=2,alpha=0.5,edge_color='c')
nx.draw_networkx_edges(B,pos,
edgelist=edge_list_path,
width=3,alpha=0.5,edge_color='g')
nx.draw_networkx_edges(B,pos,
edgelist=edge_list_complete_2,
width=2,alpha=0.5,edge_color='b')
plt.axis('off')
plt.show() # display
Do This
Generate the lazy random walk matrix, W, for the above graph.
Login with LibreOne to run this code cell interactively.
If you have already signed in, please refresh the page.
A = nx.adjacency_matrix(B)
A = A.todense()
d = np.sum(A,0) # Make a vector of the sums.
D = np.diag(np.asarray(d)[0])
A = nx.adjacency_matrix(B)
A = A.todense()
d = np.sum(A,0) # Make a vector of the sums.
D = np.diag(np.asarray(d)[0])
Login with LibreOne to run this code cell interactively.
If you have already signed in, please refresh the page.
#Put your answer to the above question here.
#Put your answer to the above question here.
Login with LibreOne to run this code cell interactively.
If you have already signed in, please refresh the page.
from answercheck import checkanswer
checkanswer.matrix(W, "7af4a5b11892da6e1a605c8239b62093")
from answercheck import checkanswer
checkanswer.matrix(W, "7af4a5b11892da6e1a605c8239b62093")
Do This
Compute the eigenvalues and eigenvectors of W. Make a diagonal matrix J with the eigenvalues on the diagonal. Name the matrix of eigenvectors V (each column is an eigenvector).
Login with LibreOne to run this code cell interactively.
If you have already signed in, please refresh the page.
#Put your answer to the above question here.
#Put your answer to the above question here.
Now we make sure we constructed V and A correctly by double checking that W=VJV−1
Login with LibreOne to run this code cell interactively.
If you have already signed in, please refresh the page.
np.allclose(W, V*J*np.linalg.inv(V))
np.allclose(W, V*J*np.linalg.inv(V))
Do This
Let your p0=[1,0,0,…,0]. Compute pt for t=1,2,…,100, and plot ||v1−pt||1 versus t, where v1 is the eigenvector associated with the largest eigenvalue λ1=1 and whose sum equals 1. (Note: ||⋅||1 may be computed using np.linalg.norm(v_1-p_t, 1).)
Login with LibreOne to run this code cell interactively.
If you have already signed in, please refresh the page.
#Put your answer to the above question here.
#Put your answer to the above question here.
Compare to Complete Graph
If you complete the above, do the same for a complete graph on the same number of nodes.
Question
What do you notice about the graph that is different from that above?