P(v)=
به عنوان مثال یک صفحه اگر به وسیله ی صفحات با کیفیت بالاتر مورد اشاره قرار بگیرد، دارای کیفیت بالاتری است.
یک گره w با درجه خروجی صفر (که اغلب “گره آویزان^[۱۸]” خوانده می شود) به عنوان چاله^[۱۹] عمل می کند. هر رتبه تخصیص داده شده به w از دست می رود، زیرا که w هرگز در سمت راست معادله بالا ظاهر نمی شود. با خلاصه سازی معادله ی بالا برای همه u ها، ما مشاهده می کنیم که باید برای همه گره های آویزان باید داشته باشیمp(u)=0.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

در نتیجه تمام گره هایی که از یک مسیر مستقیم در G به یک گره با درجه خروجی صفر می رسند باید رتبه ی صفر داشته باشند. بنابراین معادله ی بالا به شکل زیر اصلاح می شود، به طوری که همه گره های آویزان پیوندهایی به همه گره های موجود دارند و این به آن معنی است که همه ی گره ها رتبه را از هر گره آویزان دریافت می کنند که n در اینجا تعداد گره ها است.
اگر B نشان دهنده ماتریس مجاورت گراف وب با ردیف های نرمال سازی شده با بهره گرفتن از اصلاحات گره های آویزان که در بالا شرح داده شد باشد ]۲۴[:
اگر صفحهu به صفحه V اشاره کند
B(u,v)
اگر
در بقیه موارد
۰
پس معادله بالا به شکل زیر در می آید:
P=B^TP
ماتریس انتقال B و زنجیره مارکوف مطابق با آن نامتناوب است اگر و فقط اگر بزرگترین مقسوم علیه مشترک طول همه ی چرخه های مستقیم در گراف وب یکی باشد. B قابل کاهش نیست اگر و فقط اگر G شامل یک کامپوننت متصل تنها (SCC) باشد، یعنی یک مسیر مستقیم مابین هر زوج صفحات در G باشد و این در عمل موردنظر نیست و این را می توان با محدود کردن محاسبات به بزرگترین جزء متصل گراف وب بدست آورد اما بزرگترین SCC گراف وب واقعی تنها ۳۰%-۲۵ گره ها را در بر می گیرد ]۱۶[. به منظور غلبه بر این مسائل، ما یک گراف کامل وزن دار کوچک را به گراف وب خود افزوده ایم. ما بردار “رتبه صفحه” P با P(i)≥۰ و ۱||P||₁=تعریف کرده ایم.
(۲-۵)
P(v)= c.r(v) + (1-c).
در اینجا(r(1),…..,r(n))^T r= بردار شخصی با r(i)≥۰ و ۱||r||₁= و c احتمال انتقال با مقدار ۱۵/۰c.
اگر r یکنواخت است، به عنوان مثال r(v)= برای همه v ها، سپس P رتبه صفحه (PR) می باشد.
در نشانگذاری ماتریس ] ۲۴ :[
اگر صفحهu به صفحه V اشاره کند
cr(v)+(1-c) = M(u,v)
اگر
در بقیه موارد
۰
پس داریم:
P=cr+(1-c)B^TP=M^TP
این ماتریس نیز نامتناوب است، زیرا گره ها با r(v)>0 طول یک چرخه با احتمال انتقال مثبت M(vv)>0 دارند. اگر برای همه ی v ها در G،r(v)>0 باشد، پس همه ی گره ها از همه گره ها قابل دسترس هستند، بنابراین همه ی گره ها یک SCC واحد را شکل می دهند، پس M غیرمتناوب است.
ایده ” رتبه صفحه” به خوبی از طریق مدل بازدید کننده ی تصادفی^[۲۰] قابل توضیح است. در این مدل کاربر از طریق صفحات وب هدایت می شود. او می تواند دو نوع عملیات را اجرا کند. در هر صورت او یکی از فوق پیوندهای صفحه ی جاری را دنبال می کند و یا مستقیماً به یک صفحه ی تصادفی می رود. او نخستین یا دومین عمل را با احتمال c -1 انتخاب می کند. اگر او تصمیم بگیرد یکی از لینک ها را دنبال کند، این لینک به صورت تصادفی انتخاب شده است. به عبارت دیگر صفحه ی هدف v با احتمال r(v) انتخاب شده است.
دومین نوع عملیات ” انتقال از راه دور” نامیده می شود که c احتمال انتقال از راه دور است و r بردار شخصی یا انتقال:
اگر P(k) به توزیع بازدید کننده تصادفی در زمان k اشاره داشته باشد با P(0)=r پس] ۲۷[:
P^(k)=M^Tp^(k-1)=(M^T)^kr
به وسیله ی تئوری پایه ای زنجیره ی مارکوف، k^th امین تکرار ⁽P^(k همیشه به راه حل یکتای معادله ی بالا همگرا خواهد بود و کسری از زمان که رندم سورفر روی صفحه v صرف می کند، به رتبه صفحه P(v) همگرا خواهد بود ]۲۷[.
رتبه صفحه شخصی:
فرض کنید که n صفحه روی وب موجود است و هر صفحه A ، لینک های ورودی T1، T2 و ……Tn دارد و C(A) تعداد لینک هایی است که از صفحه A خارج می شوند و d یک مقدار پیوسته در محدود ۰ و ۱ باشد. پس رتبه صفحه، PR(A) به صورت زیر بیان می شود ]۲۸[:
(۲-۶)
+ d PR(A)=
برای ماتریس کامل M معادله بالا بعد از چند تکرار همگرا خواهد شد. بعد از محاسبه ی رتبه صفحه، در صورتی که این مقدار بالا باشد، صفحه در مکان بالا رتبه بندی خواهد شد .
HITS:
کلینبرگ^[۲۱] یک الگوریتم مبتنی بر تکرار را تحت عنوان HITS یا الگوریتم کلینبرگ معرفی نموده است. HITS مبتنی بر پرس و جو است که محاسبات آن باید خیلی سریع در زمان پرس و جو انجام شود. محاسبات HITS بر پایه زیرگراف کوچکی است که به روش زیر تولید شده است:
یک مجموعه S_q از نتایج جستجو که تصور می شود با پرسش q متناسب است، بدست آورده می شود و این می تواند n نتیجه بالای موتورهای جستجو با بهره گرفتن از رتبه بندی مبتنی بر متن باشد. معمولاً صفحاتی که از S_q مورد اشاره قرار گرفته اند و صفحاتی که به S_q اشاره می کنند نیز اضافه می شوند.
ساخت یک گراف مجاورت G_q، زیرگراف به وسیله مجموعه گسترش یافته S_q توسعه می یابد.
HITS دو نمره برای هر گره در G_q محاسبه می کند. نمره اعتبار a(v) که منعکس کننده ارتباط محتوای v با پرسش است. نمره قطبیت^[۲۲] h(v) که کیفیت صفحه v را به عنوان یک مجموعه لینک با توجه به موضوع داده شده، تعیین می کند.
الگوریتم بر این اصل استوار است که قطب های خوب به احتمال زیاد به صفحات با اعتبار بالا لینک می شوند و اعتبارهای خوب در صفحات با قطبیت خوب آشکار می شوند.
در یک الگوریتم با تکرار، فرض کنید که h(k) و a(k) به بردارهای نمره قطبیت و نمره اعتبار اشاره می کنند. نخستین بردار قطبیت، h(0) ممکن است مقادیر مثبت دلخواه را شامل شود. (k+1) امین نمره اعتبار v از بردار قطبیت قبلی h(k) محاسبه می شود به طوری که مجموع نمرات قطبیت جاری گره هایی که به v اشاره می کنند ]۲۹[:
a^(k+1)(v)=
(۲-۷)
به طور مشابه k+1 امین نمره قطبیت v، مجموع نمره اعتبار گره هایی است که به وسیله v مورد اشاره قرار گرفته اند.
h(k+1)(u)=(v)
اگر A_q گراف مجاورت G_q هست، معادلات بالا می تواند به شکل ماتریس بیان شوند ]۲۹[:
a^(k+1)=A_q^T h(k)