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)
PageRank Algorithm hypothesis , One user randomly jumps to another on the Internet page. He asked the user to eventually arrive at some page Probability .
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 .
We have the following digraph , Each node represents a page , Each directed edge represents from a page To another page Link to .
The first 0 Time to traverse the , In the first place , Users randomly access this 4 individual page Probability , Certainly 1/4.
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]
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]
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])
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 》