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

پیج‌رنک وزن‌دار

معرفی‌شده توسط
Xing, W. & Ghorbani, A.
سال
2004
نوع
Centrality measure / ranking algorithm
خانواده
Network science

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

اندازه قلم

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

پیج‌رنک وزن‌دار (Weighted PageRank) الگوریتم کلاسیک پیج‌رنک را به شبکه‌هایی گسترش می‌دهد که در آن‌ها یال‌ها دارای قدرت یا فراوانی‌های متفاوتی هستند و اهمیت را متناسب با وزن یال‌های ورودی و خروجی توزیع می‌کند، نه اینکه همه پیوندها را به یک اندازه در نظر بگیرد. این امر آن را در هر شبکه‌ای که قدرت اتصال اهمیت دارد، به طور قابل توجهی آموزنده‌تر از پیج‌رنک باینری می‌سازد.

شهود پشت روش

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

تاریخ

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

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

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

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

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

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

نقاط قوت

  • قدرت یال را مستقیماً در انتشار اهمیت گنجانده و رتبه‌بندی‌های واقع‌بینانه‌تری نسبت به پیج‌رنک باینری در شبکه‌های وزن‌دار ارائه می‌دهد.
  • اعتبار جهانی و در سطح شبکه را به جای تنها اتصال محلی، به تصویر می‌کشد.
  • مکانیسم تله‌پورتاسیون پیج‌رنک را حفظ می‌کند و آن را در برابر گره‌های آویزان و مؤلفه‌های جدا شده، در صورت تصحیح، مقاوم می‌سازد.
  • از طریق محاسبات تکراری کارآمد به شبکه‌های بزرگ مقیاس‌پذیر است؛ عملیات ماتریس پراکنده حافظه را قابل مدیریت نگه می‌دارد.
  • به راحتی قابل تفسیر است: امتیاز بالا به این معنی است که یک گره تأییدیه سنگین و وزن‌دار از سایر گره‌های با امتیاز بالا دریافت می‌کند.

کاربردها

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

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

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

1

شبکه را به عنوان یک گراف نمایش دهید که در آن هر یال دارای یک وزن عددی است که نشان‌دهنده قدرت پیوند است — مانند فراوانی تعامل، حجم تراکنش، تعداد هم‌تألیفی، یا امتیاز شباهت. الگوریتم نیازمند این است که این وزن‌ها نامنفی باشند؛ وزن‌های منفی باید قبل از تحلیل تبدیل شوند.

2

برای هر یال جهت‌دار از گره v به گره u، دو عامل وزن را محاسبه کنید: یک عامل وزن ورودی که وزن یال را با کل وزن ورودی u نرمال‌سازی می‌کند، و یک عامل وزن خروجی که آن را با کل وزن خروجی v نرمال‌سازی می‌کند. این کسرها تعیین می‌کنند که چه مقدار از رتبه v از طریق این یال خاص به u توزیع می‌شود.

فرمول
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}
3

فرمول پیج‌رنک وزن‌دار را به صورت تکراری اعمال کنید: رتبه هر گره برابر است با یک عبارت تله‌پورتاسیون پایه (1 منهای عامل میرایی d، که معمولاً 0.85 است) به علاوه d برابر مجموع رتبه همه همسایگان ورودی که با دو عامل وزن مقیاس‌بندی شده‌اند. این امر رتبه را متناسب با قدرت یال توزیع می‌کند، نه به طور یکنواخت.

فرمول
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)
4

به‌روزرسانی رتبه را تا زمانی تکرار کنید که تغییر در امتیاز هر گره کمتر از یک تلرانس کوچک (معمولاً 1e-6) شود. همگرایی برای گراف‌های قویاً همبند تضمین شده است؛ برای گراف‌هایی با گره‌های آویزان یا مؤلفه‌های ایزوله، تصحیح استاندارد گره‌های آویزان را قبل از تکرار اعمال کنید.

5

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

دام‌های رایج

  • استفاده از وزن‌های یال خام و نرمال‌نشده بدون بررسی مقیاس آن‌ها — ترکیب تعداد در ده‌ها با مقادیر در میلیون‌ها، انتشار رتبه را مخدوش می‌کند.
  • فراموش کردن مدیریت گره‌های آویزان (گره‌های بدون یال خروجی)، که در صورت عدم تصحیح، می‌توانند رتبه را از کل شبکه تخلیه کنند.
  • فرض اینکه عامل میرایی پیش‌فرض 0.85 به طور جهانی مناسب است؛ در شبکه‌های استنادی یا بیولوژیکی، یک مقدار متفاوت ممکن است بهتر منعکس‌کننده دامنه باشد.
  • تفسیر امتیازات پیج‌رنک وزن‌دار به عنوان احتمالات مطلق به جای رتبه‌بندی‌های نسبی — تنها ترتیب آن‌ها در اجراهای مختلف پایدار است.
  • مقایسه امتیازات پیج‌رنک وزن‌دار در شبکه‌های با اندازه‌های مختلف بدون نرمال‌سازی.

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

پیج‌رنک وزن‌دار چه تفاوتی با پیج‌رنک استاندارد دارد؟

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

از چه عامل میرایی باید استفاده کنم؟

مقدار متداول 0.85 است که از مفروضات گراف وب در مورد گشت و گذار تصادفی مشتق شده است. برای شبکه‌های اجتماعی، بیولوژیکی یا استنادی، مقادیر بین 0.5 تا 0.9 در ادبیات بررسی شده‌اند. تحلیل حساسیت در طیفی از مقادیر میرایی توصیه می‌شود.

آیا پیج‌رنک وزن‌دار را می‌توان برای شبکه‌های بدون جهت به کار برد؟

بله، با نمایش هر یال بدون جهت به عنوان یک جفت یال جهت‌دار با وزن یکسان. سپس الگوریتم عوامل وزن ورودی و خروجی متقارن تولید می‌کند که به فرمولی ساده می‌شود که همچنان به قدرت یال احترام می‌گذارد.

چگونه با یال‌های با وزن صفر برخورد کنم؟

یال‌های با وزن صفر هیچ کمکی به انتشار رتبه نمی‌کنند، بنابراین می‌توانند قبل از تحلیل حذف شوند. اگر وزن‌های صفر از نظر ساختاری معنی‌دار هستند (عدم وجود در مقابل داده‌های از دست رفته)، تمایز را قبل از حذف آن‌ها به وضوح مستند کنید.

آیا پیج‌رنک وزن‌دار بهتر از مرکزیت درجه وزن‌دار است؟

بستگی به سؤال پژوهشی دارد. مرکزیت درجه وزن‌دار تنها اتصالات مستقیم را به تصویر می‌کشد، در حالی که پیج‌رنک وزن‌دار اعتبار جهانی را که در کل شبکه منتشر می‌شود، به تصویر می‌کشد. از درجه وزن‌دار برای نفوذ محلی و از پیج‌رنک وزن‌دار برای اهمیت در سطح شبکه استفاده کنید.

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

منابع

  1. Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.

    باز کردن مرجع DOI
    کپی شد.
  2. PageRank. Wikipedia.

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