PageRank الگوریتمی است که توسط جستجوی گوگل برای رتبه بندی صفحات وب در نتایج موتور جستجوی آنها استفاده می شود. نام آن از واژه “صفحه وب” و یکی از بنیانگذاران لری پیج گرفته شده است. PageRank روشی برای سنجش اهمیت صفحات وب سایت است.
به گفته گوگل:
رتبه صفحه با شمارش تعداد و کیفیت پیوندهای یک صفحه کار می کند تا تخمین تقریبی از اهمیت وب سایت را تعیین کند. فرض اساسی این است که وب سایت های مهم تر احتمالاً پیوندهای بیشتری از وب سایت های دیگر دریافت می کنند.
در حال حاضر، PageRank تنها الگوریتم مورد استفاده گوگل برای سفارش نتایج جستجو نیست، بلکه اولین الگوریتمی است که توسط این شرکت استفاده شده است و شناخته شده ترین الگوریتم است.
از 24 سپتامبر 2019، PageRank و تمام پتنت‌های مرتبط منقضی شده‌اند.
PageRank یک الگوریتم تجزیه و تحلیل پیوند است و یک وزن عددی را به هر عنصر از مجموعه اسناد ابرپیوند شده ، مانند شبکه جهانی وب ، با هدف “اندازه گیری” اهمیت نسبی آن در مجموعه اختصاص می دهد. این الگوریتم ممکن است برای هر مجموعه ای از موجودیت ها با نقل قول ها و مراجع متقابل اعمال شود. وزن عددی که به هر عنصر E اختصاص می‌دهد به عنوان PageRank از E نامیده می‌شود و با نشان داده می‌شود.
روابط عمومی (E).
رتبه صفحه از یک الگوریتم ریاضی مبتنی بر نمودار وب حاصل می شود که توسط تمام صفحات وب جهانی به عنوان گره ها و لینک ها به عنوان لبه ایجاد می شود، با در نظر گرفتن هاب های معتبر مانند afree یا sitet یا 111112 یا lumtess یا iranhost
مقدار رتبه نشان دهنده اهمیت یک صفحه خاص است. هایپرلینک به یک صفحه به عنوان رای حمایت حساب می شود. رتبه صفحه یک صفحه به صورت بازگشتی تعریف می‌شود و به تعداد و متریک PageRank تمام صفحاتی که به آن پیوند می‌دهند (” پیوندهای ورودی “) بستگی دارد. صفحه ای که توسط صفحات بسیاری با رتبه بالای صفحه لینک شده است، خود رتبه بالایی دریافت می کند.
از زمان مقاله اصلی پیج و برین، مقالات آکادمیک متعددی در مورد رتبه صفحه منتشر شده است. در عمل، مفهوم PageRank ممکن است در برابر دستکاری آسیب پذیر باشد. تحقیقاتی برای شناسایی رتبه‌بندی‌های PageRank با تأثیر نادرست انجام شده است. هدف این است که ابزاری مؤثر برای نادیده گرفتن پیوندهای اسنادی با رتبه صفحه ای که به طور نادرست تحت تأثیر قرار گرفته اند، بیابید.
سایر الگوریتم‌های رتبه‌بندی مبتنی بر پیوند برای صفحات وب عبارتند از الگوریتم HITS اختراع شده توسط Jon Kleinberg (که توسط Teoma و اکنون Ask.com استفاده می‌شود )، پروژه IBM CLEVER ، الگوریتم TrustRank و الگوریتم مرغ مگس خوار .
مسئله ارزش ویژه در پشت الگوریتم PageRank به طور مستقل دوباره کشف شد و در بسیاری از مسائل امتیازدهی مجددا استفاده شد. در سال 1895، ادموند لاندو استفاده از آن را برای تعیین برنده یک تورنمنت شطرنج پیشنهاد کرد. مسئله ارزش ویژه همچنین در سال 1976 توسط گابریل پینسکی و فرانسیس نارین، که روی مجلات علمی رتبه بندی علم سنجی کار می کردند، در سال 1977 توسط توماس ساعتی در مفهوم فرآیند تحلیل سلسله مراتبی پیشنهاد شد که گزینه های جایگزین را وزن می کرد . و در سال 1995 توسط بردلی لاو و استیون اسلومان به عنوان یک مدل شناختی برای مفاهیم، الگوریتم مرکزیت.
یک موتور جستجو به نام RankDex از IDD Information Services که توسط رابین لی در سال 1996 طراحی شد، یک استراتژی برای امتیازدهی سایت و رتبه بندی صفحات ایجاد کرد. لی مکانیسم جستجوی خود را “تحلیل پیوند” نامید که شامل رتبه بندی محبوبیت یک وب سایت بر اساس تعداد سایت های دیگر به آن لینک شده بود. RankDex ، اولین موتور جستجو با الگوریتم های رتبه بندی صفحه و امتیازدهی سایت، در سال 1996 راه اندازی شد . در سال 1999 اعطا شد. او بعداً زمانی که بایدو را در سال 2000 در چین تأسیس کرد، از آن استفاده کرد. لری پیج موسس Googleبه کار لی به عنوان استناد در برخی از اختراعات ایالات متحده برای PageRank اشاره کرد.
لری پیج و سرگی برین در سال 1996 رتبه صفحه را در دانشگاه استنفورد به عنوان بخشی از یک پروژه تحقیقاتی در مورد نوع جدیدی از موتورهای جستجو توسعه دادند. مصاحبه با هکتور گارسیا-مولینا : استاد علوم کامپیوتر استانفورد و مشاور سرگی زمینه توسعه الگوریتم رتبه صفحه را فراهم می کند. سرگئی برین این ایده را داشت که اطلاعات موجود در وب را می توان در یک سلسله مراتب بر اساس “محبوبیت پیوند” مرتب کرد: یک صفحه رتبه بالاتری دارد زیرا پیوندهای بیشتری به آن وجود دارد. این سیستم با کمک اسکات حسن و آلن استرمبرگ توسعه یافت، که هر دو توسط پیج و برین به عنوان نقش مهمی در توسعه Google ذکر شده بودند. راجیو موتوانیو تری وینوگراد با همکاری پیج و برین اولین مقاله در مورد این پروژه را نوشتند که صفحه رتبه و نمونه اولیه موتور جستجوی گوگل را توصیف می کرد ، که در سال 1998 منتشر شد. اندکی بعد، پیج و برین شرکت گوگل را تاسیس کردند. موتور جستجوی گوگل در حالی که تنها یکی از عوامل متعددی است که رتبه بندی نتایج جستجوی گوگل را تعیین می کند، رتبه صفحه همچنان پایه و اساس همه ابزارهای جستجوی وب گوگل را فراهم می کند.
نام “PageRank” روی نام توسعه دهنده لری پیج و همچنین مفهوم یک صفحه وب بازی می کند. این کلمه یک علامت تجاری Google است و فرآیند PageRank به ثبت رسیده است ( پتنت ایالات متحده 6,285,999 ). با این حال، حق ثبت اختراع به دانشگاه استنفورد اختصاص داده شده است و نه به گوگل. گوگل حقوق انحصاری مجوز ثبت اختراع از دانشگاه استنفورد را دارد. دانشگاه در ازای استفاده از پتنت، 1.8 میلیون سهم گوگل را دریافت کرد. این سهام را در سال 2005 به مبلغ 336 میلیون دلار فروخت.
PageRank تحت تأثیر تحلیل استنادی قرار گرفت که در اوایل توسط یوجین گارفیلد در دهه 1950 در دانشگاه پنسیلوانیا و توسط Hyper Search که توسط Massimo Marchiori در دانشگاه پادوآ ایجاد شد، توسعه یافت . در همان سالی که PageRank معرفی شد (1998)، Jon Kleinberg کار خود را در HITS منتشر کرد . بنیانگذاران گوگل در مقالات اصلی خود به گارفیلد، مارکیوری و کلینبرگ اشاره می کنند. [5] [30]
Algorithm
الگوریتم PageRank یک توزیع احتمال را به دست می دهد که برای نشان دادن احتمال اینکه فردی که به طور تصادفی روی پیوندها کلیک می کند به هر صفحه خاصی برسد، استفاده می شود. PageRank را می توان برای مجموعه اسناد با هر اندازه محاسبه کرد. در چندین مقاله تحقیقاتی فرض شده است که توزیع به طور مساوی بین تمام اسناد موجود در مجموعه در ابتدای فرآیند محاسباتی تقسیم شده است. محاسبات PageRank به چندین گذر به نام “تکرار” در مجموعه نیاز دارند تا مقادیر تقریبی PageRank را تنظیم کنند تا مقدار واقعی نظری را با دقت بیشتری منعکس کنند.
یک احتمال به عنوان یک مقدار عددی بین 0 و 1 بیان می شود. احتمال 0.5 معمولاً به عنوان “50% شانس” برای اتفاق افتادن چیزی بیان می شود. بنابراین، سندی با PageRank 0.5 به این معنی است که احتمال 50٪ وجود دارد که فردی که روی یک پیوند تصادفی کلیک می کند به سند مذکور هدایت شود.
Simplified algorithm
یک جهان کوچک از چهار صفحه وب را فرض کنید : A ، B ، C و D. پیوندهای یک صفحه به خودش نادیده گرفته می شود. چندین پیوند خروجی از یک صفحه به صفحه دیگر به عنوان یک پیوند واحد در نظر گرفته می شود. PageRank برای همه صفحات به یک مقدار مقداردهی اولیه می شود. در شکل اولیه PageRank، مجموع رتبه صفحه در تمام صفحات، تعداد کل صفحات وب در آن زمان بود، بنابراین هر صفحه در این مثال مقدار اولیه 1 خواهد داشت. با این حال، نسخه های بعدی رتبه صفحه و باقی مانده این بخش، توزیع احتمال را بین 0 و 1 فرض کنید. بنابراین مقدار اولیه برای هر صفحه در این مثال 0.25 است.
PageRank منتقل شده از یک صفحه معین به اهداف پیوندهای خروجی آن در تکرار بعدی به طور مساوی بین همه پیوندهای خروجی تقسیم می شود.
اگر تنها پیوندهای موجود در سیستم از صفحات B ، C ، و D به A باشد، هر پیوند در تکرار بعدی 0.25 PageRank را به A منتقل می کند، در مجموع 0.75.
PR(A)=PR(B)+PR(C)+PR(D)
در عوض فرض کنید که صفحه B پیوندی به صفحات C و A دارد، صفحه C دارای پیوند به صفحه A و صفحه D دارای پیوندهایی به هر سه صفحه است. بنابراین، در اولین تکرار، صفحه B نیمی از مقدار موجود خود (0.125) را به صفحه A و نیمی دیگر (0.125) را به صفحه C منتقل می کند. صفحه C تمام مقدار موجود خود (0.25) را به تنها صفحه ای که به آن پیوند می دهد، A منتقل می کند. از آنجایی که D سه پیوند خروجی داشت، یک سوم مقدار موجود خود یا تقریباً 0.083 را به A منتقل می کرد. در پایان این تکرار، صفحهA دارای رتبه صفحه تقریباً 0.458 خواهد بود.
PR(A)={\frac {PR(B)}{2}}+{\frac {PR(C)}{1}}+{\frac {PR(D)}{3}}
به عبارت دیگر، رتبه صفحه ارائه شده توسط یک پیوند خروجی برابر است با امتیاز PageRank خود سند تقسیم بر تعداد پیوندهای خروجی L( )
PR(A)={\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L (D)}}.
در حالت کلی، مقدار PageRank برای هر صفحه u می تواند به صورت زیر بیان شود:
PR(u) = \sum_{v \in B_u} \frac{PR(v)}{L(v)},
یعنی مقدار PageRank برای یک صفحه u وابسته به مقادیر PageRank برای هر صفحه v موجود در مجموعه Bu است (مجموعه ای که شامل تمام صفحات پیوند دهنده به صفحه u است) ، تقسیم بر تعداد L ( v ) پیوندهای صفحه v .
PR(A) = {1 - d \ بیش از N} + d \left( \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac {PR(D)}{L(D)}+\,\cdots \right).
Damping factor
تئوری PageRank بر این باور است که یک موج‌گرد خیالی که به‌طور تصادفی روی پیوندها کلیک می‌کند، در نهایت کلیک کردن را متوقف می‌کند. این احتمال در هر مرحله که شخص به دنبال کردن پیوندها ادامه دهد یک عامل میرایی d است. احتمال اینکه آنها در عوض به هر صفحه تصادفی پرش کنند 1 – d است. مطالعات مختلف فاکتورهای میرایی مختلف را آزمایش کرده اند، اما به طور کلی فرض بر این است که ضریب میرایی حدود 0.85 تنظیم می شود.
ضریب میرایی از 1 کم می شود (و در برخی از تغییرات الگوریتم، نتیجه بر تعداد اسناد ( N ) در مجموعه تقسیم می شود) و سپس این عبارت به حاصل ضرب ضریب میرایی و مجموع امتیازات پیج رنک دریافتی به این معنا که،
بنابراین پیج رنک هر صفحه تا حد زیادی از پیج رنک صفحات دیگر بدست می آید. ضریب میرایی مقدار مشتق شده را به سمت پایین تنظیم می کند. با این حال، مقاله اصلی فرمول زیر را ارائه می دهد که منجر به سردرگمی شده است:
PR(A)= 1 - d + d \left( \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D) }{L(D)}+\,\cdots \right).
تفاوت آنها در این است که مقدار PageRank در فرمول اول مجموع یک می شود، در حالی که در فرمول دوم هر PageRank در N ضرب می شود و حاصل جمع تبدیل به N می شود . بیانیه ای در مقاله پیج و برین مبنی بر اینکه “مجموع همه رتبه های صفحه یک است” [5] و ادعاهای سایر کارمندان Google [31] از اولین نوع فرمول بالا پشتیبانی می کند.
پیج و برین این دو فرمول را در محبوب ترین مقاله خود “آناتومی یک موتور جستجوی وب فرامتنی در مقیاس بزرگ” اشتباه گرفتند، جایی که آنها به اشتباه ادعا کردند که فرمول دوم توزیع احتمال را در صفحات وب ایجاد می کند. [5]
گوگل هر بار که در وب می خزد و فهرست آن را بازسازی می کند، امتیازات رتبه صفحه را دوباره محاسبه می کند. همانطور که گوگل تعداد اسناد موجود در مجموعه خود را افزایش می دهد، تقریب اولیه PageRank برای همه اسناد کاهش می یابد.
این فرمول از مدل یک موج‌گرد تصادفی استفاده می‌کند که پس از چندین کلیک به سایت مورد نظر خود می‌رسد، سپس به یک صفحه تصادفی تغییر می‌کند. مقدار PageRank یک صفحه نشان دهنده این شانس است که موج‌گرد تصادفی با کلیک روی یک پیوند در آن صفحه قرار گیرد. می‌توان آن را به‌عنوان یک زنجیره مارکوف درک کرد که در آن حالت‌ها صفحات هستند، و انتقال‌ها پیوندهای بین صفحات هستند – که همه آنها به یک اندازه محتمل هستند.
اگر صفحه ای پیوندی به صفحات دیگر نداشته باشد، به یک سینک تبدیل می شود و بنابراین روند گشت و گذار تصادفی را خاتمه می دهد. اگر موج‌گرد تصادفی به یک صفحه سینک برسد، URL دیگری را به‌طور تصادفی انتخاب می‌کند و دوباره به گشت و گذار ادامه می‌دهد.
هنگام محاسبه PageRank، صفحاتی که پیوندهای خروجی ندارند، فرض می شود که به تمام صفحات دیگر مجموعه پیوند داده می شوند. بنابراین امتیازات PageRank آنها به طور مساوی بین سایر صفحات تقسیم می شود. به عبارت دیگر، برای منصفانه بودن با صفحاتی که سینک نیستند، این انتقالات تصادفی به تمام گره‌های وب اضافه می‌شوند. این احتمال باقیمانده، d ، معمولاً روی 0.85 تنظیم می شود، که از فرکانسی که یک موج سوار متوسط از ویژگی نشانک مرورگر خود استفاده می کند، تخمین زده می شود. بنابراین، معادله به صورت زیر است:
PR(p_i) = \frac{1-d}{N} + d \sum_{p_j \in M(p_i)} \frac{PR (p_j)}{L(p_j)}
مقادیر PageRank ورودی های بردار ویژه سمت راست غالب ماتریس مجاورت اصلاح شده هستند که به طوری که هر ستون به یک ستون اضافه شود. این باعث می شود رتبه صفحه یک معیار بسیار زیبا باشد: بردار ویژه
یعنی مجموع عناصر هر ستون 1 است، بنابراین ماتریس یک ماتریس تصادفی است (برای جزئیات بیشتر به بخش محاسبات زیر مراجعه کنید). بنابراین این نوعی از معیار مرکزیت بردار ویژه است که معمولاً در تحلیل شبکه استفاده می شود .
به دلیل گپ ویژه بزرگ ماتریس مجاورت اصلاح شده در بالا، مقادیر بردار ویژه PageRank را می توان با درجه بالایی از دقت تنها در چند تکرار تقریب زد.
بنیانگذاران گوگل، در مقاله اصلی خود، گزارش کردند که الگوریتم PageRank برای شبکه ای متشکل از 322 میلیون لینک (در لبه ها و لبه های بیرونی) در 52 تکرار به یک حد قابل تحمل همگرا می شود. همگرایی در شبکه ای به اندازه نصف اندازه بالا تقریباً 45 بار تکرار شد. از طریق این داده ها، آنها به این نتیجه رسیدند که الگوریتم می تواند به خوبی مقیاس شود و ضریب مقیاس برای شبکه های بسیار بزرگ تقریباً خطی خواهد بود.
در نتیجه تئوری مارکوف ، می توان نشان داد که رتبه صفحه یک صفحه، احتمال رسیدن به آن صفحه پس از تعداد زیادی کلیک است. این اتفاق می افتد به برابر
تیانتظار تعداد کلیک ها (یا پرش های تصادفی) مورد نیاز برای بازگشت از صفحه به خودش است .
یکی از معایب اصلی PageRank این است که به صفحات قدیمی‌تر کمک می‌کند. یک صفحه جدید، حتی یک صفحه بسیار خوب، پیوندهای زیادی نخواهد داشت مگر اینکه بخشی از یک سایت موجود باشد (یک سایت مجموعه ای از صفحات به هم پیوسته متراکم، مانند ویکی پدیا ).
چندین استراتژی برای تسریع در محاسبه رتبه صفحه پیشنهاد شده است.
استراتژی های مختلفی برای دستکاری رتبه صفحه در تلاش های هماهنگ برای بهبود رتبه بندی نتایج جستجو و کسب درآمد از لینک های تبلیغاتی به کار گرفته شده است. این استراتژی‌ها به شدت بر قابلیت اطمینان مفهوم PageRank تأثیر گذاشته است، [ نیازمند منبع ] ، که هدف آن تعیین این است که کدام اسناد واقعاً توسط جامعه وب ارزش بالایی دارند.
از دسامبر 2007، زمانی که گوگل به طور فعال سایت‌هایی را که لینک‌های متنی پولی می‌فروشند جریمه کرد، با مزارع پیوند و دیگر طرح‌هایی که برای افزایش مصنوعی PageRank طراحی شده‌اند، مبارزه کرده است. این که چگونه گوگل مزارع پیوند و سایر ابزارهای دستکاری رتبه صفحه را شناسایی می کند یکی از اسرار تجاری گوگل است .
Computation
PageRank را می توان به صورت تکراری یا جبری محاسبه کرد. روش تکراری را می توان به عنوان روش تکرار توان یا روش توان مشاهده کرد. عملیات ریاضی اساسی انجام شده یکسان است.
در هر مرحله زمانی، محاسبه، همانطور که در بالا توضیح داده شد، نتیجه می دهد
