عنوان پایان‌نامه
پیداکردن موتیف شبکه در شبکه های بزرگ زیستی بوسیله رایانش ابری
- رشته تحصیلی
- مهندسی کامپیوتر -نرم افزار
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 2195;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 56592
- تاریخ دفاع
- ۲۷ دی ۱۳۹۱
- دانشجو
- ایمان شرف الدین
- استاد راهنما
- مسعود رهگذر, علی مسعودی نژاد
- چکیده
- بسیاری از ساختار‌های زیستی می‌توانند به صورت یک شبکه پیچیده مدل شوند. یکی از راه‌های تحلیل این شبکه¬های پیچیده، پیدا کردن موتیف‌ها در شبکه می‌باشد. موتیف‌ها، عبارتند از الگوهایی که در یک شبکه مرتبأ تکرار می‌شوند، همچنین از موتیف‌ها به عنوان سنگ بنای سازنده هر شبکه هم یاد می‌شود. مسئله پیدا کردن موتیف در شبکه، به دلیل وجود زیر مسئله پیدا کردن هم‌ریختی گراف، به عنوان یک مسئله سنگین از لحاظ محاسباتی دسته‌بندی شده است. زمان پاسخ‌دهی روش‌های ارائه شده که به صورت غیر موازی تعریف شده‌اند، با افزایش اندازه موتیف و شبکه ورودی به صورت نمایی افزایش می‌یابد. برای رفع این مشکل، در این پژوهش، اقدام به ارائه یک روش جدید پیدا کردن موتیف به صورت موازی بر پایه دیدگاه MapReduce شده است، که در واقع یک گسترش بر الگوریتم کاوش می‌باشد. ارزیابی کارایی الگوریتم پیشنهادی نشانگر عملکرد خوب آن در پیدا کردن موتیف‌های بزرگ در شبکه‌های بزرگ می‌باشد . نتایج بدست آمده از اعمال الگوریتم بر روی سه شبکه مطرح، بیانگر این موضوع است که این روش می‌تواند با افزایش تعداد پردازنده‌هایی که در دست دارد، به افزایش سرعت مناسبی دست پیدا کند.
- Abstract
- Many natural structures can be modeled by complex networks. One way to investigate these complex networks is finding motifs in these networks. Network motifs are over-represented patterns in a network, which represent fundamental building blocks of that network. The problem of finding motifs in a given network has been proven as a computationally hard task because it uses the graph isomorphism algorithms. Sequential methods’ execution time grows exponentially when the sizes of motifs and networks increase. In this research, we propose a new parallel strategy based on the Google MapReduce approach that extends one of the efficient sequential methods known as Kavosh. Performance evaluation of our algorithm shows that it can facilitate the process of large motif detection in large networks. The results of applying the proposed algorithm, to a set of well-known networks show that our method is able to reach a very good speedup with augmented number of processors.
