Skip to content
بازگشت به نتایج جست‌وجو

PageRank Centrality

معرفی‌شده توسط
Page, Brin, Motwani & Winograd
سال
1999
نوع
Iterative link-based centrality algorithm
خانواده
Centrality

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

PageRank یک الگوریتم مرکزیت مبتنی بر پیوند است که با اندازه‌گیری اینکه چه تعداد گره با کیفیت بالا به آن اشاره می‌کنند، به هر گره در یک گراف جهت‌دار امتیاز اهمیت اختصاص می‌دهد. این الگوریتم که توسط لری پیج، سرگئی برین، راجیف موتوانی و تری وینوگراد در دانشگاه استنفورد در سال ۱۹۹۹ معرفی شد، مبنای ریاضی موتور جستجوی گوگل شد و همچنان یکی از تأثیرگذارترین الگوریتم‌ها در علم شبکه و بازیابی اطلاعات باقی مانده است.

شهود پشت روش

یک کاربر وب را تصور کنید که پیوندها را به صورت تصادفی کلیک می‌کند و گاهی اوقات به جای دنبال کردن پیوند، به یک صفحه کاملاً تصادفی می‌پرد. کسری از زمان که این کاربر صرف هر صفحه می‌کند، پس از تعداد بی‌نهایت کلیک، PageRank آن صفحه است. صفحه‌ای که اغلب بازدید می‌شود - زیرا بسیاری از صفحات محبوب به آن پیوند دارند - امتیاز بالایی دریافت می‌کند. ضریب میرایی (معمولاً ۰.۸۵) احتمال ادامه کلیک کردن به جای پرش را مدل می‌کند.

تاریخ

PageRank در دانشگاه استنفورد توسط لری پیج و سرگئی برین به عنوان مکانیزم رتبه‌بندی اصلی پروژه جستجوی BackRub آنها توسعه یافت که در سال ۱۹۹۸ به گوگل تبدیل شد. گزارش فنی بنیادی، که با همکاری راجیف موتوانی و تری وینوگراد نوشته شد، در سال ۱۹۹۹ منتشر شد. این الگوریتم استفاده از مرکزیت مبتنی بر ویژه بردار را در شبکه‌های جهت‌دار در مقیاس بزرگ رایج کرد و مستقیماً الگوریتم‌های تحلیل پیوند بعدی از جمله HITS و TrustRank را الهام بخشید.

چه زمانی استفاده شود

PageRank زمانی مناسب است که نیاز به رتبه‌بندی گره‌ها در یک گراف جهت‌دار بر اساس اهمیت ساختاری جهانی دارید، به خصوص زمانی که جهت یال نشان‌دهنده تأیید یا نفوذ (پیوندهای وب، استنادات، دنبال‌کنندگان اجتماعی) باشد. این الگوریتم فرض می‌کند که گراف را می‌توان به عنوان یک زنجیره مارکوف مدل کرد و برای همگرایی تمیز به یک مؤلفه متصل یا قویاً متصل نیاز دارد. این الگوریتم برای شبکه‌های بدون جهت کمتر مناسب است و ممکن است معیارهای مرکزیت HITS یا بینابینی ترجیح داده شوند، و می‌تواند به اسپم پیوند یا افزایش مصنوعی درجه ورودی حساس باشد.

محدودیت‌ها و ملاحظات

  • نیاز به گراف جهت‌دار دارد؛ کاربرد در شبکه‌های بدون جهت نیازمند انتخاب قرارداد است
  • سرعت همگرایی به شکاف طیفی ماتریس انتقال بستگی دارد و برای گراف‌های با اتصال ضعیف می‌تواند کند باشد
  • به انتخاب ضریب میرایی d حساس است؛ مقادیر مختلف می‌توانند رتبه‌بندی‌ها را به طور قابل توجهی تغییر دهند
  • در برابر دستکاری مزارع پیوند و پیوندهای ورودی مصنوعی آسیب‌پذیر است

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • مبنای احتمالی اصولی از طریق مدل زنجیره مارکوف کاربر تصادفی
  • با استفاده از ضرب ماتریس-بردار پراکنده و تکرار توان، به گراف‌های بسیار بزرگ مقیاس می‌شود
  • توپولوژی جهانی گراف را ثبت می‌کند و به گره‌هایی که توسط سایر گره‌های با امتیاز بالا تأیید شده‌اند پاداش می‌دهد
  • در دامنه‌های وب، استنادی، بیولوژیکی و شبکه‌های اجتماعی به طور گسترده اعتبارسنجی شده است

کاربردها

  • رتبه‌بندی موتور جستجوی وب: مرتب‌سازی نتایج جستجو بر اساس اعتبار جهانی صفحات وب
  • تحلیل استنادی دانشگاهی: شناسایی مقالات یا مجلات تأثیرگذار در شبکه‌های ادبیات علمی
  • اندازه‌گیری نفوذ در شبکه‌های اجتماعی: رتبه‌بندی کاربران بر اساس اعتبار دنبال‌کنندگانشان
  • تحلیل شبکه بیولوژیکی: یافتن پروتئین‌ها یا ژن‌های هاب در شبکه‌های برهم‌کنش پروتئین و تنظیم ژن
  • سیستم‌های توصیه‌گر: انتشار سیگنال‌های ترجیحی از طریق گراف‌های دو بخشی کاربر-آیتم

چگونه کار می‌کند

چگونه کار می‌کند

1

هر گره در گراف با امتیاز PageRank برابر ۱/N شروع می‌شود، که N تعداد کل گره‌ها است. این مقداردهی اولیه یکنواخت تضمین می‌کند که هیچ گره‌ای مزیت مصنوعی ندارد و قبل از اولین تکرار، یک توزیع احتمال معتبر در سراسر شبکه فراهم می‌کند.

فرمول
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}
2

یک ماتریس انتقال ستونی تصادفی (column-stochastic) M از ساختار مجاورت گراف ساخته می‌شود. هر درایه M_ij برابر با ۱ تقسیم بر درجه خروجی گره j است اگر یال از j به i وجود داشته باشد، و در غیر این صورت صفر است. گره‌های آویزان (بدون یال خروجی) معمولاً با توزیع مجدد امتیاز خود به طور یکنواخت در بین همه گره‌ها مدیریت می‌شوند.

فرمول
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}
3

بردار PageRank با استفاده از فرمول کاربر تصادفی به صورت تکراری به‌روزرسانی می‌شود. با ضریب میرایی d (پیش‌فرض ۰.۸۵)، هر گره احتمال پایه تله‌پورت (۱-d)/N را به اضافه d برابر مجموع وزنی امتیازات دریافتی از تمام گره‌هایی که به آن پیوند دارند، دریافت می‌کند. این مرحله تا زمانی که امتیازات پایدار شوند، تکرار می‌شود.

فرمول
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}
4

پس از هر تکرار، نرم L1 تغییر در بردار امتیاز با یک مقدار کوچک تولرانس اپسیلون (مثلاً ۱e-6) مقایسه می‌شود. هنگامی که تغییر کمتر از این آستانه قرار گرفت، الگوریتم همگرا شده است و بردار امتیاز فعلی به عنوان توزیع نهایی PageRank بازگردانده می‌شود.

فرمول
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilon

دام‌های رایج

  • نادیده گرفتن گره‌های آویزان (گره‌های بدون یال خروجی) می‌تواند خاصیت تصادفی ماتریس انتقال را مختل کرده و منجر به امتیازات نادرست شود
  • استفاده از PageRank بر روی گراف‌های بدون جهت بدون تبدیل به مدل انتقال متقارن ممکن است تخمین‌های مرکزیت گمراه‌کننده‌ای تولید کند
  • تنظیم تولرانس بیش از حد شل منجر به همگرایی زودهنگام می‌شود؛ تنظیم بیش از حد سفت و سخت، محاسبات را بدون تغییرات معنی‌دار امتیاز افزایش می‌دهد
  • تفسیر PageRank به عنوان یک معیار اهمیت مطلق به جای یک رتبه‌بندی نسبی در چارچوب یک گراف خاص

پرسش‌های متداول

ضریب میرایی d چه چیزی را نشان می‌دهد و چگونه باید انتخاب شود؟

ضریب میرایی d (معمولاً ۰.۸۵) احتمال این است که کاربر تصادفی به جای پرش به یک گره تصادفی، یک پیوند را دنبال کند. مقادیر نزدیک به ۱ الگوریتم را به ساختار گراف حساس‌تر می‌کنند اما همگرایی کندتر و تمایل بیشتری به ایجاد گره‌های گیرنده رتبه دارند؛ مقادیر نزدیک به ۰ به رتبه‌بندی یکنواخت نزدیک می‌شوند. مقدار ۰.۸۵ به صورت تجربی توسط پیج و برین برای گراف وب تأیید شد و مقدار پیش‌فرض استاندارد است.

PageRank چگونه با مرکزیت درجه متفاوت است؟

مرکزیت درجه فقط تعداد مستقیم پیوندهای ورودی به یک گره را می‌شمارد و همه منابع را یکسان در نظر می‌گیرد. PageRank هر پیوند ورودی را با امتیاز گره پیوند دهنده وزن‌دهی می‌کند، بنابراین تأیید از یک گره با رتبه بالا بیشتر از یک گره با رتبه پایین اهمیت دارد. این تعریف بازگشتی ساختار جهانی گراف را به جای صرفاً اتصال محلی ثبت می‌کند.

آیا PageRank را می‌توان برای گراف‌های بدون جهت اعمال کرد؟

بله، اما با ملاحظاتی. یک گراف بدون جهت باید با جایگزینی هر یال بدون جهت با دو یال جهت‌دار به یک نمایش جهت‌دار تبدیل شود. امتیازات PageRank حاصل سپس برابر با تابعی از درجه گره می‌شوند و الگوریتم را به یک مرکزیت درجه وزن‌دار تقلیل می‌دهند. برای شبکه‌های بدون جهت، معیارهای مرکزیت جایگزین مانند مرکزیت ویژه بردار یا مرکزیت بینابینی اغلب آموزنده‌تر هستند.

روش‌های مرتبط

منابع

  1. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.

    باز کردن مرجع انتشار
    کپی شد.