Random Surfer Demos

In [6]:
# Standard Imports
import numpy as np
from numpy.random import rand, randint, choice
from scipy.sparse import coo_matrix, dok_matrix, find
from copy import deepcopy
import matplotlib.pyplot as plt
%matplotlib inline

The Web

In [7]:
plt.imshow(plt.imread('figures/web1.png'))
plt.axis('off');
In [8]:
# Make initial graph from Lecture
G = dok_matrix((12,12), dtype=np.float32)
G[8,0] = 1 # link from 0 to 8
G[5,0] = 1
G[6,1] = 1 
G[3,2] = 1
G[5,2] = 1
G[6,2] = 1
G[7,3] = 1 # consider changing G[7,3] to G[7,1] = 1
G[10,3] = 1
G[11,3] = 1
G[3,4] = 1
G[6,4] = 1
G[3,5] = 1 # change to 0 for terminal branch [cycle]
G[8,5] = 1
G[2,6] = 1
G[3,6] = 1
G[5,7] = 1
G[10,7] = 1
G[0,8] = 1
G[9,8] = 1
G[0,9] = 1
G[3,10] = 1
G[11,10] = 1
G[4,11] = 1
In [9]:
G.toarray()
Out[9]:
array([[0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 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., 1., 0., 1., 1., 1., 0., 0., 0., 1., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1.],
       [1., 0., 1., 0., 0., 0., 0., 1., 0., 0., 0., 0.],
       [0., 1., 1., 0., 1., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0.],
       [1., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0.],
       [0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 0.],
       [0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 1., 0.]], dtype=float32)

Random Surfer Method

In [10]:
N = np.shape(G)[0]
visits = np.zeros(N)

j = randint(N)  # choose a page to start

for t in range(10000):
    visits[j] += 1   # Increment page count
    outLinks = find(G[:,j]==1)[0]
    if len(outLinks)>0:
        j = choice(outLinks)  # Choose another outlink
    
plt.stem(visits);
plt.xlabel('We Page')
plt.ylabel('Number of Visits');
In [11]:
# RandyA
def RandyA(G, numSteps=10000):
    N = np.shape(G)[0]  # number of nodes
    visits = np.zeros(N)

    j = randint(N)

    for t in range(numSteps):
        visits[j] += 1
        outLinks = find(G[:,j]==1)[0]

        # Test for random teleportation
        if len(outLinks)!=0:
            # Follow an outlink
            j = choice(outLinks)
    return visits
In [12]:
v1 = RandyA(G, numSteps=1000)
plt.figure(figsize=[14,4])
plt.subplot(1,2,1); plt.stem(v1);
plt.subplot(1,2,2); plt.imshow(plt.imread('figures/web1.png')); plt.axis('off');
In [13]:
G[7,1] = 1  # Creates a terminal node
G[7,3] = 0
v2 = RandyA(G, numSteps=1000)
plt.figure(figsize=[14,4])
plt.subplot(1,2,1); plt.stem(v2);
plt.subplot(1,2,2); plt.imshow(plt.imread('figures/web2.png')); plt.axis('off');
print(v1[7], v2[7])

72.0 1.0
In [14]:
G[7,1] = 0; G[7,3] = 1;
G[0,9] = 0  # Creates a terminal node
v3 = RandyA(G, numSteps=1000)
plt.figure(figsize=[14,4])
plt.subplot(1,2,1); plt.stem(v3);
plt.subplot(1,2,2); plt.imshow(plt.imread('figures/web3.png')); plt.axis('off');

Teleport out of terminal nodes

In [15]:
# RandyB
def RandyB(G, numSteps=10000):
    N = np.shape(G)[0]  # number of nodes
    visits = np.zeros(N)

    j = randint(N)
    teleCount = 0  # for counting teleportations
    
    for t in range(numSteps):
        visits[j] += 1
        outLinks = find(G[:,j]==1)[0]
        numOutLinks = len(outLinks)

        # Test for random teleportation
        if numOutLinks!=0:
            # Follow an outlink
            j = outLinks[randint(numOutLinks)]
        else:
            # Teleport
            j = randint(N)
            teleCount += 1
    print('Teleported '+str(teleCount)+' times')    
    return visits
In [16]:
v3B = RandyB(G, numSteps=1000)
plt.figure(figsize=(12,4))
plt.subplot(1,2,1); plt.stem(v3); plt.title('RandyA');
plt.subplot(1,2,2); plt.stem(v3B); plt.title('RandyB');

Teleported 36 times
In [17]:
G[0,9] = 1
G[5,0] = 0
v4 = RandyB(G, numSteps=1000)
plt.figure(figsize=[14,4])
plt.subplot(1,2,1); plt.stem(v4);
plt.subplot(1,2,2); plt.imshow(plt.imread('figures/web4.png'));
plt.axis('off');

Teleported 0 times

Teleport randomly

In [18]:
# RandyC
def RandyC(G, numSteps=10000, alpha=0.85):
    N = np.shape(G)[0]  # number of nodes
    visits = np.zeros(N)

    j = randint(N)
    teleCount = 0  # for counting teleportations
    
    for t in range(numSteps):
        visits[j] += 1
        outLinks = find(G[:,j]==1)[0]
        numOutLinks = len(outLinks)

        # Test for random teleportation
        if rand()<alpha:
            # No random teleportation
            if numOutLinks!=0:
                # Follow an outlink
                j = outLinks[randint(numOutLinks)]
            else:
                # Teleport
                j = randint(N)
                teleCount += 1  
        else:
            # Random teleport
            j = randint(N)
            teleCount += 1
    print('Teleported '+str(teleCount)+' times')    
    return visits
In [19]:
v4C = RandyC(G, numSteps=10000, alpha=0.85)
plt.figure(figsize=(12,4))
plt.subplot(1,2,1); plt.stem(v4); plt.title('RandyB');
plt.subplot(1,2,2); plt.stem(v4C); plt.title('RandyC');

Teleported 1499 times

Markov Transition Matrix

In [20]:
G[5,0] = 1
D = deepcopy(G)
deg = np.sum(G, axis=0)
for c in range(N):
    for r in range(N):
        D[r,c] /= deg[0,c]
In [21]:
P = G @ D

x = np.ones(N) / N   # uniform distribution
x = np.random.rand(N)
x /= np.sum(x)
for n in range(20):
    plt.plot(x)
    x = P @ x
    x /= np.sum(x)
plt.plot(x, 'o');
In [ ]: