عنوان پایان‌نامه
بررسی Pagerank وزن داردر گرافهای تکاملی
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 71..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 66884
- تاریخ دفاع
- ۱۲ شهریور ۱۳۹۳
- دانشجو
- زینب السادات حسینی خلیلی
- استاد راهنما
- علی معینی
- چکیده
- از زمان پیدایش شبکه‌ی جهانی اینترنت تاکنون حجم وب همواره رو به افزایش بوده است. مهمترین ابزار برای دسترسی به این اقیانوس بیکران اطلاعات، موتورهای جستجو می‌باشند که اصلی ترین بخش های آنها در پاسخ به پرس‌وجوی کاربر خزش و رتبه‌بندی صفحات وب است. به این صورت که ابتدا صفحات وب را جستجو کرده و تصویری کلی از گراف وب بدست می‌آورد (خزش) و سپس به رتبه‌بندی صفحات پرداخته و آنها را به‌ترتیب اولویت به کاربر نمایش می‌دهد. اما بطور تجربی ثابت شده که به‌دلیل ماهیت پویای وب، رشد نمایی و تغییرات زیاد اطلاعات، هیچ خزشگری نمی‌تواند به تصویری از همه‌ی صفحات وب دست یابد، بلکه بهترین موتورهای جستجو هم حداکثر ?72 از گراف وب را جستجو کرده‌اند. در این پایان نامه بجای اینکه در الگوریتم رتبه‌بندی، فرض را بر این بگذاریم که کل گراف وب را در دسترس داریم و بر آن مبنا رتبه‌بندی را انجام دهیم، مسئله‌ی تکاملی بودن گراف وب را مد نظر قرار داده و بر این مبنا رتبه‌بندی را انجام می‌دهیم . برای رتبه‌بندی صفحات وب هم از الگوریتم PageRank وزن‌دار (WPR) که در واقع بهبودیافته‌ی همان PageRank کلاسیک می‌باشد، استفاده می‌کنیم. به‌این‌صورت که با استفاده از یک الگوریتم، در هر بازه‌ی زمانی، بخشی از گراف وب را جستجو کرده و تصویری از گراف وب بدست می‌آوریم و WPR گراف حاصل از جستجو را با WPR گراف اصلی در آن بازه زمانی قیاس می‌کنیم، آنگاه میزان خطای WPR گرافهای حاصل از الگوریتم های مختلف جستجو را در مراحل تکامل، به نمودار می‌کشیم و به مقایسه‌‌‌ی آنها می‌پردازیم.
- Abstract
- The most important section of search engines are crawling and ranking the webpages. In other word, they first crawl webpages and take a general image of the web graph, then rank webpages and show them to users in order of their ranking. But empirically it is proved that none of crawlers can take a general image of the web because the web is dynamic and it's content and structure changes gradually. So the best search engine can take, at most, 72% of image of the web. In this thesis, for ranking we do not assume that we have the total image of the web, instead the structure of the web is considered as an evolving graph. Also this algorithm uses the weighted PageRank (WPR) method that is improved level of classical PageRank algorithm for ranking webpages. We first, at each step, crawl a portion of the web graph, and take an image of the web, then we contrast the WPR of base graph and WPR of searched graph, to find out which searching algorithm is more appropriate for WPR of evolving graph of the web.
