الگوریتم پیج رنک چیست ؟

الگوریتم پیج رنک گوگل
زمان مطالعه مطلب : 5 دقیقه
  • الگوریتم PageRank یا الگوریتم گوگل رنک یکی از الگوریتم های گوگل است که توسط لری پیج یکی از بنیانگذاران گوگل معرفی شد.  اولین بار برای رتبه بندی صفحات وب در موتور جستجوی گوگل استفاده شد.  امروزه بیشتر و بیشتر در زمینه های مختلف استفاده می شود، به عنوان مثال در رتبه بندی کاربران در رسانه های اجتماعی و غیره… چیزی که در الگوریتم PageRank جذاب است این است که چگونه از یک مسئله پیچیده شروع کنیم و به یک راه حل بسیار ساده ختم کنیم.  در این پست ایده و تئوری الگوریتم PageRank را به شما آموزش می دهم.  شما فقط باید اصولی در جبر و زنجیره مارکوف داشته باشید.  در اینجا، ما از رتبه بندی صفحات وب به عنوان یک مورد استفاده برای نشان دادن الگوریتم PageRank استفاده می کنیم.

    وب را می توان مانند یک نمودار جهت دار نشان داد که در آن گره ها صفحات وب را نشان می دهند و لبه ها پیوندهای بین آنها را تشکیل می دهند.  به طور معمول، اگر یک گره (صفحه وب) i به یک گره j مرتبط باشد، به این معنی است که i به j اشاره دارد.

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

    جایی که rᵢ امتیاز گره i و dᵢ خارج از درجه آن است.

    از مثال بالا می توانیم این سیستم خطی را بنویسیم:

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

    الگوریتم پیج رنک
    الگوریتم پیج رنک

    زنجیره مارکوف و رتبه صفحه

    از آنجایی که یک زنجیره مارکوف با یک توزیع اولیه و یک ماتریس انتقال تعریف می شود، نمودار فوق را می توان به عنوان یک زنجیره مارکوف با ماتریس انتقال زیر مشاهده کرد:

    متوجه شدیم که P transpose یک ردیف تصادفی است که شرطی برای اعمال قضایای زنجیره مارکوف است.

    برای توزیع اولیه، در نظر بگیرید که برابر است با

    که در آن n تعداد کل گره‌ها است.  این بدان معنی است که واکر تصادفی به طور تصادفی گره اولیه را انتخاب می کند که از آنجا می تواند به تمام گره های دیگر برسد.

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

    توزیع ثابت یک زنجیره مارکوف، توزیع احتمال π با π = Pπ است.  این بدان معنی است که توزیع پس از یک مرحله تغییر نخواهد کرد.  توجه به این نکته مهم است که همه زنجیره های مارکوف توزیع ثابت را قبول ندارند

    اگر یک زنجیره مارکوف به شدت متصل باشد، به این معنی که می توان به هر گره ای از هر گره دیگری دسترسی داشت، آنگاه توزیع ثابت را می پذیرد.  در مشکل ما هم همینطور است.  بنابراین، پس از یک پیاده روی بی نهایت طولانی، می دانیم که توزیع احتمال به توزیع ثابت π همگرا می شود.

    متوجه شدیم که π بردار ویژه ماتریس P با مقدار ویژه 1 است. به جای محاسبه همه بردارهای P و انتخاب موردی که با مقدار ویژه 1 مطابقت دارد، از قضیه فروبنیوس-پرون استفاده می‌کنیم.

    طبق قضیه فروبنیوس-پرون، اگر یک ماتریس A یک ماتریس مربع و مثبت باشد (همه ورودی‌های آن مثبت هستند)، آنگاه مقدار ویژه r مثبت دارد، مانند |λ|  < r، که در آن λ  مقدار ویژه A است. بردار ویژه v A با مقدار ویژه r مثبت است و بردار ویژه مثبت منحصر به فرد است.

    در مورد ما، ماتریس P مثبت و مربع است.  توزیع ثابت π  لزوماً مثبت است زیرا یک توزیع احتمال است.  نتیجه می گیریم که π بردار ویژه  غالب P با مقدار ویژه 1 است.

    برای محاسبه π، از تکرار روش توان استفاده می‌کنیم که یک روش تکراری برای محاسبه بردار ویژه غالب ماتریس A است. از تقریب اولیه بردار ویژه غالب b که می‌تواند به‌طور تصادفی مقداردهی اولیه شود، الگوریتم آن را تا زمان همگرایی با استفاده از  الگوریتم زیر:

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

    پیج رنک چیست
    پیج رنک چیست

    انتقال از راه دور و عامل میرایی

    برای مثال، در نمودار وب، می‌توانیم یک صفحه وب i پیدا کنیم که فقط به صفحه وب j و j فقط به i اشاره دارد.  این همان چیزی است که ما آن را مشکل تله عنکبوت می نامیم.  ما همچنین می توانیم یک صفحه وب را پیدا کنیم که هیچ لینک خروجی ندارد.  معمولاً به آن «بن بست» می گویند

    در مورد تله عنکبوتی، وقتی واکر تصادفی به گره 1 در مثال بالا می رسد، فقط می تواند به گره 2 بپرد و از گره 2، فقط می تواند به گره 1 و غیره برسد.  اهمیت همه گره های دیگر توسط گره های 1 و 2 گرفته می شود. در مثال بالا، توزیع احتمال به π = (0، 0.5، 0.5، 0) همگرا می شود.  این نتیجه مطلوب نیست.

    در مورد Dead end‌ها، وقتی واکر به گره 2 می‌رسد، نمی‌تواند به هیچ گره دیگری برسد، زیرا هیچ لینک خروجی ندارد.  الگوریتم نمی تواند همگرا شود

    برای غلبه بر این دو مشکل، مفهوم انتقال از راه دور را معرفی می کنیم.

    انتقال از راه دور شامل اتصال هر گره از گراف به تمام گره های دیگر است.  سپس نمودار کامل خواهد شد.  ایده این است که با یک احتمال مشخص β، واکر تصادفی طبق ماتریس انتقال P به گره دیگری می‌پرد و با احتمال (1-β)/n، به طور تصادفی به هر گره در نمودار می‌پرد.  سپس ماتریس انتقال جدید R را دریافت می‌کنیم:

    که در آن v بردار یکها و e بردار 1/n است

    β معمولاً به عنوان عامل میرایی تعریف می شود.  در عمل، توصیه می شود β را روی 0.85 تنظیم کنید.

    ماتریس R دارای ویژگی‌های یکسانی با P است، به این معنی که توزیع ثابت را می‌پذیرد، بنابراین می‌توانیم از همه قضایایی که قبلاً دیدیم استفاده کنیم.

    این برای الگوریتم PageRank است.  امیدوارم شهود و نظریه پشت الگوریتم PageRank را درک کرده باشید.

    میانگین امتیازات ۵ از ۵
    از مجموع ۱ رای

    دیدگاهتان را بنویسید