نگاهی به محاسبه پیج‌ رنک و مفهوم زنجیره مارکوف

در عصر دیجیتال، جستجو کردن در فضای وب به بخشی جدایی ناپذیر از زندگی روزمره ما تبدیل شده است. یکی از چالش‌های اساسی در بازیابی اطلاعات (Information Retrieval) رتبه بندی صفحات وب برای ارائه مرتبط‌ترین نتایج به کاربران است. در این مقاله، مفهوم پیج رنک (Page Rank) و رابطه آن با زنجیره مارکوف (Markov chain)، دو مولفه حیاتی در الگوریتم رتبه بندی صفحات وب را بررسی خواهیم کرد و نحوه سنجش اهمیت صفحات وب را بیشتر متوجه خواهیم شد.

نمایی کلی از پیج رنک

پیج رنک یک الگوریتم کلیدی است که در رتبه بندی صفحات وب استفاده می‌شود. این الگوریتم توسط Larry Page و Sergey Brin بنیان گذاران گوگل توسعه یافته است. ایده پشت پیج رنک، تعیین اهمیت یک صفحه وب بر اساس لینک‌هایی است که به آن اشاره می‌کنند.

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

تعداد لینک‌ها و محبوبیت (Link counts and popularity)

یکی از راه‌های سنجش محبوبیت (Popularity) یک صفحه وب، شمارش تعداد لینک‌هایی است که به آن اشاره می‌کنند. این معیار ساده که به شکل محبوبیت بدون جهت (Undirected popularity) است، به عنوان degree شناخته می‌شود و لینک‌های ورودی و خروجی را در نظر می‌گیرد. به عنوان مثال اگر یک صفحه دارای سه لینک ورودی و دو لینک خروجی باشد، degree آن پنج است.

از طرف دیگر، می‌توان فقط تعداد لینک‌های ورودی را در نظر گرفت، که می‌توان آن را به عنوان یک معیار جهت‌دار محبوبیت (Directed of popularity) دانست.

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

شهود پیج رنک

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

مثلا در تصویر بالا در Node E، شش لینک از Node های دیگر گرفته و چند لینک هم داده است. اما Node c فقط یک لینک گرفته و آن هم از Node B است و همانطور که می‌بینیم Node c از E بزرگ‌تر است.

مفاهیم Random walk و Teleporting

مرورگری را تصور کنید که به صورت تصادفی درون صفحات وب می‌چرخد یا به اصطلاح راه می‌رود و قدم می‌زند، به این مفهوم Random walk می‌گویند که در فارسی به آن ولگشت، گام تصادفی، گشت تصادفی، قدم‌زدن تصادفی گفته می‌شود و از این به بعد در این مقاله به این رفتار "ولگشت" می‌گوییم.

ما از یک صفحه تصادفی شروع می‌کنیم و در هر مرحله، احتمالا در امتداد یکی از لینک‌های موجود در صفحه از آن خارج می‌شویم. حال اگر یک صفحه دارای سه لینک باشد، بنابراین با احتمال 1/3 ، وارد لینک اول می‌شویم، با احتمال 1/3، در امتداد لینک دوم وارد می‌شویم و به همین شکل هم 1/3 برای لینک سوم است.

بنابراین شهود پیج رنک این است که، در حالت ثابت یا ایستا (Steady state) پس از ولگشت‌های زیاد، هر صفحه دارای نرخ بازدید طولانی مدتی (Long term visit rate) می‌شود و از این مفهوم برای عنوان پیج رنک استفاده می‌کنیم.

پس برای محاسبه پیج رنک از یک الگوریتم تکراری استفاده می‌شود که یک پیاده روی تصادفی یا ولگشت (Random walk) در صفحات وب را شبیه سازی می‌کند. در این ولگشت، وبگرد (Surfer) از یک صفحه شروع می‎‌‌کند و احتمالا لینک‌ها را دنبال می‌کند.

با این حال این ولگشت کافی نیست، زیرا ممکن است در صفحات بن بست (Dead end page) گیر کند. برای غلبه بر این موضوع پیج رنک، ،تله پورت (Teleporting) را معرفی می‌کند. وقتی وب گرد به یک صفحه بن بست رسید، با احتمال خاصی به یک صفحه تصادفی می‌پرد و از گیر نکردن آن اطمینان می‌دهد.

اگر ما در یک صفحه غیر بن بست (None dead end page) باشیم با احتمال 10 درصد ممکن است که به یک صفحه تصادفی پرش کنیم و با احتمال باقی مانده 90 درصد ما به داخل یکی از لینک‌های صفحه خواهیم رفت.

آن 10 درصد احتمال یک پارامتر است که آن را آلفا (ɑ) می‌نامیم. بنابراین تله پورت (Teleport) به این معنی است که نمی‌توانیم به صورت لوکالی گیر کنیم و همچنین این امکان را به ما می‌دهد که پیج رنک را برای هر صفحه‌ای که از آن یک نرخ بازدید بلند مدت داریم، محاسبه کنیم. برای اینکه بفهمیم چگونه این محاسبه را انجام دهیم، باید با زنجیره‌های مارکوف (Markov chains) شروع کنیم.

زنجیره‌ مارکوف چیست؟

زنجیره مارکوف یک مدل ریاضی است و برای توصیف دنباله‌ای از رویداد‌ها یا حالت‎‌ها به کار می‌رود که در آن فقط به وضعیت فعلی بستگی دارد و مستقل از چگونگی رسیدن زنجیره به آن حالت است. پس این حالت یک فرآیند تصادفی است که از ویژگی مارکوف پیروی می‌کند و بیان دارد که رفتار آینده سیستم فقط به وضعیت فعلی آن بستگی دارد و به تاریخچه حالات قبل از آن ارتباطی ندارد.

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

برای درک بیشتر مفهوم آن یک مثال داشته باشیم. فرض کنید یک مدل آب و هوایی دارید که می‌تواند در یکی از این سه حالت باشد: آفتابی، ابری یا بارانی

احتمال بین این حالت‌ها فقط به آب و هوای فعلی بستگی دارد. به عنوان مثال ، اگر در حال حاضر هوا آفتابی است، احتمال 0.6 برای آفتابی ماندن در روز بعد، 0.3 احتمال برای تبدیل شدن به یک روز ابری و 0.1 احتمال انتقال به یک روز بارانی وجود دارد.

با شبیه‌سازی این زنجیره مارکوف در چند روز، می‌توانید رفتار بلند مدت آب‌و‌هوا را بر اساس وضعیت فعلی آن پیش بینی کنید.

مثال دیگری که می‌توان زد راجب پرتاب سکه و شیر یا خط آمدن آن است. مهم نیست در پی تلاش‌های گذشته چندبار شیر یا خط آمده است و فقط State حال حاضر مهم است که هر کدام با احتمال 50 درصد ممکن است شیر یا خط بیاید.

حال به ارتباط زنجیره مارکوف و پیج رنک برمی‌گردیم. یک زنجیره مارکوف:

1. دارای N حالت است. (N state) N در واقع تعداد صفحات موجود است.

2. شامل یک ماتریس N × N برای احتمال انتقال (P) است.

همچنین باید بدانیم که:

_ در هر مرحله از زنجیره مارکوف، ما در یکی از حالت‌ها (States) هستیم.

_ برای 1 ≤ i, j ≤ n، ماتریس ورودی Pij (i و j اندیس‌های p هستند ) به ما P(j|i) را می‌دهد و اینکه j، حالت بعد i باشد اگر در حال حاضر در حالت i باشیم را معلوم می‌کند.

در واقع به زبان ساده تر، اگر ما در حالت i باشیم، با چه احتمالی (P) به حالت بعدی یعنی j می‌رویم.

حال اگر تمام احتمالات i به j را جمع کنیم، جمع آن‌ها باید 1 شود. مثلا اگر در صفحه سه لینک خروجی داریم و احتمال هر کدام 1/3 باشد، مجموع این 3 احتمال ( 1 = 1/3 + 1/3 + 1/3) باید 1 باشد. پس برای همه i ها داریم:

• در این‌جا سیگما ( ∑ ) به معنای مجموع تمام احتمالات حالت‌ها است.

برای تفهیم بهتر مطلب مثالی بزنیم. مثلا یک زنجیره کوچک مارکوف داریم. در این زنجیره سه گره (Node) داریم. (A, B, C)

بنابراین اگر در A باشیم، احتمال رفتن به B، نیم (0.5) است. احتمال رفتن به C، نیم (0.5) است. اگر در C باشیم قطعا به A خواهیم رفت و اگر در B باشیم، قطعا به A خواهیم رفت. پس این دو احتمال هم در اینجا 1 می‌باشد.

پس در اینجا می‌توانیم ماتریس احتمال انتقال (P) را به این شکل بسازیم.

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

وبگرد تصادفی و زنجیره مارکوف (Random Surfer and Markov chain)

بنابراین یک زنجیره مارکوف، نوعی abstraction از یک Random walk است و ما از آن برای صحبت در مورد وبگردی که به صورت تصادفی در فضای وب می‌چرخد استفاده خواهیم کرد.

با این تفاصیل هر حالت (State) از زنجیره مارکوف، باید نمایانگر یکی از صفحات وب باشد و احتمال انتقال (Pij) نشان‌دهنده احتمال انتقال از یک صفحه وب به صفحه دیگر خواهد بود.

اکنون می‌توانیم ماتریس احتمال انتقال P را از روی ماتریس مجاورت گراف وب (Web graph) تولید کنیم. ماتریس مجاورت (Adjacency Matrix) فقط شامل 1 و 0 است. اگر دو صفحه به هم لینک داشته باشند درایه (به هر کدام از مقدارهای درون ماتریس گفته می‌شود ) آن 1 می‌شود و اگر نداشته باشند 0 است.

تله پورت (Teleporting)

1. اگر در یک گره (Node) وب باشیم و گره هیچ لینک بیرونی نداشته باشد، وبگرد تصادفی (Random surfer) تله‌پورت می‌کند و احتمال انتقال به هر گره در کل گراف وب برابرست با 1/N ( در اینجا یک بر روی N است و ویرگول به این شکل نمایش می‌دهد)

بنابراین اگر N صفحه در وب وجود دارد و ما در یک صفحه بن بست (Dead end page) قرار داریم، با احتمال 1/N ( در اینجا یک بر روی N است) به هر صفحه دیگری در کل وب خواهیم رفت.

2. در حالت بعدی اگر یک Node لینک‌های خروجی داشته باشد، فرضا تعداد K تا (k>0) لینک خروجی دارد، آنگاه با احتمال 1/N (در اینجا یک بر روی N است) ، Surfer به یک گره تصادفی تله‌پورت خواهد کرد و احتمال آن از آن‌جایی که N گره وب وجود دارد، ɑ/N است.

3. همچنین برای احتمال باقی‌مانده (ɑ -1)، یک ولگشت معمولی خواهیم داشت (یعنی تله‌پورت نداریم) و همانطور که گفتیم K لینک خروجی از این صفحه خاص وجود دارد، بنابراین احتمال آن K(ɑ - 1) است.

استخراج ماتریس احتمال انتقال P از ماتریس مجاورت A

فرض کنید ماتریس مجاورت گراف وب را داشتیم. بنابراین Aij ( i و j اندیس‌های A هستند که در اینجا منظور همان یکی از درایه‌های ماتریس A است و i، j سطر و ستون این ماتریس می‌باشد ) برابراست با 1 اگر لینکی از صفحه i به j وجود داشته باشد.در واقع این ماتریسی صفر و یک است که ساختار وب را بیان می‌کند.

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

پس اگر این کیس ما باشد، می‌توانیم هر درایه این ماتریس را با 1/N (در اینجا یک بر روی N است) جایگزین کنیم و احتمال رفتن به هر مکانی از آن صفحه 1/N (در اینجا هم یک بر روی N است) است.

برای سطر‌های دیگر یعنی سطر‌هایی که دارای لینک خارجی هستند، به این صورت عمل می‌کنیم:

1. اول شروع می‌کنیم به نرمالایز کردن یا همون نرمال‌سازی (Normalize)

نرمالیزه یا نرمال سازی داده‌ها به معنای مقیاس کردن مقادیر به گونه ای است که محدوده مقادیر سطر یا ستون بین 0 و 1 باشد. بنابراین هر 1 را در ماتریس A به تعداد یک‌هایی که در ردیف خودش است، تقسیم می‌کنیم. مثلا اگر در یک ردیف 3 تا یک وجود دارد، آنگاه یک‌های آن ردیف را تقسیم بر 3 می‌کنیم.

2. در قدم دوم ماتریس نهایی را در (ɑ-1) ضرب می‌کنیم، به این دلیل که می‌خواهیم به یک گره تصادفی از گره‌ای که در آن هستیم وارد شویم.

3. درقدم آخر هم مقدار ɑ/N را به هر ورودی ماتریس نتیجه اضافه می‌کنیم تا مقدار ماتریس P را بدست آوریم.

بنابراین با ɑ/N ما به مکان تصادفی دیگری می‌رویم. حال با یک مثال عملی این محاسبات را بررسی کنیم.

محاسبه احتمال انتقال با تله‌پورت

در این‌جا مثال کوچکی از وب با سه Node را داریم (1, 2, 3). همانطور که مشاهده می‌کنید، ما می‌توانیم از 1 به 2 برویم، از 2 به 3 برویم، از 3 به 2 برویم و از 2 به 1 برویم. پس ماتریس مجاورت (Adjacency matrix) به این شکل خواهد بود.

پس در واقع ماتریس A به این صورت شد:

حال چطور ماتریس احتمال انتقال P را از این ماتریس مجاورت A بدست آوریم.

ابتدا با مثال ساده‌تری شروع می‌کنیم که در آن 0 = ɑ است. به این معنی که تله‌پورت وجود ندارد. در این صورت، تمام کاری که ما برای محاسبه P باید انجام دهیم این است که ماتریس A را به یک ماتریس احتمال Normalize کنیم. بنابراین مجموع هر ردیف به 1 می‌رسد، زیرا لینک‌های خروجی از هر گره باید احتمالی باشد که در آن به هر لینک با احتمال خودش می‌رویم.

اگر به ماتریس A نگاهی بیندازیم، در ردیف اول و سوم، مجموع درایه‌های ماتریس، 1 است. پس این ردیف‌ها نرمالایز شده‌اند. اما در ردیف دوم مجموع درایه‌های آن 2 می‌شود و نیاز به نرمالایز کردن دارد. پس طبق چیزی که در قبل گفتیم باید هر کدام از یک‌ها تقسیم بر تعداد یک‌های آن ردیف شود و از آن‌جایی که ردیف دوم 2 تا یک دارد، پس هر کدام تقسیم بر 2 می‌شوند و ماتریس به این شکل در می‌آید.

اکنون در مثال بعدی فرض کنیم که تله‌پورت داریم و ɑ = 0.5 است. پس با فرض ɑ = 0.5 به این شکل آن را برای ردیف اول حساب می‌کنیم.

ما گفتیم که با احتمال ɑ، می‌توانیم به هر مکانی در وب تله‌پورت کنیم و در این مثال گراف وب کوچک ما سه گره وجود دارد، پس N = 3 است.

بنابراین با احتمال ɑ بردار ɑ (1/N 1/N 1/N) را داریم و با احتمال (1 - ɑ) بردار (1 - ɑ) (0 1 0) را داریم که در واقع به هر گره با احتمال لینک خارجی آن می‌رویم. در ردیف اول و از گره 1 فقط به گره 2 می‌توانیم برویم که احتمالش را 1 گذاشتیم. بنابراین با (1 - ɑ) مجموعه‌ای از انتقال‌ها را می‌گیریم.

پس در واقع همانطور که در گذشته گفتیم دو حالت داریم. یک حالت ɑ است که Surfer تله‌پورت می‌کند و حالت بعدی (1 - ɑ) است که Surfer یک ولگشت معمولی خواهد داشت و از آن‌جایی که گفتیم ɑ = 0.5 است در ادامه به این شکل خواهد شد.

اگر آن را برای تمامی ردیف‌ها حساب کنیم، ماتریس نهایی به این شکل می‌شود.

شروع محاسبه پیج رنک

برای نشان دادن احتمال بودن در یک State از برداری به نام X استفاده می‌کنیم. بردار X به ما می‌گوید که در یک ولگشت یا پیاده‌روی تصادفی در هر نقطه کجا هستیم.

X = (x1, ……..Xn)

برای مثال ما می‌توانیم بگوییم که در یک حالت هستیم یا نیستیم. بنابراین وقتی می‌گوییم در حالت i هستیم به این معنی است.

ما می‌توانیم آن را تعمیم دهیم که به جای استفاده از 0 و 1، بردار X = (x1, ……..Xn) را به عنوان احتمالات داشته باشیم. این بردار احتمال به ما می‌گوید احتمال اینکه Surfer در هر نقطه در حالت i باشد چقدر است و البته که مجموع این Xi ها باید 1 شود، چون مجموع همه احتمالات باید یک باشد.

مثلا بردار (0.3 0.4 0.3) برداری خواهد بود که که هر کدام از اعداد می‌گویند با چه احتمالی ما می‌توانیم کجای راه باشیم. بنابراین اگر بردار احتمال ما یک بردار خاص X باشد و مجموعه‌ای از مقادیر مشخص داشته باشد X = (X1, ….Xn) ، وضعیت فعلی ما، جاییکه در آن قرار داریم، بر روی مکان‌های احتمالی که می‌توانیم باشیم توزیع شده است.

قدم بعدی گام تصادفی چیست؟

ماتریس احتمال انتقال P دقیقا طوری طراحی شده است که بگوید از حالت i به کجا برویم. بنابراین اگر در حال حاضر در حالت X هستیم (X توزیع بر روی مکان‌هایی است که می‌توانیم باشیم)، آنگاه حالت بعدی با XP توزیع می‌شود.پس ما فقط X را در ماتریس احتمال انتقال P ضرب می‌کنیم و این مقدار به ما می‌گوید احتمال توزیع بر روی حالت‌ها در قدم بعدی چیست.

پروسه ارگودیک چیست؟

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

حال یک مثال ساده برای نشان دادن مفهوم یک سیستم ارگودیک می‌زنیم.

مثال: چرخش عادلانه سکه

یک سکه عادلانه را در نظر بگیرید که می تواند شیر (S) یا خط (K) را با احتمال مساوی (50٪ احتمال هر کدام) فرود آورد. این چرخاندن سکه را می‌توان به عنوان یک سیستم ارگودیک ساده در نظر گرفت.

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

S

K

S

S

K

K

S

K

اگر میانگین تعداد دفعاتی که شیر می‌اید را حساب کنیم:

(1 + 0 + 1 + 1 + 0 + 0 + 1 + 0) / 8 = 4 / 8 = 0.5

بنابراین میانگین شیر آمدن در این بازه زمانی 0.5 است.

اکنون میانگین مجموعه را در نظر بگیریم، که به معنی در نظر گرفتن تمام نتایج ممکن از سکه است. در این مورد، دو نتیجه ممکن وجود دارد H :و T، هر کدام با احتمال 0.5.

میانگین مجموعه به صورت زیر محاسبه می شود:

(0.5 * 0) + (0.5 * 1) = 0 + 0.5 = 0.5

میانگین مجموعه 0.5 برای آمدن شیر است.

در این مثال ساده شده، میانگین زمانی (0.5 شیر) و میانگین مجموعه (0.5 شیر) برابر هستند، زیرا ما تعداد نسبتاً کمی از چرخش‌های سکه را در نظر گرفته‌ایم. در سیستم‌های ارگودیک، با در نظر گرفتن چرخش‌های بیشتر و بیشتر در یک دوره طولانی‌تر، میانگین زمانی به میانگین مجموعه نزدیک می‌شود، که مفهوم اساسی ارگودیسیته است.

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

اگر می‌خواهید مثال دیگری را در مورد یک پروسه ارگودیک ببینید، پیشنهاد می‌کنم 7 دقیقه ابتدایی این ویدیو را مشاهده کنید.

حال به سراغ مفهوم ارگودیک در الگوریتم پیج رنک برویم.

زنجیره مارکوف ارگودیک

یک زنجیره مارکوف ارگودیک است اگر:

1. مسیری از هر حالتی به حالت دیگر داشته باشد.

2. برای هر حالت شروعی (Start State)، پس از یک زمان گذرا محدود T0، احتمال قرار گرفتن در هر حالتی در زمان ثابت T (T0>T) غیر صفر است.

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

ارگودیک، بدون توجه به وضعیت اولیه، احتمال قرار گرفتن در یک حالت خاص باید در طول زمان به توزیع یک حالت پایدار یا ایستا (Steady state) همگرا شود.

برای یک زنجیره مارکوف ارگودیک، نرخ بازدید طولانی مدت (Long term visit rate) یکتایی برای هر حالت وجود دارد. در واقع این توزیع احتمال حالت پایدار (steady state probability distribution) می‌باشد که به این شکل است.

بنابراین π احتمال برای هر حالت است. مثلا π1 احتمال در حالت 1 است و πn احتمال در حالت n است. همچنین در یک دوره طولانی مدت، نسبت به نرخ π از هر حالت بازدید خواهیم کرد.

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

مثالی برای حالت ایستا یا پایدار (Steady state)

برای درک بهتر موضوع مثالی بزنیم. ابتدا این را می‌دانیم که حالت پایدار، بردار احتمالاتی است که در آن πi، احتمال بودن ما در حالت i است. حال برای مثال یک گراف کوچک داریم که شامل 2 گره (Node) است. همانطور که در شکل زیر نشان داده شده است، π1 ،مقدارش 1/4 است و می‌توانید ببینید که احتمال رفتن از گره 2 به گره 1 هم 1/4 است. اگر در گره 1 باشید احتمال ماندن در گره 1 هم 1/4 است. بنابراین در دراز مدت، احتمال اینکه ما در گره1 قرار بگیریم 1/4 است. در حالی که برای گره 2، احتمال لوپ بک 3/4 است. همچنین احتمال رفتن از گره 1به 2 هم 3/4 است.

بنابراین در این‌جا نرخ بازدید طولانی مدت 3/4 خواهد بود.حال این مثالی برای درک مفاهیم بود. اکنون چگونه آن را در حالت کلی حساب کنیم.

چگونه بردار π را محاسبه کنیم؟

ابتدا باید بدانیم که اگر موقعیت فعلی ما با π توصیف شود، مرحله بعدی به صورت πP توزیع (Distribute) می‌شود و همانطور که به یاد داریم P، ماتریس احتمال انتقال بود. بنابراین اگر اکنون توزیع بر روی حالت‌ها را با π توصیف کنیم، وضعیت بعدی که مرحله بعدی ولگشت (Random walk) ما است را به صورت πP نشان می‌دهیم. بنابراین داریم:

π = πP

ما می‌دانیم که دور شدن و رفتن به مرحله بعدی از حالت پایدار ما را به حالت پایدار برمی‌گرداند و اگر این معادله را حل کنیم، چیزی که به‌دست می‌آید π است. منظور این است که ما از حالت پایدار اول به حالت پایدار دوم می‌رسیم.

بردار π در واقع بردار ویژه برای ماتریس احتمال انتقال P است و ماتریس‌های احتمال انتقال همیشه دارای بزرگترین مقدار ویژه 1 هستند.

روش محاسبه π با تکرار توان (Power iteration)

یک راه ساده برای محاسبه π ، روش تکرار توان است. حتما به یاد دارید که گفتیم تعریف حالت پایدار این است که از هر کجا که شروع کنیم، در نهایت به حالت پایدار می‌رسیم. اکنون با توزیع احتمال 1 در حالت 1 و توزیع صفر در هر حالت دیگر شروع می‌کنیم.(به این معناست که احتمال در حالت 1، یک است و در بقیه حالت‌ها صفر است.)

X = (1000….0)

سپس آن را در ماتریس احتمال خود، P ضرب می‌کنیم. بنابراین پس از یک مرحله در XP هستیم. پس از دو مرحله در XP به توان 2 (XP2) و بعد از آن در XP به توان 3 (XP3) و به همین ترتیب ادامه دارد.

بنابراین در نهایت، به این معنی است که ما برای مقدار یک K بزرگ (تعداد حالات) در XPk = π (k توان P است) هستیم.

با این تفاصیل کاری که ما برای تخمین π انجام می‌دهیم این است که X را با افزایش توان P ضرب کنیم تا زمانی که حاصل ضرب، پایدار به نظر برسد و آن را π می‌نامیم.

مثالی برای توان تکرار

از ماتریس احتمال انتقال که قبلا برای تله‌پورت α = 0.5 محاسبه کردیم، استفاده می‌کنیم. اکنون فرض کنید Surfer در حالت 1 شروع می‌کند. به این معناست که وضعیت Random walks ما بردار X است که 1 در حالت 1 است، 0 در حالت 2 است و 0 در حالت 3 است. به این دلیل که فقط 3 عدد گره وجود دارد.

حالا چگونه X1 را محاسبه کنیم؟

بنابراین ما X0 را در P ضرب می‌کنیم و به ما بردار X1 را خواهد داد. برای فهم چگونگی ضرب ماتریس‌ها می‌توانید این ویدیو را مشاهده کنید.

بنابراین این اکنون وضعیت فعلی ما پس از یک بار تکرار (Iteration) است. همچنین بعد از 2 بار تکرار، دوباره ماتریس نهایی که وضعیت فعلی است را در ماتریس احتمال P ضرب می‌کنیم.

این بردار، توزیع جدیدی بر روی حالت‌های ممکن می‌دهد.

اگر ما این روند را ادامه دهیم تا به حالت پایدار برسیم، به حالت پایدار (5/18 4/9 5/18) خواهیم رسید.

بنابراین این مقدار نرخ بازدید طولانی مدت (Long term visit rate) برای گره 1، 2 و 3 خواهد بود که در واقع این سه مقدار پیج رنک‌های صفحه 1، 2 و 3 هستند.

خلاصه ای از پیج رنک

پیش پردازش

1. با استفاده از گراف لینک‌ها، ماتریس احتمال انتقال P را می‌سازیم.

2. با استفاده از آن بردار پیج رنک π را محاسبه می‌کنیم.

3. مقدار πi ، پیج رنک صفحه i و عددی بین صفر تا یک است.

پردازش پرس و جو (Query processing)

1. همه صفحاتی که با پرس و جو (Query) مطابقت دارند، بازیابی می‌کنیم.

2. آن‌ها را بر اساس پیج رنک رتبه‌بندی می‌کنیم.

3. این رتبه بندی مستقل از پرس و جو است. (Query independent)

پس پیج رنک حتی به پرس و جو نگاه نمی‌کند.

4. وقتی از پیج‌رنک در هر نوع الگوریتم بازیابی اطلاعات استفاده می‌کنیم، قصد داریم آن را با سایر معیار‌های پرس و جو مثل TF-IDF و غیره ترکیب کنیم.

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