30.3: El poder de una matriz

• Para una matriz diagonalizable\(A\), tenemos\(C^{-1}AC = D\). Entonces tenemos\(A = CDC^{-1}\)
• Nosotros tenemos\(A^2 = CDC^{-1}CDC^{-1} = CD^{2}C^{-1}A^{n} = CDC^{-1} \ldots CDC^{-1} = CD^{n}C^{-1}\).
• Porque las columnas de\(C\) son vectores propios, entonces podemos decir que los vectores propios para\(A\) y\(A^n\) son los mismos si\(A\) es diagonalizable.
• Si\(x\) es un vector propio de\(A\) con el valor propio correspondiente\(\lambda\), entonces también\(x\) es un vector propio de\(A^n\) con el valor propio correspondiente\(\lambda^n\).

# 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');

Gráfica Caminata Aleatoria

• Defina las siguientes matrices:
  • \(I\)es la matriz de identidad
  • \(A\)es la matriz de adyacencia
  • \(D\)es una matriz diagonal de grados (número de aristas conectadas a cada nodo)

\[W=\frac{1}{2}(I + AD^{-1}) \nonumber \]

• La matriz de caminata aleatoria perezosa\(W\),, toma un vector de distribución de cosas\(p_t\), y lo difunde a sus vecinos:

\[p_{t+1}=Wp_{t} \nonumber \]

• Para alguna distribución inicial de cosas\(p_0\),, podemos calcular cuánto estaría en cada nodo a la vez,\(t\), alimentando de la\(W\) siguiente manera:

\[p_{t}=W^{t}p_{0} \nonumber \]

• Al enchufar la expresión anterior se obtiene:

\[p_{t}=\left( \frac{1}{2}(I+AD^{-1}) \right)^t p_{0} \nonumber \]

Hacer esto

Utilizando álgebra matricial, mostrar que\(\frac{1}{2}(I + AD^{-1})\) es similar a\(I-\frac{1}{2}N\), donde\(N=D^{-\frac{1}{2}}(D-A)D^{-\frac{1}{2}}\) está la gráfica normalizada Laplaciana.

Gráfico de Caminata Aleatoria sobre Barbell

Para generar el gráfico de barra, ejecute la siguiente celda.

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

Hacer esto

Generar la matriz de caminata aleatoria perezosa\(W\),, para la gráfica anterior.

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])

#Put your answer to the above question here.

from answercheck import checkanswer
checkanswer.matrix(W, "7af4a5b11892da6e1a605c8239b62093")

Hacer esto

Calcular los valores propios y vectores propios de\(W\). Hacer una matriz diagonal\(J\) con los valores propios en la diagonal. Nombra la matriz de vectores propios\(V\) (cada columna es un vector propio).

#Put your answer to the above question here. 

Ahora nos aseguramos de que construimos\(V\) y\(A\) correctamente comprobando que\(W = VJV^{-1}\)

np.allclose(W, V*J*np.linalg.inv(V))

Hacer esto

Deja que tu\(p_0 = [1,0,0, \ldots, 0]\). Calcular\(p_t\) para\(t = 1,2,\ldots,100\), y trazar\(||v_1 - p_t||_1\) versus\(t\), donde\(v_1\) está el vector propio asociado con el valor propio más grande\(\lambda_1 = 1\) y cuya suma es igual a 1. (Nota:\(||\cdot||_1\) puede calcularse usando np.linalg.norm (v_1-p_t, 1).)

#Put your answer to the above question here. 

Comparar con Gráfica Completa

Si completa lo anterior, haga lo mismo para una gráfica completa en el mismo número de nodos.

Pregunta

¿Qué notas de la gráfica que es diferente de la anterior?