در این پایان نامه، دو روش پیشنهادی، یکی برای افزایش کارایی تشخیص تشکل های همپوشان در شبکه های ایستا و دیگری برای شبکه های پویا به همراه نتایج آزمایش های متعدد انجام شده برای ارزیابی کارایی آنها ارائه شده است.

واژگان کلیدی: شبکه های پویا، شبکه های اجتماعی، تشخیص تشکل همپوشان، روش پخش برچسب

 

فهرست مطالب

فصل اول: مقدمه………………………………………………………………………………………………………………………………………………………………………………………………….. 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] در مغز ماست. این سیستم های پیچیده نقش های بسیار مهمی در جنبه های مختلف زندگی ما ایفا می‌کنند. درک، توصیف، پیش بینی و کنترل این سیستم ها از جمله بزرگترین چالش های ما در جهان مدرن است.

معمولا در پشت هر کدام از این سیستم های پیچیده، شبکه ای عظیم قرار دارد که تعاملات بین اجزای این سیستم ها را مشخص می‌کند. به عنوان مثال: فعل و انفعالات شیمیایی درون بدن موجودات زنده، تعاملات میان سلول های عصبی مغز، روابط دوستی، خویشاوندی و اجتماعی، شبکه جهانی اینترنت، تراکنش های مالی، خطوط انتقال و توزیع نیرو، راه های ارتباطی زمینی، هوایی و دریایی، همگی بخشی از مواردی هستند که می‌توان آنها را به صورت یک شبکه توصیف کرد. همچنین می‌توان گفت که شبکه ها قلب بسیاری از فناوری های انقلابی عصر حاضر هستند. موتورهای