دانلود پایان نامه ارشد : شناسایی تشکل‌های همپوشان در شبکه‌های پویا

دانلود متن کامل پایان نامه مقطع کارشناسی ارشد رشته مهندسی کامپیوتر

گرایش :هوش مصنوعی

عنوان : شناسایی تشکل‌های همپوشان در شبکه‌های پویا

دانشگاه شیراز

دانشکده مهندسی

 

پایان نامه­ ی کارشناسی ارشد در رشته ­ی مهندسی کامپیوتر- هوش مصنوعی

شناسایی تشکل‌های همپوشان در شبکه‌های پویا

استاد راهنما

دکتر علی حمزه

شهریور ماه 1392

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود(در فایل دانلودی نام نویسنده موجود است)تکه هایی از متن پایان نامه به عنوان نمونه :(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)چکیدهبسیاری از ساختارهای پیچیده طبیعی و اجتماعی را می‌توان به صورت شبکه[1] در نظر گرفت. جاده‌ها، پایگاه‌های اینترنتی، شبکه های اجتماعی، ارتباطات سازمانی، روابط خویشاوندی، تبادل نامه‌های الکترونیک، تماس‌های تلفنی و تراکنش‌های مالی تنها چند نمونه از این شبکه‌ها هستند. امروزه تحلیل شبکه‌ها یکی از شاخه‌های پژوهشی پرطرفدار و پرکاربرد در سطح جهان است و توجه پژوهشگران بسیاری از رشته‌های مختلف از جمله علوم کامپیوتر و علوم اجتماعی را به خود اختصاص داده است. نتایج حاصل از این پژوهش‌ها، ابزار و اطلاعات مفیدی را برای استفاده در حوزه‌های مختلف از جمله: ارتباطات، امنیت و تجارت در اختیار قرار می‌دهد.یکی از موضوعات پرکاربرد در زمینه تحلیل شبکه‌ها، شناسایی تشکل‌ها[2] در شبکه است. می‌توان هر تشکل را توده‌ای متراکم از رئوس در نظر گرفت که از طریق یالهای اندکی با تشکل‌های دیگر در ارتباط است. به عنوان مثال افراد با علایق و تمایلات مشابه در شبکه‌های اجتماعی، صفحات با محتوای مرتبط در فضای وب، مقالات با حوزه‌های مشابه در پایگاه مقالات، همگی نمونه‌هایی از تشکل‌ها در شبکه‌های مختلف هستند. در سال‌های اخیر، کارهای بسیاری در زمینه شناسایی تشکل‌ها، انجام گرفته و الگوریتم‌ها و ابزارهای متعددی ارائه شده است اما همچنان تلاش برای ارائه روش‌های بهتر از منظرهای مختلف از جمله سرعت، دقت و مقیاس‌پذیری ادامه دارد.در این پایان نامه، دو روش پیشنهادی، یکی برای افزایش کارایی تشخیص تشکل های همپوشان در شبکه های ایستا و دیگری برای شبکه های پویا به همراه نتایج آزمایش های متعدد انجام شده برای ارزیابی کارایی آنها ارائه شده است.واژگان کلیدی: شبکه های پویا، شبکه های اجتماعی، تشخیص تشکل همپوشان، روش پخش برچسب فهرست مطالبفصل اول: مقدمه............................................................................................................................................................................................................................. 1مقدمه............................................................................................................................................................................................................................................. 1دانش شبکه................................................................................................................................................................................................................................. 2کاربردهای دانش شبکه...................................................................................................................................................................................................... 3کاربردهای اقتصادی...................................................................................................................................................................................................... 3کاربردهای بهداشتی...................................................................................................................................................................................................... 4کاربردهای امنیتی.......................................................................................................................................................................................................... 5کاربردها در حوادث همگانی.................................................................................................................................................................................... 6کاربردها در پژوهش بر روی مغز.......................................................................................................................................................................... 6کاربردهای مدیریتی....................................................................................................................................................................................................... 6کاربردهای پژوهشی....................................................................................................................................................................................................... 7کاربردهای دیگر............................................................................................................................................................................................................... 8تاریخچه......................................................................................................................................................................................................................................... 9مفاهیم اولیه........................................................................................................................................................................................................................... 10انگیزه انجام این پایان نامه............................................................................................................................................................................................. 13نگاه کلی به فصول رساله................................................................................................................................................................................................ 14فصل دوم: پیشینه تحقیق..................................................................................................................................................................................................... 16مقدمه.......................................................................................................................................................................................................................................... 16شبکه های ایستا و شبکه های پویا......................................................................................................................................................................... 17تشکل های غیر همپوشان و تشکل های همپوشان.................................................................................................................................... 18تعریف مسئله......................................................................................................................................................................................................................... 19روش های موجود برای تشخیص تشکل های همپوشان در شبکه های ایستا.......................................................................... 21روش نفوذ دسته........................................................................................................................................................................................................... 21روش افراز گراف و دسته بندی یال ها.......................................................................................................................................................... 22روش بسط محلی و بهینه سازی........................................................................................................................................................................ 23روش تشخیص فازی.................................................................................................................................................................................................. 24روش الگوریتم های پویا و مبتنی بر عامل.................................................................................................................................................. 25روش‌های دیگر............................................................................................................................................................................................................... 26مقایسه روش های تشخیص تشکل های همپوشان در شبکه های ایستا...................................................................................... 26مجموعه داده ها............................................................................................................................................................................................................ 27معیارهای ارزیابی.......................................................................................................................................................................................................... 29نتایج آزمایش ها........................................................................................................................................................................................................... 30تحلیل نتایج..................................................................................................................................................................................................................... 37تشخیص تشکل های همپوشان در شبکه های پویا..................................................................................................................................... 38جمع بندی.............................................................................................................................................................................................................................. 38فصل سوم: ارائه راه حل و روش های پیشنهادی.................................................................................................................................................. 42مقدمه.......................................................................................................................................................................................................................................... 42نگاهی دقیق تر به روش انتشار برچسب............................................................................................................................................................... 42الگوریتم.............................................................................................................................................................................................................................. 43تحلیل پیچیدگی زمانی............................................................................................................................................................................................ 45بهبود کارایی روش انتشار برچسب.......................................................................................................................................................................... 46الگوریتم.............................................................................................................................................................................................................................. 46الگوریتم مبتنی بر انتشار برچسب برای تشخیص تشکل های همپوشان در شبکه های پویا.......................................... 48الگوریتم.............................................................................................................................................................................................................................. 48فصل چهارم: آزمایش ها و نتایج....................................................................................................................................................................................... 52مقدمه.......................................................................................................................................................................................................................................... 52بهبود کارایی روش انتشار برچسب در شبکه های ایستا.......................................................................................................................... 52پیاده سازی روش پایه.............................................................................................................................................................................................. 52پیاده سازی روش پیشنهادی.............................................................................................................................................................................. 53مجموعه داده ها............................................................................................................................................................................................................ 53معیار ارزیابی.................................................................................................................................................................................................................... 54نتایج آزمایش ها........................................................................................................................................................................................................... 54تحلیل نتایج..................................................................................................................................................................................................................... 57تحلیل پیچیدگی زمانی............................................................................................................................................................................................ 58تشخیص تشکل های همپوشان در شبکه های پویا..................................................................................................................................... 58مجموعه داده ها............................................................................................................................................................................................................ 59معیارهای ارزیابی.......................................................................................................................................................................................................... 60نتایج آزمایش ها........................................................................................................................................................................................................... 60تحلیل نتایج..................................................................................................................................................................................................................... 63تحلیل پیچیدگی زمانی............................................................................................................................................................................................ 64فصل پنجم: بحث و نتیجه گیری...................................................................................................................................................................................... 66نتیجه گیری........................................................................................................................................................................................................................... 66پیشنهاد ها برای کارهای آینده................................................................................................................................................................................ 67منابع و مآخذ................................................................................................................................................................................................................................. 69 [1] Network[2] Community Detectionفهرست تصاویرنمونه ای از شبکه راه های ارتباطی.. 3شبکه کاربران شبکه اجتماعی فیسبوک... 4بخشی از شبکه روابط صدام حسین و اطرافیانش. 5شبکه پیش بینی نحوه شیوع ویروس H1N1  در سال 2009. 6نمونه ای از شبکه روابط بین کارکنان یک سازمان. 7شبکه مواد غذایی مکمل.. 8معمای پل های کونیگزبرگ و گراف نشان دهنده آن.. 9چند مثال از شبکه ها 10دو نمونه گراف و نمودار توزیع درجه آنها 12یک گراف کامل.. 12نمونه یک شبکه پویا و تغییرات آن در چهار برش زمانی.. 17تشکل های غیر همپوشان و تشکل های همپوشان.. 19شبکه دوستی دانش آموزان دبیرستان و تشکل های آن.. 36یک نمونه از زیر شبکه های روش پیشنهادی، به همراه تشکل های آن.. 46شبکه اولیه و شبکه های ایجاد شده از روی آن.. 59فهرست جداولفهرست الگوریتم های انتخاب شده برای مقایسه در حوزه تشکل های همپوشان.. 27نتایج حاصل از عملکرد الگوریتم های مورد آزمایش.... 37مشخصات شبکه های مورد استفاده در آزمایش ها 60 فهرست الگوریتم هاالگوریتم  SLPA.. 43الگوریتم پیشنهادی برای تشخیص تشکل های همپوشان در شبکه های ایستا 47الگوریتم پیشنهادی برای تشخیص تشکل های همپوشان در شبکه های پویا 49

مقدمه

در دنیای امروز، ما با سیستم های پیچیده ای[1] در پیرامون خود احاطه شده ایم، از جامعه که در آن میلیون ها عضو با یکدیگر در حال تعامل هستند تا شبکه های تلفن همراه و کامپیوتر که میلیون ها کاربر را به یکدیگر متصل می‌کنند. همچنین توانایی ما برای استنتاج و درک محیط اطراف، وابسته به شبکه ای از میلیاردها سلول عصبی[2] در مغز ماست. این سیستم های پیچیده نقش های بسیار مهمی در جنبه های مختلف زندگی ما ایفا می‌کنند. درک، توصیف، پیش بینی و کنترل این سیستم ها از جمله بزرگترین چالش های ما در جهان مدرن است.معمولا در پشت هر کدام از این سیستم های پیچیده، شبکه ای عظیم قرار دارد که تعاملات بین اجزای این سیستم ها را مشخص می‌کند. به عنوان مثال: فعل و انفعالات شیمیایی درون بدن موجودات زنده، تعاملات میان سلول های عصبی مغز، روابط دوستی، خویشاوندی و اجتماعی، شبکه جهانی اینترنت، تراکنش های مالی، خطوط انتقال و توزیع نیرو، راه های ارتباطی زمینی، هوایی و دریایی، همگی بخشی از مواردی هستند که می‌توان آنها را به صورت یک شبکه توصیف کرد. همچنین می‌توان گفت که شبکه ها قلب بسیاری از فناوری های انقلابی عصر حاضر هستند. موتورهای جستجو[3]، شبکه های اجتماعی مجازی[4]، شبکه های کامپیوتری جهانی، شبکه جهانی مخابرات و تلفن همراه تنها تعدادی از این نمونه ها هستند.با وجود تفاوت و تنوع بسیار زیادی که در ماهیت، اندازه، کاربرد، رفتار و ویژگی های مختلف این سیستم ها و شبکه ها، چه از نوع طبیعی و چه ساخته دست بشر وجود دارد، می‌توان اصول و قوانین مشخص و مشابهی را در میان آنها مشاهده کرد. برای مثال: شبکه واکنش های شیمیایی که اجزای آن را مولکول های بسیار کوچک تشکیل می‌دهند، شبکه جهانی وب[5] که در آن صفحات وب به وسیله پیوندهای وب[6] به یکدیگر متصل شده اند، شبکه های اجتماعی که از روابط میان افراد تشکیل شده اند و بسیاری موارد دیگر، همگی قابل توصیف با ساختارها و قوانین مشابهی هستند و این امر به عنوان یک مزیت بزرگ تلقی می‌شود. زیرا می‌توان تمام این سیستم های متفاوت طبیعی و مصنوعی را توسط ابزارهای ریاضی و مدل سازی مشابهی توصیف کرد.با توجه به اینکه از سال ها پیش بسیاری از این سیستم ها، مانند: ساختارها و واکنش های زیستی، راه های ارتباطی، روابط اجتماعی و نظایر آن و همچنین دانش مطالعه بر روی سیستم ها و شبکه ها شناخته شده اند، پرسشی که ممکن است مطرح شود این است که چرا اهمیت این موضوع تنها در چند دهه اخیر آشکار شده است؟ پاسخی که می‌توان داد این است که در گذشته ابزارهای مناسبی برای جمع آوری، نگهداری و پردازش این اطلاعات وجود نداشت اما امروزه با توسعه چشمگیر فناوری هایی نظیر کامپیوتر و شبکه های ارتباطی دیجیتال، این امکان فراهم آمده است که گردآوری، ترکیب، اشتراک و تحلیل این اطلاعات با سهولت، سرعت و دقت بالا و هزینه کم قابل اجرا باشد.

دانش شبکه[7]

دانش شبکه شاخه ای از علوم بشری است که به مطالعه بر روی شبکه ها می‌پردازد و تلاش می‌کند با استفاده از نتایج بررسی های خود، از آنها برای درک بهتر سیستم های پیچیده بهره بگیرد. به طور کلی می‌توان چهار ویژگی را برای این دانش برشمرد که در ادامه به اختصار به آنها اشاره می‌شود (1):ماهیت میان رشته ای: با توجه به نحوه برخورد با مسئله در حوزه مطالعه شبکه ها، این دانش تنها به یک شاخه خاص از علم محدود نبوده و می‌تواند در علوم گوناگون از قبیل: علوم اجتماعی، زیستی، کامپیوتر، فیزیک، شیمی، اطلاعات، اقتصاد، امنیت و بسیاری از موارد دیگر کاربرد داشته باشد. به عنوان مثال، روشی که در حوزه علوم اجتماعی برای تشخیص افراد و گرو های موثر بر جامعه مورد استفاده قرار می‌گیرد، ممکن است در شبکه های کامپیوتری برای مدیریت ترافیک شبکه به کار برده شود.عملگرایی و تمرکز بر داده ها: بر خلاف نظریه گراف ها که بیشتر به جنبه های انتزاعی و ریاضی مسائل توجه دارد، این دانش بیشتر بر حوزه کاربرد عملی و داده های مسئله تمرکز می‌کند. به همین جهت ابزارها و روش هایی که در این زمینه ارائه می‌شوند، بر روی داده ها و مسائل واقعی آزمایش می‌شوند تا قابلیت و کارایی آنها مشخص شود.بیان کمی و ریاضی: مطالعه شبکه ها برای توصیف و مطالعه بهتر و دقیق تر، از ابزارها و روش های ریاضی بهره می‌برد. به عنوان مثال: نظریه گراف ها، آمار و احتمالات، داده کاوی[8]، تئوری اطلاعات[9]، کنترل و فیزیک آماری از جمله علومی هستند که در این حوزه کاربرد دارند.پردازش و محاسبات: از آنجا که اغلب مسائل مطرح شده در این حوزه، حجم عظیمی از اطلاعات را در بر می‌گیرند، بخش مهمی از کار به طراحی و بکارگیری روش هایی معطوف می‌شود که بتوانند از عهده محاسبات سنگین مورد نیاز برآیند. به همین منظور طراحی الگوریتم ها، پایگاه داده ها و داده کاوی بخشی از ابزارهای نرم افزاری هستند که بسیار به کار برده می‌شوند.تعداد صفحه :88قیمت : 14000تومان

بلافاصله پس از پرداخت ، لینک دانلود پایان نامه به شما نشان داده می شود

و در ضمن فایل خریداری شده به ایمیل شما ارسال می شود.

پشتیبانی سایت :        09309714541 (فقط پیامک)        info@arshadha.ir

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

--  -- --

مطالب مشابه را هم ببینید

فایل مورد نظر خودتان را پیدا نکردید ؟ نگران نباشید . این صفحه را نبندید ! سایت ما حاوی حجم عظیمی از پایان نامه های دانشگاهی است. مطالب مشابه را هم ببینید. برای یافتن فایل مورد نظر کافیست از قسمت جستجو استفاده کنید. یا از منوی بالای سایت رشته مورد نظر خود را انتخاب کنید و همه فایل های رشته خودتان را ببینید