عنوان پایان‌نامه
بهبود الگوریتم محاسبه ی توزیع شده ی رتبه ی پیچ
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79252;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79252
- تاریخ دفاع
- ۲۷ دی ۱۳۹۵
- دانشجو
- سهیل قنبری
- استاد راهنما
- علی معینی
- چکیده
- امروزه شبکه های توزیع شده، کاربردی روزمره در زندگی افراد دارد. شبکه ها از انواع مختلفی تشکیل شده اند، از شبکه های اطلاعات گرفته تا شبکه های پخش و توزیع و شبکه های زیست محیطی. در هر یک از انواع شبکه رتبه بندی گره های شبکه اهمیت زیادی دارد. رتبه بندی در شبکه ها بر اساس معیار های متفاوتی صورت می پذیرد. برای مثال الگوریتم رتبه بندی پیج گره های یک شبکه را بر اساس میزان اهمیت گره ها رتبه بندی م ¬کند. الگوریتم رتبه بندی پیج از الگوریتم های مطرح و از محبوب ترین الگوریتم های رتبه بندی در جهان است. ما تلاش کرده ایم تا با بهبود عملکرد الگوریتم رتبه بندی پیج در رتبه بندی گره ها بر اساس میزان سکوت، روش های جدیدی ارائه کنیم. سکوت در یک شبکه به این معنا است که یک گره بیش از این که اطلاعات با شبکه به اشتراک بگذارد از اطلاعات شبکه استفاده کند. اصطلاحاً به گره ای ساکت گفته می شود که تعداد یال های ورودی آن از تعداد یال های خروجی آن بیشتر باشد، همچنین به گره هایی که دارای یال ورودی هستند اما هیچ یال خروجی ندارند نیز گره های ساکت بدیهی یا گره های آویزان گفته می شود. هدف ارائه ی روشی است که تمامی گره های شبکه را توامان و بر اساس میزان سکوت آنها به صورت توزیع شده رتبه بندی کند. منظور از ارائه ی روش توزیع شده این است که هر گره به تنهایی بتواند رتبه ی خود را در شبکه بدست آورد. برای رسیدن به این هدف از روش های مونت کارلو بهره برده ایم. برای این منظور با کمک صورت مسئله آزمایش مونت کارلو طراحی کرده ایم و برای مدل سازی از پیاده روی تصادفی استفاده کرده ایم. تا با استفاده از قوانین زنجیره ی مارکوف به نتیجه ی مورد نظر برسیم. به روش استفاده شده در این پایان نامه روش زنجیره ی مارکوف مونت کارلو (MCMC) گفته میشود. پس از ارائه ی روش تلاش شده تا حاصل کار را به کمک معیارهایی ارزیابی کنیم و نتایج را به نمایش گذاریم.
- Abstract
- In recent years networks are inseparable parts of real-life communication systems. Networks are composing of individual units –called nodes– connected together in some ways. Each unit in a network contains or generates information that can be sent by links. Examples of information networks include the Internet, computer networks and all online societies. A new aspect that we give attention in this paper is silentness. A silent node use information of a networks although share nothing. With ranking this kind of nodes we can manage networks for dealing with silent. We can use some plan to make them more active. We look for techniques for distributed computing of silent nodes ranks in networks with local view. Using page rank or other silent nodes ranking algorithms that apply iterative methods are not appropriate for distributed networks. In a distributed network only limited size of massages are allowed to be send over adage in each round. Using Monte Carlo method helps us to decrease communication overhead and makes the algorithm more appropriate for distributed networks. In this paper we present a distributed algorithm for ranking nodes by silentness in a large network. KEYWORDS Ranking, PageRank, Silnetness, Dangling nodes, Monte Carlo, Markov Chain
