PageRank گوگل چگونه محاسبه می شود؟

اين مقاله با كمي تغييرات ، ترجمه اي از مقاله The Google Pagerank Algorithm and How It Works‌ نوشته Ian Rogers است.

كاربرد PageRank
PageRank يكي از روشهائي است كه Google‌ از آن براي تعيين ارتباط يك صفحه با موضوع و اهميت آن استفاده مي كند. PageRank تنها يكي از مقوله هائي است كه مربوط به ليست شدن سايتها در گوگل مي باشند.

PageRank هر صفحه در نوار ابزار ( Toolbar ) گوگل نمايش داده ميشود. اگر بخواهيد ميتوانيد آنرا از آدرس http://toolbar.google.com دريافت نمائيد. PageRank عددي بين 0 و 10 است و به نظر ميرسد كه از يك مقياس لگاريتمي پيروي مي نمايد.

Toolbar PageRank
(log base 10)
Real PageRank

0
0 - 10

1
100 - 1,000

2
1,000 - 10,000

3
10,000 - 100,000

4
and so on...

جزئيات دقيق اين مقياس مشخص نيست ، چرا كه PageRank صفحات هر ماه و در زماني كه گوگل رتبه بندي خود را انجام ميدهد عوض ميشود . اگر فرض كنيم كه مقياس به صورت لگاريتمي است ، پس گوگل مي تواند به بالاترين PageRank عدد 10 را نسبت دهد و بقيه را نسبت به آن رتبه بندي نمايد. همچنين خود نوار ابزار گوگل بعضي مواقع PageRank را حدس ميزند به خاطر اينكه به صفحاتي كه تازه Upload شده اند نيز PageRank تعلق ميگيرد.
اينطور به نظر ميرسد كه نوار ابزار به URL نگاه ميكند و از روي آن صفحه مادر ( اشاره كننده ) را تشخيص ميدهد و اگر صفحه مادر داراي PageRank باشد ، نوار ابزار عدد 1 را از آن كم ميكند و به به صفحه مذكور PageRank نسبت ميدهد. و اگر از اين راه نتواند PageRank را حدس بزند آنگاه عبارت PageRank بروي نوار ابزار خاكستري ميشود و عبارت No PageRank Information available پس از قرار گرفتن موس بروي آن نمايش داده ميشود.

PageRank چيست؟
به طور مختصر ميتوان گفت كه : PageRank يك "راي" به اهميت يك صفحه خاص است كه توسط تمامي صفحات ديگر وب به آن اختصاص داده مي شود. هر link به صفحه يك راي مثبت به PageRank آن مي باشد و اگر لينكي وجود نداشته باشد راي ممتنع ميگردد (دقت كنيد كه راي منفي نمي شود).
خود گوگل PageRank را به شرح زير تعريف مي نمايد.

"فرض كنيم كه صفحه A داراي صفحات T1 تا Tn است كه به آن اشاره مي كنند. d هم يك فاكتور كند كننده ( damping factor ) است كه مقداري بين 0 تا 1 دارد. معمولا براي d مقداري معادل 0.85 انتخاب ميشود. همچنين C(A) تعداد لينكهائي كه اين صفحه به صفحات ديگر داده است. در اين صورت PageRank صفحه A مساوي است با :

PR(A) = (1-d) + d(PR(T1)/C(T1)+...+PR(Tn)/C(Tn))

بايد توجه داشت كه PageRank به صورت يك احتمال پراكندگي ( probability distribution) بوجود مي آيد و از يك الگوريتم تكرار شونده استفاده ميكند."

اجازه دهيد كه نحوه عملكرد اين فرمول را با تقسيم وظايف اجزاي آن توضيح دهيم :

PR(Tn) : هر صفحه PageRank خود را دارد. كه PR(T1) براي صفحه اول سايت است و PR(Tn) براي nامين صفحه اي كه در سايت به آن مي رسيم.
C(Tn) : هر صفحه راي خود را به صورت مساوي بين صفحاتي كه به آنها لينك داده است تقسيم ميكند. تعداد لينكهاي خارج شده از صفحه 1 را با C(1) و براي صفحه nام را با C(n) نشان داده ايم.
PR(Tn)/C(Tn) : اگر صفحه A‌ از صفحه n يك لينك داشته باشد آنگاه سهم راي صفحه A برابر ميشود با PR(Tn)/C(Tn)
d(... : تمامي آراء با هم جمع ميشود و براي اينكه از افزايش بي رويه وزن برخي از صفحات جلوگيري شود اين مجموع در عدد 0.85 ضرب مي شود.
(1-d) : براي اينكه ميانگين PageRank ها همواره يك باشد.
نحوه محاسبه PageRank
فهميديم كه PageRank صفحه به PageRank صفحاتي كه به آن لينك داده اند بستگي دارد. بنابر اين اين طور به نظر مياد كه ما نميتوانيم PageRank يك صفحه را بدست بياوريم مگر آنكه PageRank صفحات اشاره كننده به آن را محاسبه كنيم. و همچنين اگر يك صفحه داراي لينك به خودش باشد و يا اينكه صفحات از يك شكل دايره اي لينك دادن استفاده كرده باشند تكليف چيست؟
اما حقيقت امر به اين بدي نيست . يعني ما ميتوانيم PageRank صفحه را بدون دانستن PageRank صفحات ديگر بدست آوريم. اين عجيب به نظر ميرسد ولي اساسا هر بار كه ما محاسبه را تكرار ميكنيم يك رقم به رقم نهائي نزديك تر ميشويم. پس تنها چيزي كه بايد به خاطر داشت مقدار بدست آمده در هر بار محاسبه فرمول ميباشد و آنرا بايد تكرار كرد تا آنكه ديگر عدد بدست آمده آنچنان تغييري نكند. در اين زمان به عدد PageRank واقعي رسيده ايم.
يك مثال ساده : دوصفحه كه هر كدام به يكديگر اشاره ميكنند.

هر كدام از اين صفحات تنها يك لينك خروجي دارد . پس C(A) = 1 , C(B) = 1

نميدانيم كه براي شروع PageRank اين صفحات چيست . پس حدس مي زنيم.

حدس 1 :
حدس مي زنيم كه PageRank صفحات 1 است و محاسبه را انجام مي دهيم.

d=0.85
PR(A) = (1-d) + d(PR(B)/1)
PR(B) = (1-d) + d(PR(A)/1)

كه مي شود

PR(A) = 0.15 + 0.85 * 1 = 1
PR(B)= 0.15 + 0.85 * 1 = 1

اعداد اصلا تغيير نميكند ، پس به اين نتيجه مي رسيم كه حدس اول بسيار حدس خوبي بوده است.

حدس 2 :
حدس اول خيلي ساده ما را به نتيجه رساند ، پس ممكن است كه درست نباشد. اجازه دهيد حدس را به عدد صفر تغيير دهيم و محاسبات را تكرار كنيم.

PR(A) = 0.15 + 0.85 * 0 = 0.15
PR(B) = 0.15 + 0.85 * 0.15 = 0.2775

و دوباره تكرار ميكنيم :

PR(A) = 0.15 + 0.85 * 0.2775 = 0.385875
PR(B) = 0.15 + 0.85 * 0.385875 = 0.47799375

و دوباره تكرار ميكنيم :

PR(A) = 0.15 + 0.85 * 0.47799375 = 0.5562946875
PR(B) = 0.15 + 0.85 * 0.5562946875 = 0.622850484375

به همين ترتيب اعداد بزرگتر مي شوند ولي آيا اعداد از يك هم بيشتر ميشوند؟ و اگر عددي از يك بيشتر شود چه بايد كرد؟

حدس 3 :
حالا فرض كنيم كه عدد شروع 40 است. يعني PageRank صفحات A و B عدد 40 است. پس خواهيم داشت:

PR(A) = 0.15 + 0.85 * 40 = 34.15
PR(B) = 0.15 + 0.85 * 34.15 = 29.1775

و دوباره تكرار ميكنيم :

PR(A) = 0.15 + 0.85 * 29.1775 = 24.950875
PR(B) = 0.15 + 0.85 * 24.950875 = 21.35824375

خوب، همان طور كه پيداست اعداد به سمت عدد 1 كم مي شوند و زماني كه به عدد يك برسند ديگر تغيير نخواهند كرد.
كد اجرائي و همچنين برنامه مورد نظر اين محاسبات كه با حدس صفر شروع شده : Show the code | Run the program

اصل مهم : بنابر اين مهم نيست كه حدس را چه عددي قرار دهيم ، محاسبه نهائي به عدد يك ختم خواهد شد.

به جواب سريعتر برسيم
براي رسيدن به جواب در شبكه هاي بزرگ به چه تعداد محاسبه نياز است؟ مثلا براي شبكه اي به گستردگي اينترنت احتياج به ميليونها محاسبه خواهد بود. انتخاب ترتيب محاسبه مي تونه مفيد باشه. با اينكه جواب نهائي يكسان است ، اما انتخاب ترتيب مراحل محاسبات ميتونه به سرعت انجام آن كمك كنه.

حال به يك سري مثال مي پردازيم كه توسط برنامه اي كه لينك آن در انتهاي هر مثال موجود است و در 20 تا 40 مرحله محاسبات انجام شده است.

مثال 1 :
به شكل زير دقت كنيد

پس از محاسبات PageRank صفحات به صورت زير است. Show the code | Run the program

و ميانگين PageRank عدد 1 شده است .
توجه كنيد كه صفحه D با اينكه هيچ لينك ورودي ندارد اما بازهم PageRank آن صفر نيست . پس هر صفحه در ابتدا داراي PageRank معدل 0.15 خواهد بود.

مثال 2 :
يك نمونه سلسله مراتبي ( hierarchy ) به همراه تعدادي لينك خروجي.

Show the code | Run the program

همانطور كه ميتوان تصور كرد Home Page بيشترين PageRank را دارد . چرا كه بيشترين لينك ورودي را دارا مي باشد. اما چرا متوسط عدد 0.378 شده است؟ به نظر مي آيد كه يك جاي كار اشتباه است!

اما اشتباهي رخ نداده است. به صفحات External Site ها توجه كنيد. اين صفحات به هيچ صفحه ديگري لينك نداده اند و بنابراين PageRank خود را هدر مي دهند . براي توضيحات بيشتر به اين thread مراجعه كنيد.

مثال 3 :
اجازه دهيد كه در مثال قبلي External Site ها به Home Page لينك دهيم. ببينيد كه مقدار ميانگين چه تغييري مي كند.

Show the code | Run the program

بهتر شد. نه؟ ضمنا PageRank تمام صفحات هم زياد شده است . بالاخص Home Page.

مثال 4 :
چه اتفاقي براي PageRank مي افتد اگر ما page review داشته باشيم؟

Show the code | Run the program

مثال 5 :
يك سلسله ساده

Show the code | Run the program

دقت كنيد كه PageRank صفحه Home دو نيم برابر صفحات داخلي ميباشد. بنابراين حالت سلسله اي راي ها را براي PageRank در يك صفحه متمركز ميكند.

مثال 6 :
حالت چرخشي ( Looping )

Show the code | Run the program

اين حالت چيزي است كه ما انتظار آنرا داشتيم. تمامي صفحات تعداد لينكهاي مساوي دارند و تمامي صفحات هم PageRank يكسان.

مثال 7 :
حالت Internal linking به صورت گسترده و يا Fully Meshed

Show the code | Run the program

به همون دليل مثال 6 ، اينجا هم همگي داراي PageRank مساوي هستند.

مثال 8 :
سلسله مراتبي - اما با يك لينك ورودي و يك لينك خروجي

فرض كنيد كه يك External Site وجود دارد كه داراي صفحات و لينكهاي زياد است و در نتيجه يكي از صفحات آن داراي PageRank متوسط 1.0 است . همچنين فرض كنيد كه وب مستر آن سايت تنها يك لينك به صفحه Home سايت شما داده است.

Show the code | Run the program

در مثال 5 صفحه Home سايت شما داراي PageRank معادل 1.92 بود . اما در اينجا PageRank به عدد 3.31 ارتقاء پيدا كرده. خيلي عالي است نه؟
ضمنا نه تنها سايت مذكور معادل 0.85 به ما PageRank داده است ، بلكه صفحات ديگر سايت ما هم كه ارتقاء پيدا كرده اند و به ارتقاء صفحه home كمك كرده اند.

اصل مهم: ساختاري منظم براي يك سايت به ارتقاء PageRank آن كمك زيادي ميكند.

مثال 9:
حالت چرخشي - داراي يك لينك ورودي و يك لينك خروجي

Show the code | Run the program

همانطور كه ديده ميشه ، PageRank صفحه Home بالا رفته اما چرا PageRank صفحه More پائين آمده است؟
علت آن است كه ، راي صفحه Product بين صفحه More و سايت B به صورت مساوي تقسيم شده است و در حقيقت اين براي سايت B خوب است و براي ما بد.

مثال 10:
Fully meshed - داراي يك لينك ورودي و يك لينك خروجي

Show the code | Run the program

بهتر شد. مي بينيم كه صفحه Product ميزان 3/4 راي خود را در سايت ما نگه داشته است. همچنين نگهداري اين ميزان راي در سايت ، نتيجه خوبي را براي صفحه Home‌ داشته است.
پس ميتوان گفت كه : بيشتر كردن تعداد لينكهاي داخلي ( Internal Links ) در صفحات از هدر رفتن آراء جلوگيري ميكند و طبيعتا PageRank صفحات سايت ما را افزايش ميدهد .

3 اصل مهم :

اگر صفحه اي داراي اهميت بالائي مي باشد ، آنرا در بالاي مدل سلسله مراتبي قرار دهيد.
اگر صفحات سايت شما داراي لينكهاي خروجي زيادي هستند ، سعي كنيد لينكهاي داخلي سايت را افزايش دهيد تا PageRank صفحات را ثابت نگه داريد .
اگر صفحاتي از سايت شما داراي لينك خروجي نيست ، افزايش تعداد لينكهاي داخلي هيچ تائيري بر PageRank ندارد. پس دقت كنيد كه سايت خود را از حالت قابل استفاده خارج نكنيد.
اهميت داشتن Site Map
داشتن Site Map به دودليل مهم است

اگر كاربر URL اشتباه وارد كند ، اكثر سايتها يك صفحه غير مفيد به عنوان "404 Page not found" نمايش ميدهند. اين براي كاربر مايوس كننده ميباشد. بهتر است كه صفحه اين خطا به حالتي تغيير كند كه اولا علت خطا را نمايش دهد و ثانيا Site Map را هم نمايش دهد .
لينك دادن به Site Map در هر صفحه تعداد لينكهاي داخلي را افزايش ميدهد و در نتيجه از هدر رفتن آراء بر اي ارتقاء PageRank جلوگيري ميكند.
مثال 11:
اجازه دهيد سايت خود را به نحوي نمايش دهيم كه PageRank به طور مصنوعي در صفحه Home متمركز شود.

به نظر مدل خوبي است و تمام آراء به سمت صفحه Home مي رود. بايد PageRank خوبي بدست آوريم. حال برنامه را اجراء ميكنيم تا نتيجه را ببينيم.

Show the code | Run the program

مي بينيد كه نتيجه بر خلاف انتظار ما ، چندان هم خوب نيست. علت اين است كه لينكهاي ورودي صفحات D و C بسيار ضعيف هستند و كمك زيادي به صفحه A نمي كنند.

سعي در سوء استفاده و تقلب در محاسبات PageRank از آنچه كه فكر ميكنيد مشكل تر است.

مثال 12:
يك layout خوب براي صفحات وب كه شامل document طولاني مي باشد اين است كه ، آن document را به چند صفحه تقسيم كنيم و بروي صفحات يك Navigator براي رفتن به صفحات بعد و قبل قرار دهيم و همچنيم در تمام صفحات هم به صفحه Home يك لينك دهيم.

Show the code | Run the program

در اين مثال كه تنها يك document وجود دارد ، صفحه اول از document يعني صفحه B داراي PageRank بيشتري نسبت به صفحه Home يعني A است. به اين خاطر كه صفحه B‌ تمامي راي صفحه A را به خود اختصاص داده است ولي صفحه A تنها بخشي از آراء صفحات B و C و D را به خود اختصاص داده است.

خوب اگر بخواهيد كه سايت قابل استفاده و مفيدي داشته باشيد ممكن است كه PageRank در سايت شما قرباني شود. اما نگران نباشيد ، چونكه اگر سايت شما مفيد باشد webmaster سايتهاي ديگر به سايت شما لينك خواهند داد و PageRank سايت شما احيا خواهد شد.

پس ميتوان گفت كه : با اضافه كردن تعداد لينكهاي داخلي به سايت خود ، مي توانيد PageRank را به طور مساوي بين صفحات سايت تقسيم كنيد.

مثال 13:
در اين مثال مي بينيم كه چگونه ميتوان به PageRank بالائي از روشهاي غلط و تقلب دست يافت.

براي نمونه ببينيم اگر كه 1000 صفحه خارجي به سايت ما لينك دهند و ما تنها يك لينك خروجي داشته باشيم چه مي شود؟

Show the code | Run the program

بله ، صفحات Spam با اينكه بي ارزش هستند اما از PageRank بالائي برخوردارند.

پس ميتوان گفت كه : بهترين متوسط PageRank صفحات سايت شما عدد 1 است و داشتن تعداد صفحات زياد اصلا اهميت ندارد. ولي در مدل سلسله مراتبي ميتوان راي ها را به سمت صفحه Home‌متمركز كرد و PageRank آنرا بالا برد.

از اين روش برخي از سايتها براي بالا بردن PageRank استفاده مي كنند كه اگر رباتهاي گوگل ( Google's robots‌) متوجه آن شوند به احتمال زياد از حضور آن سايتها در فهرستهاي گوگل جلوگيري ميكنند.

بنابراين ، پيشنهاد ميكنم كه از دو روش صحيح زير براي بالا بردن PageRank سايت خود در گوگل استفاده كنيد.

1 - يك سايت بزرگ داشته باشيد
سايتهاي بزرگ مانند http://news.bbc.co.uk داراي دهها و شايد صدها نويسنده و ويراستار خبري ميباشد. هر كدام از صفحات اين سايت داراي مطالب جهاني و مهم هستند و تمامي آنها نيز به صفحه Home سايت لينك داده اند. بنابراين مي بينيم كه PageRank صفحه Home آن 9 از 10 است.

پس هيچ جايگزيني براي محتواي خوب وجود ندارد!

2 - يك چيز مفيد براي ارائه به ديگران داشته باشيد
مي بينيم كه http://www.phpbb.com داراي PageRank معادل 8 از 10 است. با اينكه سرمايه گذاري و بازاريابي قوي پشتيبان آن نبوده است. چه طور اين اتفاق افتاده است؟

علت آن است كه بسياري از افراد كه داراي سايتهاي bulletin board هستند از سيستم مديريت phpbb استفاده كرده اند . در تمام صفحات سايت آنان عبارت زير مشاهده ميشود.

Powered by phpBB

پس ميليونها صفحه راي خود را با قرار دادن اين لينك در خود به سمت سايت http://www.phpbb.com ارسال ميكنند. علت اين است! Drool

دو اصل مهم:

ابزارهاي مفيد رايگان در اختيار ديگران قرار دهيد تا مديران سايتها پس از استفاده از آن با رقبت به سايت شما لينك دهند.
بهتر است كه لينكهاي ورودي از سايتها ي زيادي (‌حتي سايتهائي با PageRank كم ) به سايت شما وجود داشته باشد تا اينكه تنها چند لينك محدود (‌ولو از سايتهائي با PageRank بالا )‌ به سايت خود داشته باشيد.
نتيجه گيري نهائي
PageRank ساده است (‌به جز يك فرمول ترسناك ) ولي وقتي يك محاسبه ساده ميليونها بار تكرار مي شود نتايج ممكن است پيچيده به نظر آيد.

PageRank تنها قسمتي از مسائل تعيين كننده رتبه در ليستهاي گوگل است. به طور مثال شواهد نشان داده است كه گوگل اين روزها به متن موجود در يك href براي تگ <a> اهميت بيشتري قائل است تا PageRank .

PageRank جزئي از داستان ليست شدن در فهرست گوگل است ولي ارزش آنرا دارد كه با آن به عنوان يك طرح خوب در اينترنت بيشتر آشنا شويد.

منابع :

The original PageRank paper by Google’s founders Sergey Brin and Lawrence Page - http://www-db.stanford.edu/~backrub/google.html
Chris Ridings’ “PageRank Explained” paper which, as of April 2002 http://web.archive.org/web/*/http://www.goodlookingcooking.co.uk/PageRank.pdf , contains one major mistake/misunderstanding - http://www.goodlookingcooking.co.uk/PageRank.pdf
Phil Craven’s PageRank Calculator (fortunately his figures agree with mine)
A detailed explanation of how Chris incorrectly altered the PageRank equation with his MiniRank model
An excellent discussion on chad-jams (including “pregnant chad”) by Douglas W. Jones - http://www.cs.uiowa.edu/~jones/cards/chad.html - I don’t think many people know the United States’ voting system is this flawed!!!
Discussion forums on this topic:
MarketPositionTalk - PageRank updates
SearchEngineForums - PR documents and calculator
WebmasterWorld - PR document and calculator

armoazn

مدتها بود ميخواستم اين مقاله رو ترجمه کنم و بنويسم!
کارت خيلي برام جالب بود! Applause

احسان نوشته بود:

مدتها بود ميخواستم اين مقاله رو ترجمه کنم و بنويسم!
کارت خيلي برام جالب بود! Applause

ممنون

به نظر خودم مقاله ي ارزشمندي بود که تو کمتر جايي پيدا ميشه.

اين مقاله رو توي سايت دانشگاه استنفورد ديدم. خيلي علمي تر از مقاله قبليه. توصيه ميکنم اگه وقت داشتيد بخونيدش. Smile

The Anatomy of a Large-Scale Hypertextual Web Search Engine