PAGERANK: خوارزمية الترتيب لصفحات الويب

لذلك ، ضع في اعتبارك الرسم البياني الموزون الموجه. دع الرسم له رؤوس n. كل زوج من القمم يتوافق مع بعض الوزن (احتمال الانتقال).







وتجدر الإشارة إلى أن الرسوم البيانية النموذجية للويب عبارة عن سلسلة Markov منفصلة متجانسة يتم استيفاء شرط عدم القابلية للتحلل وحالة عدم الانتظام.



لنكتب معادلة Kolmogorov-Chapman:







حيث P هي مصفوفة الانتقال.



افترض أن هناك حدًا يسمى







المتجه v توزيع الاحتمال الثابت.



من العلاقة (2) تم اقتراح البحث عن متجه الترتيب لصفحات الويب في نموذج برين بيج.



نظرًا لأن v حد ،







يمكن حساب التوزيع الثابت بطريقة التكرارات البسيطة (MPI).







من أجل الانتقال من صفحة ويب إلى أخرى ، يجب على المستخدم ، مع وجود احتمال معين ، اختيار الرابط الذي يريد الانتقال إليه. إذا كان المستند يحتوي على عدة روابط صادرة ، فسنفترض أن المستخدم ينقر على كل منها بنفس الاحتمال. وأخيرًا ، هناك أيضًا معامل النقل الآني ، والذي يوضح لنا أنه مع وجود بعض الاحتمالات يمكن للمستخدم الانتقال من المستند الحالي إلى صفحة أخرى ، وليس بالضرورة أن يكون مرتبطًا بشكل مباشر بالصفحة التي نحن فيها في الوقت الحالي. اسمح للمستخدم بالانتقال الفوري مع الاحتمال δ ، ثم تأخذ المعادلة (1) الشكل







بالنسبة لـ 0 <δ <1 ، فإن المعادلة مضمونة للحصول على حل فريد. في الممارسة العملية ، عادة ما تستخدم معادلة مع δ = 0.15 لحساب PageRank.



النظر في الرسم البياني للويب Google من رابط الموقع. يحتوي مخطط الويب هذا على 875713 رأسًا ، مما يعني أنه بالنسبة لمصفوفة ثنائية الأبعاد P ، تحتاج إلى تخصيص 714 جيجا بايت من الذاكرة. تعد ذاكرة الوصول العشوائي (RAM) الخاصة بأجهزة الكمبيوتر الحديثة مرتبة أقل من حيث الحجم ، لذلك يبدأ الكمبيوتر في استخدام ذاكرة القرص الصلب ، مما يؤدي إلى إبطاء عمل برنامج حساب PageRank بشكل كبير. لكن المصفوفة P عبارة عن مصفوفة متفرقة - مصفوفة تتكون في الغالب من صفر من العناصر. للعمل مع المصفوفات المتفرقة في Python ، يتم استخدام الوحدة النمطية المتفرقة من مكتبة scipy ، مما يساعد المصفوفة P على شغل ذاكرة أقل بكثير.







دعونا نطبق هذه الخوارزمية على هذه البيانات. تمثل العقد صفحات الويب ، والحواف الموجهة عبارة عن ارتباطات تشعبية بينها.



أولاً ، دعنا نستورد المكتبات التي نحتاجها:

import cvxpy as cp
import numpy as np
import pandas as pd
import time
import numpy.linalg as ln
from scipy.sparse import csr_matrix
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

الآن دعنا ننتقل إلى التنفيذ نفسه:

#   
data = pd.read_csv("web-Google.txt", names = ['i','j'], sep="\t", header=None)
NODES = 916428
EDGES = 5105039
#  
NEW = csr_matrix((np.ones(len(data['i'])),(data['i'],data['j'])),shape=(NODES,NODES))
b = NEW.sum(axis=1)
NEW = NEW.transpose()
# 
p0 = np.ones((NODES,1))/NODES
eps = 10**-5
delta = 0.15 
ERROR = True
k = 0
# 
while (ERROR == True):
    with np.errstate(divide='ignore'): 
             z = p0 / b
    p1 = (1-delta) * NEW.dot(csr_matrix(z)) + delta * np.ones((NODES,1))/NODES
    if (ln.norm(p1-p0) < eps):
        ERROR = False
    k = k + 1
#   PageRank
    p0 = p1 
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

في الرسوم البيانية ، يمكننا أن نرى كيف يصل المتجه p إلى حالة ثابتة v :







باستخدام متجه PageRank ، يمكنك أيضًا تحديد الفائز في الانتخابات. مجموعة فرعية صغيرة من المساهمين في ويكيبيديا هم المسؤولون ، وهم مستخدمون يتمتعون بإمكانية الوصول إلى ميزات تقنية إضافية للمساعدة في الصيانة. لكي يصبح المستخدم مسؤولاً ، يتم إصدار طلب مسؤول ، ويقرر مجتمع Wikipedia ، من خلال التعليق العام أو التصويت ، من الذي يجب ترقيته إلى منصب المسؤول.



يمكن أيضًا تقليل مشكلة PageRank إلى مشكلة تصغير وحلها باستخدام طريقة التدرج الشرطي لـ Frank-Wolfe ، والتي تتكون مما يلي: حدد أحد رؤوس البسيط وقم بعمل نقطة بداية عند هذا الرأس. تنفيذ هذه الطريقة على البيانات - الرابط أدناه:

#   
data = pd.read_csv("grad.txt", names = ['i','j'], sep="\t", header=None)
NODES = 6301
EDGES = 20777
#  
NEW = csr_matrix((np.ones(len(data['i'])),(data['i'],data['j'])),shape=(NODES,NODES))
b = NEW.sum(axis=1)
NEW = NEW.transpose()
e = np.ones(NODES)
with np.errstate(divide='ignore'): 
             z = e / b
NEW = NEW.dot(csr_matrix(z))

# 
eps = 0.05
k=0
a_0 = 1
y = np.zeros((NODES,1))
p0 = np.ones((NODES,1))/NODES
# 
p0[0] = 0.1
y[np.argmin(df(p0))] = 1              

p1 = (1-2/(1+k))*p0 + 2/(1+k)*y
# 
while ((ln.norm(p1-p0) > eps)):
        y = np.zeros((NODES,1))
        k = k + 1
        p0 = p1
        y[np.argmin(df(p0))] = 1    
        p1 = (1-2/(1+k))*p0 + 2/(1+k)*y
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

للتشغيل الفعال لمحرك بحث حقيقي ، فإن سرعة حساب متجه نظام ترتيب الصفحات أهم من دقة حسابه. MPI لا يسمح لك بالتضحية بالدقة من أجل سرعة الحساب. تساعد خوارزمية مونت كارلو إلى حد ما في التعامل مع هذه المشكلة. نطلق مستخدمًا افتراضيًا يتجول عبر صفحات المواقع. من خلال جمع إحصائيات زياراتهم لصفحات الموقع ، بعد فترة زمنية طويلة نسبيًا نحصل على عدد المرات التي زارها المستخدم لكل صفحة. من خلال تطبيع هذا المتجه ، نحصل على متجه PageRank المطلوب. دعونا نوضح كيف تعمل هذه الخوارزمية على البيانات المستخدمة بالفعل .

#      
def get_edges(m, i):
    if (i == NODES):
        return random.randint(0, NODES)
    else:
        if (len(m.indices[m.indptr[i] : m.indptr[i+1]]) != 0):
            return np.random.choice(m.indices[m.indptr[i] : m.indptr[i+1]])
        else:
            return NODES
#          
data = pd.read_csv("web-Google.txt", names = ['i','j'], sep="\t", header=None)
NODES = 916428
EDGES = 5105039

NEW = csr_matrix((np.ones(len(data['i'])),(data['i'],data['j'])),shape=(NODES,NODES))
#c , total –  
for total in range(1000000,2000000,100000):
# 
    k = random.randint(0, NODES)
#   PageRank
    ans = np.zeros(NODES+1)
    margin2 = np.zeros(NODES)
    ans_prev = np.zeros(NODES)
    for t in range(total):
        j = get_edges(NEW, k)
        ans[j] = ans[j]+1
        k = j
#       
    ans = np.delete(ans, len(ans)-1)
    ans = ans/sum(ans)
    for number in range(len(ans)):
        margin2[number] = ans[number] - ans_prev[number]
    ans_prev = ans
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

كما يتضح من الرسم البياني ، فإن طريقة مونت كارلو ، على عكس الطريقتين السابقتين ، ليست مستقرة (لا يوجد تقارب) ، ولكنها تساعد في تقدير متجه ترتيب الصفحة دون الحاجة إلى الكثير من الوقت.



الخلاصة: وبالتالي ، فقد درسنا الخوارزميات الرئيسية لتحديد PageRank لرسومات الويب. قبل أن تبدأ في تصميم موقع ويب ، يجب أن تتأكد من عدم إهدار نظام ترتيب الصفحات من خلال الانتباه إلى الأمور التالية:

1. توضح الروابط الداخلية كيف تتراكم "قوة الارتباط" على موقعك ، لذا ركز على المعلومات المهمة الموجودة على الصفحة الرئيسية للموقع ، حيث أن الصفحة "الرئيسية" للموقع تتمتع بأقوى نظام ترتيب للصفحات.
2. الصفحات اليتيمة التي لم يتم ربطها من صفحات أخرى على موقعك. حاول تجنب مثل هذه الصفحات.
3. وتجدر الإشارة إلى الروابط الخارجية إذا كانت مفيدة لزائر موقعك.
4. تؤدي الروابط الخارجية المقطوعة إلى تآكل الوزن الإجمالي للصفحة ، لذلك تحتاج إلى مراقبتها بشكل دوري و "إصلاحها" إذا لزم الأمر.

ومع ذلك ، هذا لا يعني أنه يجب عليك التركيز على PageRank. لكن من الجدير بالذكر أنه من خلال الاهتمام بهيكل الموقع عند بنائه ، وميزات الروابط الداخلية والخارجية ، فإنك تقوم بتحسين الموقع من أجل PageRank.