عنوان پایان‌نامه
نظریه شبکه ها والگوریتم آشکار سازی موتیف از شبکه
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 9...;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 43116
- تاریخ دفاع
- ۱۱ مهر ۱۳۸۸
- دانشجو
- سعید امیدی کلیشمی
- استاد راهنما
- علی معینی, علی مسعودی نژاد
- چکیده
- شبکه ها نمایانگر دامنه وسیعی از سامانه های جهان واقعی می باشند. فارغ از این که شبکه ها نمایش گر سامانه های طبیعی یا بشر ساخته باشند، ویژگی هایی جهانی را از خود بروز می دهند. نشان داده شده که بیشتر شبکه های جهان واقعی اعم از زیستی، تکنولوژیکی، اجتماعی و یا طبیعی پدیده ی توزیع درجه قانون توان را بروز می دهند. بسیاری از مدل سازی ها مکانیزم اتصال ترجیحی را به عنوان عامل اصلی پدیده توزیع قانون توان معرفی کرده اند. نگرش های گوناگونی در مدل سازی شبکه ها طی سال های اخیر به وجود آمده که از مدل های ساده بینانه اولیه به مدل های واقع بینانه تر تکامل یافته اند و در این رساله به بررسی تکامل این نگرش ها پرداخته خواهد شد. اما یکی دیگر از ویژگی های مهم در شبکه ها که در سال های اخیر بسیار مورد توجه قرار گرفته، موتیف در شبکه ها می باشد. موتیف به زیرگرافی اطلاق می شود که با بسامد بالایی در یک شبکه ظاهر شده است. آشکارسازی زیرگراف های پرتکرار یا همان موتیف ها رویکری است آماری برای بازیابی زیرواحد های مهم عملیاتی از شبکه. هرچند به لحاظ پیچیدگی محاسباتی، آشکارسازی موتیف در شبکه ها مسئله بسیار مشکلی است که نمی توان برای آن الگوریتمی در زمان خطی ارائه داد. بر این اساس، طراحان الگوریتم طی سال های اخیر از رویکرد تخمینی برای واکشی موتیف ها استفاده کردند. در این رساله، الگوریتم تخمینی جدیدی برای حل این مسئله ارائه داده شده است که با استفاده از شگرد های داده کاوی الگوهای اتصال پرتکرار را به طور مؤثری از شبکه ها واکشی می کند. الگوریتم ارائه داده شده قادر است در زمان مناسبی دامنه بزرگ تری از موتیف ها را در مقایسه با الگوریتم های پیشین پیدا کند.
- Abstract
- Complex networks portray a wide range of real-world systems. Despite of the fact that the networks depict natural or hand-made systems, they display some global characteristics. It has been shown that the majority of the real-world networks from biological, technological, social and even natural express power-law degree distribution phenomenon. Most of the modeling has introduced preferential attachment mechanism as the main factor in emerging power-law degree distribution in the networks. A variety of views, which are evolved in comparison with late models, has been appeared in recent years and many of them are reviewed in this dissertation. However, one of the important features in the networks is network motifs that have hugely investigated in recent years. A motif stands for a recurrent or frequent subgraph in a network. Extracting recurrent subgraphs or network motifs is a non-parametric statistical approach for detecting functional subunits in the networks. Network motif detection, however, is a computationally hard problem that can be classified as a counting problem in #P-complete. Therefore, algorithm designers have tried to overcome this hard problem using approximation approach. Here, a novel approximation algorithm is introduced that by means of data mining techniques finds connected patterns in a network effectively. The algorithm is able to detect a wide domain of network motifs more efficiently in comparison with the previous algorithms.
