الگوریتمهای پیجرنک (PageRank) و هیتس (HITS)
پیجرنک و هیتس الگوریتمهای تحلیل پیوند هستند که اهمیت یا اعتبار صفحات وب را از ساختار گراف ابرپیوندها، و نه صرفاً از محتوای صفحه، تخمین میزنند.
Definition
پیجرنک به هر صفحه یک امتیاز اهمیت مستقل از جستجو اختصاص میدهد که برابر با احتمال حالت پایدار آن تحت یک جستجوگر تصادفی است که با احتمال کاهش، پیوندهای خروجی را دنبال میکند و در غیر این صورت دورنوردی میکند، در حالی که هیتس، برای یک زیرگراف وابسته به جستجو، امتیازات اعتبار را برای صفحات با محتوای ارزشمند و امتیازات هاب را برای صفحاتی که به مراجع خوب پیوند میدهند، محاسبه میکند که هر یک دیگری را تقویت میکند.
Scope
این موضوع دو الگوریتم بنیادی تحلیل پیوند را پوشش میدهد: پیجرنک، یک معیار مستقل از جستجو برای اهمیت صفحه بر اساس مدل «جستجوگر تصادفی» (random-surfer) با قابلیت «دورنوردی» (teleportation)، و هیتس، یک طرح وابسته به جستجو که امتیازات متقابلاً تقویتکننده «هاب» (hub) و «اعتبار» (authority) را محاسبه میکند. این موضوع به فرمولبندیهای زیربنایی «گام تصادفی» (random-walk) و «بردار ویژه» (eigenvector)، نقش «کاهش» (damping) و دورنوردی، همگرایی، و انواع حساس به موضوع میپردازد. این موضوع نحوه ترکیب این امتیازات با ویژگیهای متنی برای رتبهبندی نهایی را که به رتبهبندی جستجوی وب تعلق دارد، شامل نمیشود.
Core questions
- مدل جستجوگر تصادفی چگونه پیجرنک را به عنوان یک توزیع حالت پایدار تعریف میکند؟
- چرا برای اینکه پیجرنک به خوبی تعریف شود، به یک عامل کاهش یا دورنوردی نیاز است؟
- امتیازات هاب و اعتبار در هیتس چگونه یکدیگر را تقویت میکنند؟
- این امتیازات چگونه به صورت تکراری محاسبه میشوند و چه زمانی همگرا میشوند؟
- پیجرنک و هیتس در مستقل از جستجو بودن در مقابل وابسته به جستجو بودن چگونه با یکدیگر تفاوت دارند؟
Key concepts
- پیجرنک (PageRank)
- مدل جستجوگر تصادفی (random-surfer model)
- عامل کاهش (damping factor) و دورنوردی (teleportation)
- توزیع حالت پایدار (stationary distribution) / بردار ویژه اصلی (principal eigenvector)
- هیتس (HITS)
- هابها (hubs) و مراجع (authorities)
- امتیازدهی مستقل از جستجو (query-independent) در مقابل وابسته به جستجو (query-dependent)
- تکرار توانی (power iteration) و همگرایی (convergence)
Key theories
- مدل جستجوگر تصادفی پیجرنک
- مدلسازی یک جستجوگر که پیوندها را با احتمالی برابر با یک عامل کاهش دنبال میکند و در غیر این صورت به یک صفحه تصادفی میپرد، یک زنجیره مارکوف را ایجاد میکند که توزیع حالت پایدار منحصر به فرد آن، صفحات را بر اساس بازدید طولانیمدت امتیازدهی میکند و یک معیار اهمیت پایدار و مستقل از جستجو را ارائه میدهد.
- هابها و مراجع هیتس
- در یک زیرگراف متمرکز بر جستجو، هیتس به هر صفحه یک امتیاز اعتبار متناسب با امتیازات هاب صفحاتی که به آن پیوند میدهند و یک امتیاز هاب متناسب با امتیازات اعتبار صفحاتی که به آنها پیوند میدهد، اختصاص میدهد که با تکرار این روابط متقابلاً تقویتکننده تا همگرایی محاسبه میشود.
Clinical relevance
پیجرنک در ظهور جستجوی وب در مقیاس بزرگ محوری بود و همچنان یک نقطه مرجع مفهومی برای اهمیت و اعتبار در گرافها باقی مانده است. ایدههای تحلیل پیوند فراتر از وب به شبکههای استنادی، نفوذ شبکههای اجتماعی، تشخیص تقلب، و توصیهگرها، در هر جایی که پیوندهای شبیه به تأیید اطلاعات را حمل میکنند، تعمیم مییابند.
History
در سالهای ۱۹۹۸ و ۱۹۹۹، دو پیشنهاد تقریباً همزمان نشان دادند که ابرپیوندها اعتبار را کدگذاری میکنند: هیتس کلاینبرگ و پیجرنک پیج و برین. امتیازات مستقل از جستجو و محاسبهشده جهانی پیجرنک برای ارائه در مقیاس وب بسیار مناسب بود و زیربنای یک موتور جستجوی پیشرو را تشکیل داد، در حالی که هیتس بر «استخراج موضوع» (topic-distillation) و تحقیقات بعدی در زمینه رتبهبندی گراف تأثیر گذاشت.
Key figures
- Larry Page
- Sergey Brin
- Jon Kleinberg
- Rajeev Motwani
Related topics
Seminal works
- page1999
- kleinberg1999
- brin1998
Frequently asked questions
- تفاوت بین پیجرنک و هیتس چیست؟
- پیجرنک یک امتیاز اهمیت واحد و مستقل از جستجو را برای هر صفحه از کل گراف وب از قبل محاسبه میکند، در حالی که هیتس امتیازات هاب و اعتبار وابسته به جستجو را بر روی یک زیرگراف کوچک که در زمان بازیابی حول جستجو ساخته شده است، محاسبه میکند. پیجرنک به راحتی بیشتری برای ارائه وب مقیاسپذیر است.
- چرا پیجرنک به یک عامل کاهش نیاز دارد؟
- بدون آن، جستجوگر تصادفی ممکن است در صفحاتی بدون پیوندهای خروجی یا در چرخهها گرفتار شود و توزیع حالت پایدار ممکن است منحصر به فرد یا به خوبی تعریف شده نباشد. احتمال کاهش (دورنوردی) به جستجوگر اجازه میدهد تا گهگاه به یک صفحه تصادفی بپرد و یک امتیاز منحصر به فرد و خوشرفتار را تضمین میکند.