Task 3.sagews

# Initialize the graph
G = DiGraph()
G.add_edges((
('A', 'D'), ('A', 'C'), ('N', 'A'), ('A', 'G'), ('D', 'B'), ('B', 'K'),
('K', 'D'), ('C', 'D'), ('C', 'E'), ('E', 'N'), ('N', 'G'), ('E', 'F'),
('E', 'H'), ('H', 'G'), ('F', 'I'), ('J', 'I'), ('M', 'F'), ('M', 'L'), ('L', 'M')))
E = G.edges()
V = G.vertices()

# The random walk procedure
# The walk is started from each vertex M times, moving N times during each walk
def walk_randomly(V, E, M, N):
    import random
    edges = {}
    for a, b, w in E:
        edges.setdefault(a, []).append(b)
    vertex_indices = {v: i for i, v in enumerate(V)}
    P = matrix(RR, len(V))
    for start_node in V:
        for j in range(M):
            current_node = start_node
            for i in range(N):
                P[vertex_indices[start_node], vertex_indices[current_node]] += 1
                if current_node in edges:
                    current_node = random.choice(edges[current_node])
    P /= M * N
    finishing_prob = P.numpy().mean(axis=0)
    finishing_prob = {V[i]: c for i, c in enumerate(finishing_prob)}
    return P, finishing_prob

# Find the number of times a vertex is visited during a random walk on the original graph
M = 100
N = 100
G_trans_matrix_rw, G_prob_rw = walk_randomly(V, E, M, N)

def add_labels(G, labels):
    return G.relabel({l: l + ' ' + str(c) for l, c in labels.items()}, inplace=False)

import numpy
numpy.set_printoptions(precision=3, suppress=True, linewidth=200)

prob_str = {u: "{:.1%}".format(c) for u, c in G_prob_rw.items()}
print sorted(prob_str.items())
print G_trans_matrix_rw.numpy()
H = add_labels(G, prob_str).plot()
H.show(figsize=10)

[('A', '0.1%'), ('B', '10.1%'), ('C', '0.1%'), ('D', '10.1%'), ('E', '0.1%'), ('F', '0.3%'), ('G', '28.6%'), ('H', '0.1%'), ('I', '39.8%'), ('J', '0.1%'), ('K', '10.1%'), ('L', '0.2%'), ('M', '0.2%'), ('N', '0.1%')] [[ 0.011 0.148 0.004 0.148 0.003 0.001 0.481 0.001 0.058 0. 0.147 0. 0. 0.001] [ 0. 0.34 0. 0.33 0. 0. 0. 0. 0. 0. 0.33 0. 0. 0. ] [ 0.001 0.158 0.01 0.158 0.006 0.003 0.252 0.001 0.252 0. 0.158 0. 0. 0.002] [ 0. 0.33 0. 0.34 0. 0. 0. 0. 0. 0. 0.33 0. 0. 0. ] [ 0.002 0.026 0. 0.026 0.01 0.003 0.568 0.003 0.333 0. 0.026 0. 0. 0.003] [ 0. 0. 0. 0. 0. 0.01 0. 0. 0.99 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0.99 0.01 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 0.99 0.01 0. 0. 0. 0. ] [ 0. 0.33 0. 0.33 0. 0. 0. 0. 0. 0. 0.34 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0.01 0. 0. 0.957 0. 0. 0.017 0.017 0. ] [ 0. 0. 0. 0. 0. 0.01 0. 0. 0.963 0. 0. 0.008 0.018 0. ] [ 0.005 0.081 0.002 0.082 0.001 0. 0.709 0. 0.029 0. 0.08 0. 0. 0.01 ]]

G2 = G.copy()
# Remove sinks by adding edges to them
G2.add_edges((
('K', 'C'), ('I', 'C'), ('G' 'C')
))
# Remove sources by adding edges to them
G2.add_edges((
('D', 'J'), ('D', 'L')
))

G2_trans_matrix_rw, G2_prob_rw = walk_randomly(G2.vertices(), G2.edges(),  M, N)

prob_str = {u: "{:.1%}".format(c) for u, c in G2_prob_rw.items()}
print sorted(prob_str.items())
print G2_trans_matrix_rw.numpy()
H = add_labels(G2, prob_str).plot()
H.show(figsize=10)

[('A', '1.6%'), ('B', '4.1%'), ('C', '18.9%'), ('D', '12.2%'), ('E', '9.3%'), ('F', '7.1%'), ('G', '5.3%'), ('H', '3.2%'), ('I', '11.2%'), ('J', '4.1%'), ('K', '4.1%'), ('L', '8.0%'), ('M', '7.9%'), ('N', '3.1%')] [[ 0.024 0.04 0.188 0.122 0.092 0.071 0.054 0.032 0.11 0.04 0.039 0.081 0.08 0.029] [ 0.015 0.051 0.185 0.124 0.09 0.071 0.05 0.031 0.107 0.039 0.051 0.08 0.079 0.029] [ 0.013 0.039 0.191 0.125 0.089 0.072 0.048 0.028 0.113 0.042 0.039 0.086 0.085 0.03 ] [ 0.014 0.044 0.187 0.128 0.093 0.07 0.05 0.029 0.113 0.044 0.044 0.078 0.077 0.03 ] [ 0.016 0.04 0.189 0.119 0.104 0.07 0.057 0.034 0.109 0.04 0.04 0.075 0.074 0.034] [ 0.014 0.041 0.192 0.12 0.093 0.078 0.052 0.034 0.116 0.038 0.041 0.077 0.076 0.027] [ 0.014 0.038 0.19 0.119 0.092 0.073 0.059 0.03 0.11 0.038 0.037 0.086 0.085 0.029] [ 0.016 0.042 0.191 0.121 0.094 0.068 0.061 0.041 0.106 0.039 0.041 0.074 0.073 0.031] [ 0.017 0.041 0.193 0.123 0.092 0.064 0.053 0.031 0.116 0.042 0.04 0.079 0.079 0.033] [ 0.014 0.041 0.193 0.121 0.097 0.065 0.057 0.034 0.115 0.052 0.041 0.07 0.069 0.032] [ 0.016 0.043 0.19 0.126 0.092 0.067 0.051 0.031 0.109 0.044 0.052 0.075 0.074 0.031] [ 0.015 0.041 0.185 0.118 0.09 0.076 0.047 0.028 0.114 0.04 0.04 0.088 0.087 0.03 ] [ 0.017 0.035 0.185 0.113 0.095 0.077 0.05 0.032 0.115 0.039 0.035 0.085 0.094 0.031] [ 0.02 0.037 0.188 0.123 0.089 0.069 0.056 0.031 0.11 0.042 0.037 0.08 0.079 0.039]]

def adj_to_transition_matrix(adj):
    trans = matrix(RR, adj.dimensions()[0])
    for i, row in enumerate(adj):
        out_degree = sum(row)
        if out_degree > 0:
            trans[i] = row / out_degree
        else:
            trans[i] = row
            trans[i, i] = 1
    return trans

G_adj = G.adjacency_matrix()
G2_adj = G2.adjacency_matrix()
G_trans = adj_to_transition_matrix(G_adj)
G2_trans = adj_to_transition_matrix(G2_adj)

from pylab import cm

print G_trans.numpy()
print
print G2_trans.numpy()
print

def plot_trans_matrix(A):
    A = A.numpy()
    A[A < 1e-3] = 0
    G_tmp = DiGraph(matrix(A), format='weighted_adjacency_matrix')
    G_tmp.relabel(V)
    E = G_tmp.edges()
    edge_colors = {}
    for e in E:
        c = cm.binary(e[2])[:3]
        edge_colors.setdefault(c, []).append(e)
    G_tmp.plot(layout='circular', edge_colors=edge_colors).show()

plot_trans_matrix(G_trans**1024)
print
for i in range(10):
    plot_trans_matrix(G_trans)
    G_trans *= G_trans

print
print (G_trans**1024).numpy()
print (G_trans**1024).numpy().mean(axis=0)
print
G2_trans **= 128
print G2_trans.numpy()
plot_trans_matrix(G2_trans)

[[ 0. 0. 0.333 0.333 0. 0. 0.333 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. ] [ 0. 0. 0. 0.5 0.5 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0.333 0. 0.333 0. 0. 0. 0. 0. 0.333] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. ] [ 0. 0. 0. 0. 0. 0.5 0. 0. 0. 0. 0. 0.5 0. 0. ] [ 0.5 0. 0. 0. 0. 0. 0.5 0. 0. 0. 0. 0. 0. 0. ]] [[ 0. 0. 0.333 0.333 0. 0. 0.333 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. ] [ 0. 0. 0. 0.5 0.5 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0.333 0. 0. 0. 0. 0. 0. 0. 0.333 0. 0.333 0. 0. ] [ 0. 0. 0. 0. 0. 0.333 0. 0.333 0. 0. 0. 0. 0. 0.333] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0. 0.5 0.5 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. ] [ 0. 0. 0. 0. 0. 0.5 0. 0. 0. 0. 0. 0.5 0. 0. ] [ 0.5 0. 0. 0. 0. 0. 0.5 0. 0. 0. 0. 0. 0. 0. ]]

[[ 0. 0.005 0. 0.333 0. 0. 0.429 0. 0.057 0. 0.176 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. ] [ 0. 0. 0. 0.528 0. 0. 0.286 0. 0.171 0. 0.015 0. 0. 0. ] [ 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0.056 0. 0.029 0. 0. 0.571 0. 0.343 0. 0.001 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. ] [ 0. 0.088 0. 0.002 0. 0. 0.714 0. 0.029 0. 0.167 0. 0. 0. ]] [ 0. 0.082 0. 0.135 0. 0. 0.286 0. 0.4 0. 0.097 0. 0. 0. ] [[ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032] [ 0.016 0.04 0.19 0.12 0.095 0.072 0.053 0.032 0.112 0.04 0.04 0.08 0.08 0.032]]