อัลกอริทึม PageRank และการนำไปใช้ด้วย Python

อัลกอริทึม PageRank ใช้กับหน้าเว็บ หน้าเว็บเป็น directed graph โหนดคือหน้าเว็บ ขอบคือ hyperlink สามารถหาความสำคัญของแต่ละหน้าได้จาก PageRank ค่าจะอยู่ระหว่าง 0 ถึง 1

ค่า PageRank ของโหนดขึ้นอยู่กับค่า PageRank ของโหนดที่ลิงก์มาหา และโหนดเหล่านั้นเชื่อมต่อแบบวนรอบ ใช้ iterative converging method กำหนดค่า

โค้ดตัวอย่าง: PageRank แบบเมทริกซ์

import numpy as np
import scipy as sp
import pandas as pd
from fractions import Fraction

def display_format(my_vector, my_decimal):
    return np.round((my_vector).astype(np.float), decimals=my_decimal)

# Transition matrix (3 หน้าเว็บ)
my_dp = Fraction(1, 3)
Mat = np.matrix([
    [0, 0, 1],
    [Fraction(1,2), 0, 0],
    [Fraction(1,2), 1, 0]
])

# Teleportation matrix (random surfer)
Ex = np.zeros((3, 3))
Ex[:] = my_dp

beta = 0.7  # damping factor
Al = beta * Mat + ((1 - beta) * Ex)

# Initial rank vector
r = np.matrix([my_dp, my_dp, my_dp])
r = np.transpose(r)
previous_r = r

for i in range(1, 100):
    r = Al * r
    print(display_format(r, 3))
    if (previous_r == r).all():
        break
    previous_r = r

print("Final:\n", display_format(r, 3))
print("Sum:", np.sum(r))

ผลลัพธ์ (บางส่วน)

[[0.333] [0.217] [0.45 ]]
[[0.415] [0.217] [0.368]]
[[0.358] [0.245] [0.397]]
...
[[0.375] [0.231] [0.393]]  ← 收敛
Final:
 [[0.375] [0.231] [0.393]]
Sum: 0.9999999999999951

คำอธิบาย

• Mat - เมทริกซ์การเชื่อมต่อ (adjacency matrix แบบ normalize)
• Ex - เมทริกซ์ teleportation (โอกาสสุ่มกระโดดไปหน้าไหนก็ได้)
• beta (damping factor) - โอกาสที่ user ตามลิงก์ (ปกติ 0.85)
• Al - Google Matrix = beta * Mat + (1-beta) * Ex
• r - PageRank vector เริ่มต้น uniform distribution
• Iterate: r = Al * r จน converge

การใช้ NetworkX (ทางเลือกที่ง่ายกว่า)

import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(0, 2), (1, 0), (2, 0), (2, 1)])
pagerank = nx.pagerank(G, alpha=0.7)
print(pagerank)
# {0: 0.375, 1: 0.231, 2: 0.393}

ประยุกต์ใช้: Search engine ranking, Social network analysis, Recommendation systems