Algorithms For Dummies

Introducing boredom and teleporting

Both dead ends (rank sinks) and spider traps (cycles) are common situations on the 

web because of users’ choices and spammers’ actions. The problem, however, is 

easily solved by making the random surfer randomly jump to another network 

node (teleporting, as in the sci-fi devices that take you instantaneously from one 

place to another). The theory is that a surfer will get bored at one point or another 

and move away from deadlocking situations. Mathematically, you define an alpha 

value representing the probability of continuing the random journey on the graph 

by the surfer. The alpha value redistributes the probability of being on a node 

independently of the transition matrix.

The value originally suggested by Brin and Page for alpha (also called the damping 

factor) is 0.85, but you can change it according to your needs. For the web, it 

works the best between 0.8 and 0.9 and you can read why this is the best value 

range at 

https://www.cise.ufl.edu/~adobra/DaMn/talks/damn05-santini. 

pdf

. The smaller the alpha value, the shorter the trip of the surfer on the network, 

on average, before restarting somewhere else.

def PageRank_teleporting(graph, iters = 50, alpha=0.85,

                         rounding=3):

    G, p = initialize_PageRank(graph)

    u = np.ones(len(p)) / float(len(p))

    for i in range(iters):

        p = alpha * np.dot(G,p) 

+ (1.0 - alpha) * u

    return np.round(p / np.sum(p), rounding)

---

220

 

   

  PART 3