PageRank কী?
Google-এর প্রতিষ্ঠাতা ল্যারি পেজ ও সেরজি ব্রিন द्वारा বিকশিত অ্যালগরিদম যা ওয়েব পেজের গুরুত্ব নির্ণয় করে। ওয়েবকে ডirected গ্রাফ ধরে: নোড = পেজ, এজ = হাইপারলিংক। PageRank ভ্যালু ০ থেকে ১-এর মধ্যে একটি প্রোবাবিলিটি।
গাণিতিক সূত্র
PR(p) = (1-d)/N + d × Σ PR(q)/L(q)
d= ড্যাম্পিং ফ্যাক্টর (সাধারণত 0.85)N= মোট পেজ সংখ্যাq= p-কে লিংক করা পেজগুলোL(q)= q-থেকে আউটগোইং লিংক সংখ্যা
NumPy ব্যবহার করে ইমপ্লিমেন্টেশন
import numpy as np
from fractions import Fraction
def page_rank(adj_matrix, damping=0.85, max_iter=100, tol=1e-6):
"""
adj_matrix: NxN ম্যাট্রিক্স, adj[i][j] = 1 যদি j -> i লিংক থাকে
"""
N = adj_matrix.shape[0]
# ট্রানজিশন ম্যাট্রিক্স (কলাম-স্টোকাস্টিক)
out_degrees = adj_matrix.sum(axis=0)
out_degrees[out_degrees == 0] = 1 # ড্যাঙ্গলিং নোড হ্যান্ডলিং
M = adj_matrix / out_degrees
# গুগল ম্যাট্রিক্স
G = damping * M + (1 - damping) / N
# পাওয়ার ইটারেশন
r = np.ones(N) / N # ইউনিফর্ম ইনিশিয়ালাইজেশন
for i in range(max_iter):
r_new = G @ r
if np.linalg.norm(r_new - r, 1) < tol:
break
r = r_new
return r
# উদাহরণ: ৩ নোডের ছোট গ্রাফ
# 0 <- 2, 1 <- 0, 2 <- 0,1
adj = np.array([
[0, 0, 1], # 0-এ ২ থেকে লিংক
[0.5, 0, 0], # 1-এ ০ থেকে লিংক (০.৫ = ১/২)
[0.5, 1, 0] # 2-এ ০,১ থেকে লিংক
], dtype=float)
ranks = page_rank(adj)
print("PageRank scores:")
for i, rank in enumerate(ranks):
print(f"Page {i}: {rank:.4f}")
print(f"Sum: {ranks.sum():.6f}")
আউটপুট নমুনা
PageRank scores: Page 0: 0.3750 Page 1: 0.2310 Page 2: 0.3930 Sum: 0.999000
মূল কোড ব্যাখ্যা (মূল আর্টিকেল থেকে)
মূল কোডে Fraction ব্যবহার করা হয়েছে নির্ভুলতা জন্য, এবং beta=0.7 ড্যাম্পিং ফ্যাক্টর। কনভার্জেন্স চেক করা হয়েছে previous_r == r দিয়ে।
বাস্তব ব্যবহার
- NetworkX লাইব্রেরি:
nx.pagerank(graph) - বড় গ্রাফের জন্য sparse matrix (
scipy.sparse) ব্যবহার করুন। - পার্সোনালাইজড PageRank: টেলিকপোর্ট ভেক্টর কাস্টোমাইজ করুন।
