پیج رنک گوگل چگونه محاسبه می شود :
PageRank یکی از روشهائی است که Google از آن برای تعیین ارتباط یک صفحه با موضوع و اهمیت آن استفاده می کند. PageRank تنها یکی از مقوله هائی است که مربوط به لیست شدن سایتها در گوگل می باشند.
PageRank هر صفحه در نوار ابزار ( Toolbar ) گوگل نمایش داده میشود. اگر بخواهید میتوانید آنرا از آدرس http://toolbar.google.com دریافت نمائید. PageRank عددی بین ۰ و ۱۰ است و به نظر میرسد که از یک مقیاس لگاریتمی پیروی می نماید.
جزئیات دقیق این مقیاس مشخص نیست ، چرا که PageRank صفحات هر ماه و در زمانی که گوگل رتبه بندی خود را انجام میدهد عوض میشود . اگر فرض کنیم که مقیاس به صورت لگاریتمی است ، پس گوگل می تواند به بالاترین PageRank عدد ۱۰ را نسبت دهد و بقیه را نسبت به آن رتبه بندی نماید. همچنین خود نوار ابزار گوگل بعضی مواقع PageRank را حدس میزند به خاطر اینکه به صفحاتی که تازه Upload شده اند نیز PageRank تعلق میگیرد.
اینطور به نظر میرسد که نوار ابزار به URL نگاه میکند و از روی آن صفحه مادر ( اشاره کننده ) را تشخیص میدهد و اگر صفحه مادر دارای PageRank باشد ، نوار ابزار عدد ۱ را از آن کم میکند و به به صفحه مذکور PageRank نسبت میدهد. و اگر از این راه نتواند PageRank را حدس بزند آنگاه عبارت PageRank بروی نوار ابزار خاکستری میشود و عبارت No PageRank Information available پس از قرار گرفتن موس بروی آن نمایش داده میشود.
PageRank چیست؟
به طور مختصر میتوان گفت که : PageRank یک “رای” به اهمیت یک صفحه خاص است که توسط تمامی صفحات دیگر وب به آن اختصاص داده می شود. هر link به صفحه یک رای مثبت به PageRank آن می باشد و اگر لینکی وجود نداشته باشد رای ممتنع میگردد (دقت کنید که رای منفی نمی شود).
خود گوگل PageRank را به شرح زیر تعریف می نماید.
“فرض کنیم که صفحه A دارای صفحات T1 تا Tn است که به آن اشاره می کنند. d هم یک فاکتور کند کننده ( damping factor ) است که مقداری بین ۰ تا ۱ دارد. معمولا برای d مقداری معادل ۰٫۸۵ انتخاب میشود. همچنین C(A) تعداد لینکهائی که این صفحه به صفحات دیگر داده است. در این صورت PageRank صفحه A مساوی است با :
PR(A) = (1-d) + d(PR(T1)/C(T1)+…+PR(Tn)/C(Tn))
باید توجه داشت که PageRank به صورت یک احتمال پراکندگی ( probability distribution) بوجود می آید و از یک الگوریتم تکرار شونده استفاده میکند.”
اجازه دهید که نحوه عملکرد این فرمول را با تقسیم وظایف اجزای آن توضیح دهیم :
فهمیدیم که PageRank صفحه به PageRank صفحاتی که به آن لینک داده اند بستگی دارد. بنابر این این طور به نظر میاد که ما نمیتوانیم PageRank یک صفحه را بدست بیاوریم مگر آنکه PageRank صفحات اشاره کننده به آن را محاسبه کنیم. و همچنین اگر یک صفحه دارای لینک به خودش باشد و یا اینکه صفحات از یک شکل دایره ای لینک دادن استفاده کرده باشند تکلیف چیست؟
اما حقیقت امر به این بدی نیست . یعنی ما میتوانیم PageRank صفحه را بدون دانستن PageRank صفحات دیگر بدست آوریم. این عجیب به نظر میرسد ولی اساسا هر بار که ما محاسبه را تکرار میکنیم یک رقم به رقم نهائی نزدیک تر میشویم. پس تنها چیزی که باید به خاطر داشت مقدار بدست آمده در هر بار محاسبه فرمول میباشد و آنرا باید تکرار کرد تا آنکه دیگر عدد بدست آمده آنچنان تغییری نکند. در این زمان به عدد PageRank واقعی رسیده ایم.
یک مثال ساده : دوصفحه که هر کدام به یکدیگر اشاره میکنند.
هر کدام از این صفحات تنها یک لینک خروجی دارد . پس C(A) = 1 , C(B) = 1
نمیدانیم که برای شروع PageRank این صفحات چیست . پس حدس می زنیم.
حدس ۱ :
حدس می زنیم که PageRank صفحات ۱ است و محاسبه را انجام می دهیم.
اعداد اصلا تغییر نمیکند ، پس به این نتیجه می رسیم که حدس اول بسیار حدس خوبی بوده است.
حدس ۲ :
حدس اول خیلی ساده ما را به نتیجه رساند ، پس ممکن است که درست نباشد. اجازه دهید حدس را به عدد صفر تغییر دهیم و محاسبات را تکرار کنیم.
حدس ۳ :
حالا فرض کنیم که عدد شروع ۴۰ است. یعنی PageRank صفحات A و B عدد ۴۰ است. پس خواهیم داشت:
کد اجرائی و همچنین برنامه مورد نظر این محاسبات که با حدس صفر شروع شده : Show the code | Run the program
اصل مهم : بنابر این مهم نیست که حدس را چه عددی قرار دهیم ، محاسبه نهائی به عدد یک ختم خواهد شد.
به جواب سریعتر برسیم
برای رسیدن به جواب در شبکه های بزرگ به چه تعداد محاسبه نیاز است؟ مثلا برای شبکه ای به گستردگی اینترنت احتیاج به میلیونها محاسبه خواهد بود. انتخاب ترتیب محاسبه می تونه مفید باشه. با اینکه جواب نهائی یکسان است ، اما انتخاب ترتیب مراحل محاسبات میتونه به سرعت انجام آن کمک کنه.
حال به یک سری مثال می پردازیم که توسط برنامه ای که لینک آن در انتهای هر مثال موجود است و در ۲۰ تا ۴۰ مرحله محاسبات انجام شده است.
ادامه دارد ...
با تشکر از مهندس ابراهیمی که در ترجمه این مقاله بسیار من را یاری کرد.
منبع : hostirani.com
منبع : hostirani.com
- این مقاله با کمی تغییرات ، ترجمه ای از مقاله The Google Pagerank Algorithm and How It Works نوشته Ian Rogers است.
- لازم به ذکر است که کلیه تصاویر و لینکهای مربوط به اجراء برنامه ها در سایت http://www.iprcom.com میباشد و مترجم هیچگونه دخالتی در آنها نداشته است.
PageRank یکی از روشهائی است که Google از آن برای تعیین ارتباط یک صفحه با موضوع و اهمیت آن استفاده می کند. PageRank تنها یکی از مقوله هائی است که مربوط به لیست شدن سایتها در گوگل می باشند.
PageRank هر صفحه در نوار ابزار ( Toolbar ) گوگل نمایش داده میشود. اگر بخواهید میتوانید آنرا از آدرس http://toolbar.google.com دریافت نمائید. PageRank عددی بین ۰ و ۱۰ است و به نظر میرسد که از یک مقیاس لگاریتمی پیروی می نماید.
Toolbar PageRank
(log base 10)
(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…
اینطور به نظر میرسد که نوار ابزار به URL نگاه میکند و از روی آن صفحه مادر ( اشاره کننده ) را تشخیص میدهد و اگر صفحه مادر دارای PageRank باشد ، نوار ابزار عدد ۱ را از آن کم میکند و به به صفحه مذکور PageRank نسبت میدهد. و اگر از این راه نتواند PageRank را حدس بزند آنگاه عبارت PageRank بروی نوار ابزار خاکستری میشود و عبارت No PageRank Information available پس از قرار گرفتن موس بروی آن نمایش داده میشود.
PageRank چیست؟
به طور مختصر میتوان گفت که : PageRank یک “رای” به اهمیت یک صفحه خاص است که توسط تمامی صفحات دیگر وب به آن اختصاص داده می شود. هر link به صفحه یک رای مثبت به PageRank آن می باشد و اگر لینکی وجود نداشته باشد رای ممتنع میگردد (دقت کنید که رای منفی نمی شود).
خود گوگل PageRank را به شرح زیر تعریف می نماید.
“فرض کنیم که صفحه A دارای صفحات T1 تا Tn است که به آن اشاره می کنند. d هم یک فاکتور کند کننده ( damping factor ) است که مقداری بین ۰ تا ۱ دارد. معمولا برای d مقداری معادل ۰٫۸۵ انتخاب میشود. همچنین 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) : هر صفحه رای خود را به صورت مساوی بین صفحاتی که به آنها لینک داده است تقسیم میکند. تعداد لینکهای خارج شده از صفحه ۱ را با C(1) و برای صفحه nام را با C
نشان داده ایم. - PR(Tn)/C(Tn) : اگر صفحه A از صفحه n یک لینک داشته باشد آنگاه سهم رای صفحه A برابر میشود با PR(Tn)/C(Tn)
- d(… : تمامی آراء با هم جمع میشود و برای اینکه از افزایش بی رویه وزن برخی از صفحات جلوگیری شود این مجموع در عدد ۰٫۸۵ ضرب می شود.
- (۱-d) : برای اینکه میانگین PageRank ها همواره یک باشد.
فهمیدیم که PageRank صفحه به PageRank صفحاتی که به آن لینک داده اند بستگی دارد. بنابر این این طور به نظر میاد که ما نمیتوانیم PageRank یک صفحه را بدست بیاوریم مگر آنکه PageRank صفحات اشاره کننده به آن را محاسبه کنیم. و همچنین اگر یک صفحه دارای لینک به خودش باشد و یا اینکه صفحات از یک شکل دایره ای لینک دادن استفاده کرده باشند تکلیف چیست؟
اما حقیقت امر به این بدی نیست . یعنی ما میتوانیم PageRank صفحه را بدون دانستن PageRank صفحات دیگر بدست آوریم. این عجیب به نظر میرسد ولی اساسا هر بار که ما محاسبه را تکرار میکنیم یک رقم به رقم نهائی نزدیک تر میشویم. پس تنها چیزی که باید به خاطر داشت مقدار بدست آمده در هر بار محاسبه فرمول میباشد و آنرا باید تکرار کرد تا آنکه دیگر عدد بدست آمده آنچنان تغییری نکند. در این زمان به عدد PageRank واقعی رسیده ایم.
یک مثال ساده : دوصفحه که هر کدام به یکدیگر اشاره میکنند.
نمیدانیم که برای شروع PageRank این صفحات چیست . پس حدس می زنیم.
حدس ۱ :
حدس می زنیم که PageRank صفحات ۱ است و محاسبه را انجام می دهیم.
d=0.85
PR(A) = (1-d) + d(PR(B)/1)
PR(B) = (1-d) + d(PR(A)/1)
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
PR(B)= 0.15 + 0.85 * 1 = 1
اعداد اصلا تغییر نمیکند ، پس به این نتیجه می رسیم که حدس اول بسیار حدس خوبی بوده است.
حدس ۲ :
حدس اول خیلی ساده ما را به نتیجه رساند ، پس ممکن است که درست نباشد. اجازه دهید حدس را به عدد صفر تغییر دهیم و محاسبات را تکرار کنیم.
PR(A) = 0.15 + 0.85 * 0 = 0.15
PR(B) = 0.15 + 0.85 * 0.15 = 0.2775
و دوباره تکرار میکنیم :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(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
به همین ترتیب اعداد بزرگتر می شوند ولی آیا اعداد از یک هم بیشتر میشوند؟ و اگر عددی از یک بیشتر شود چه باید کرد؟PR(B) = 0.15 + 0.85 * 0.5562946875 = 0.622850484375
حدس ۳ :
حالا فرض کنیم که عدد شروع ۴۰ است. یعنی PageRank صفحات A و B عدد ۴۰ است. پس خواهیم داشت:
PR(A) = 0.15 + 0.85 * 40 = 34.15
PR(B) = 0.15 + 0.85 * 34.15 = 29.1775
و دوباره تکرار میکنیم :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
خوب، همان طور که پیداست اعداد به سمت عدد ۱ کم می شوند و زمانی که به عدد یک برسند دیگر تغییر نخواهند کرد.PR(B) = 0.15 + 0.85 * 24.950875 = 21.35824375
کد اجرائی و همچنین برنامه مورد نظر این محاسبات که با حدس صفر شروع شده : Show the code | Run the program
اصل مهم : بنابر این مهم نیست که حدس را چه عددی قرار دهیم ، محاسبه نهائی به عدد یک ختم خواهد شد.
به جواب سریعتر برسیم
برای رسیدن به جواب در شبکه های بزرگ به چه تعداد محاسبه نیاز است؟ مثلا برای شبکه ای به گستردگی اینترنت احتیاج به میلیونها محاسبه خواهد بود. انتخاب ترتیب محاسبه می تونه مفید باشه. با اینکه جواب نهائی یکسان است ، اما انتخاب ترتیب مراحل محاسبات میتونه به سرعت انجام آن کمک کنه.
حال به یک سری مثال می پردازیم که توسط برنامه ای که لینک آن در انتهای هر مثال موجود است و در ۲۰ تا ۴۰ مرحله محاسبات انجام شده است.
ادامه دارد ...