Page Rank

Page Rank It's the ranking algorithm of Google search .PageRank It's the founder of Google Larry Page Named .（ It's just a coincidence , Dare you shout Larry Rank）

Algorithm

PageRank Algorithm hypothesis , One user randomly jumps to another on the Internet page. He asked the user to eventually arrive at some page Probability .

Example

The best example I've found is this ：

PageRank Algorithm - Example(YouTube)

If you have problems with your network , I can't visit , No problem , I will explain in detail .

Explore

We have the following digraph , Each node represents a page , Each directed edge represents from a page To another page Link to .

Iteration 0

The first 0 Time to traverse the , In the first place , Users randomly access this 4 individual page Probability , Certainly 1/4.

Iteration 1

In a traverse 1, The user is traversing 0 On the basis of , Jump to another page.

Page A

about Page A, The only access to it is Page C. however Page C It also points to B and D, So from C set out , arrive A Is the probability that 1/3. And we did that before , Only 1/4 Of users visited C, Combination of the two , Namely 1/4*1/3=1/12 = 0.08333333333333333.

B

about B Come on , It's a little more complicated . Because there is A and C All point to B.

Let's just think about it first A->B, because A At the same time point to B and C, So from A set out , arrive B Is the probability that 1/2. consider Iteration 1 Of A Is the probability that 1/4. Then the user visits first A, Revisit B Is the probability that 1/2 * 1/4 = 1/8

Empathy , Users visit first C, Revisit B Is the probability that
1/3 * 1/4 = 1/12

Combined with the above , The user is in Iteration 1 when , arrive B Is the probability that
1/2 * 1/4 + 1/3 * 1/4 = 1/8 + 1/12 = 0.20833333333333334.

C

We use symbols to represent the above operations , Then there are ：

P(C|I1) = P(C|A) * P(A) + P(C|D) * P(D) = 1/2 * 1/4 + 1 * 1/4 = 1/8+1/4=4.5/12=0.375

D

P(D|I1) = P(D|B) * P(B) + P(D|C) * P = 1 * 1/4 + 1/3 * 1/4 = 1/4+1/12=4/12=0.3333333333333333

The final result is

[0.08333333333333333, 0.20833333333333334, 0.375, 0.3333333333333333]

Iteration 2

We're traversing 1 On the basis of , Computational ergodicity 2.

A

I1 Express Iteration 1, I2 Express Iteration 2.

P(A|I2) = P(C|A) * P(C|I1) = 1/3 * 4.5/12 = 1.5/12

B

P(B|I2) = P(B|A) * P(A|I1) + P(B|C) * P(C|I1) = 1/2 * 1/12 + 1/3 * 4.5/12= 2/12

C

P(C|I2) = P(C|A) * P(A|I1) + P(C|D) * P(D|I1) = 1/2 * 1/12 = 4.5/12

D

P(D|I2) = P(D|B) * P(B|I1) + P(D|C) * P(C|I1) = 1 * 2.5/12 + 1/3 * 4.5/12= 4/12

Traverse 2 The end result of :

[0.125, 0.16666666666666666, 0.375, 0.3333333333333333]

The final PageRank yes [1, 2, 4, 3]

Code

import numpy as np
n_iterations=3
n_nodes=4
#graph
graph = np.zeros((n_nodes, n_nodes))
#direction[start_node,end_node]=1
graph[0,1]=1
graph[0,2]=1
graph[1,3]=1
graph[2,0]=1
graph[2,1]=1
graph[2,3]=1
graph[3,2]=1
graph
#page rank matrix
pr_matrix = np.zeros((n_iterations, n_nodes))
#iteration 0
pr_matrix[0] = [1/n_nodes] * n_nodes
print('Page rank in Iteration 0')
print(pr_matrix[0])
#iteration 1,2
for i_iteration in [1,2]:
print(f'Page rank in Iteration {i_iteration}')
for node in range(n_nodes):
pr=0
for previous_node in range(n_nodes):
if graph[previous_node, node]==1:
pr+=pr_matrix[i_iteration-1,previous_node]/graph[previous_node, :].sum()
pr_matrix[i_iteration, node] = pr
print(pr_matrix[i_iteration])

Source code Github Address

Welcome to other articles in this series ：

《python Machine learning handwriting algorithm series ——PageRank Algorithm 》

《python Machine learning handwriting algorithm series —— Linear regression 》

《python Machine learning handwriting algorithm series —— Logical regression 》

《python Machine learning handwriting algorithm series —— Decision tree 》

《python Machine learning handwriting algorithm series ——kmeans clustering 》

《python Machine learning handwriting algorithm series —— Gradient rise GBDT Return to 》

《python Machine learning handwriting algorithm series —— Gradient rise GBDT classification 》