دانلود پروژه: ارایه یک روش جهت کاهش میانگین فاصله‌ی گره‌‌های گراف شبکه‌های اجتماعی

فهرست مطالب

فصل اول : کلیات.. 1

1 – 1 – مقدمه. 2

1 – 2 – بیان مسئله. 4

1 – 3 – اهمیت تحقیق. 5

1 – 4 – اهداف.. 5

1 – 5 – فرضیه ها 6

فصل دوم : مروری بر ادبیات و پیشینه تحقیق. 8

2 – 1 – بررسی الگوریتم های موجود برای کاوش و تجزیه و تحلیل گراف.. 8

2 – 2 – بررسی الگوریتم های موجود برای کاهش میانگین فاصله گره های گراف شبکه اجتماعی.. 8

2 – 2 – 1 – نظریه فاصله شش رأسی.. 8

2 – 3 – الگوریتم رتبه بندی.. 10

2 – 3 – 1 – انواع رتبه بندی.. 11

2 – 3 – 1 – 1 – رتبه بندی بر اساس ارتباطات.. 11

2 – 3 – 1 – 2 –رتبه بندی با استفاده از آنالیز لینک… 12

2 – 3 – 1 – 3 – رتبه بندی وزنی صفحه. 12

2 – 3 – 2 – هاب ( مرکزیت ) و اوتوریتی.. 13

2 – 3 – 3 – محاسبه کارآمد رتبه صفحه. 13

2 – 4 – الگوریتم HADI 15

فصل سوم : روش اجرای تحقیق. 16

3 – 1 – کلیات الگوریتم. 17

3 – 2 – شاخص های تاثیر گذار در یافتن نود های مناسب.. 17

3 – 2 – 1 – درجه نود های گراف.. 17

3 – 2 – 2 – شعاع نود های گراف.. 20

3 – 2 – 3 – مکان نود در گراف.. 23

3- 2 – 3 – 1 – مرکزیت نود. 23

3 – 2 – 3 – 2 – موقعیت یک نود نسبت به سایر نود های گراف.. 27

3 – 3 – عملیات اولیه روی گراف.. 28

3 – 3 – 1 – دریافت ورودی ها 28

3 – 3 – 2 – محاسبه درجه نود های گراف.. 28

3 – 3 – 3 – محاسبه کم ترین فاصله بین هر دو نود. 28

3 – 3 – 4 – محاسبه شعاع نود های گراف و میانگین فاصله گره گراف.. 29

3 – 4 – یافتن نود های مناسب برای اتصال به منظور کاهش میانگین فاصله گره گراف.. 29

3 – 4 – 1 – فاکتور رتبه نود تعیین کننده اهمیت نود های گراف.. 30

3 – 4 – 1 – 1 – تابع بازگشتی برای محاسبه فاکتور رتبه نود. 30

3-4-1-2- تأثیر فاصله نودها بر فاکتور رتبه نود. 34

3 – 4 – 1 – 3 – تأثیر نودهای ایجادکننده فاصله گره در گراف بر پارامتر رتبه نود. 37

3-5- جمع بندی.. 38

فصل چهارم: تجزیه و تحلیل داده‌ها 39

4-1- ارائه یک نمونه کلی و اعمال الگوریتم روی آن. 40

4 – 2 – بررسی داده‌ها و یافته‌ها 45

فصل پنجم : نتیجه گیری و پیشنهادات.. 47

5-1- نتیجه گیری.. 48

5-2- پیشنهادات.. 49

واژه نامه فارسی به انگلیسی.. 50

واژه نامه انگلیسی به فارسی.. 52

منابع و مراجع. 54

 

فهرست جداول

عنوان                                                                                          شماره صفحه

جدول 2 – 1 – ماتریس گراف شکل 2 – 2 ………………………………………………………………………………….14

جدول 4 – 1 – درجه نود های گراف نمونه ………………………………………………………………………………….41

جدول 4 – 2 – شعاع نود های گراف نمونه ………………………………………………………………………………….41

جدول 4 – 3 – رتبه نود های اولیه نود های گراف نمونه ……………………………………………………………….41

جدول 4 – 4 – فاصله نود های گراف نمونه از یکدیگر ………………………………………………………………….42

جدول 4 – 5 – رتبه نود های جدید با اعمال فاکتور فاصله نود ها ……………………………………………………42

جدول 4 – 6 – تعداد نود هایی که بیشترین فاصله را با نود های گراف نمونه دارند ……………………………43

جدول 4 – 7- اعمال تعداد نود هایی که بیشینه فاصله  را با نود های گراف نمونه دارند ……………………..44

جدول 4 – 8 – میزان کاهش فاصله گره های گراف ناشی از تعدادی از نود های گراف ………………………44

فهرست نمودار ها

عنوان                                                                                          شماره صفحه

نمودار 4 – 1 – تاثیر اتصال نود ها با رتبه نود مختلف بر فاصله گره گراف ……………………………………….46

فهرست شکل ها

عنوان                                                                                          شماره صفحه

شکل 2 – 1 – نمونه ای از نظریه فاصله شش راسی ……………………………………………………………………….10

شکل 2 – 2 – گراف نمونه …………………………………………………………………………………………………………14

شکل 3 – 1 – اتصال نود ها با درجه بیشتر ……………………………………………………………………………………18

شکل 3 – 2 – اتصال نود گلوگاه ………………………………………………………………………………………………….19

شکل 3 – 3 – اتصال نود هایی با بیشترین شعاع ……………………………………………………………………………21

شکل 3 – 4 – اتصال نودی با شعاع بیشتر به نودی با فاصله بیشینه از نود قبلی …………………………………22

شکل 3 – 5 – اتصال نود های مرکزی ………………………………………………………………………………………….25

شکل 3 – 6 – اتصال نود های حاشیه ای ………………………………………………………………………………………26

شکل 3 – 7 – نمونه ای برای اعمال تابع بازگشتی بر نود C …………………………………………………………….32

شکل 3 – 7 – الف – محاسبه رتبه نود B …………………………………………………………………………33

شکل 3 – 7 – ب – محاسبه رتبه نود A …………………………………………………………………………..33

شکل 3 – 7 – ج – محاسبه رتبه نود D …………………………………………………………………………..33

شکل 3 – 7 – د – محاسبه رتبه نود E ……………………………………………………………………………..33

شکل 3 – 7 – ه – محاسبه رتبه نود F ………………………………………………………………………………33

شکل 3 – 8 – نمونه ای برای اعمالفاصله نود ها بر رتبه نود های B و E …………………………………………..36

شکل 3 – 8 – الف – محاسبه رتبه نود B …………………………………………………………………………36

شکل 3 – 8 – ب – محاسبه رتبه نود E ……………………………………………………………………………36

شکل 3 – 8 – ج – فاصله نود های B و E ……………………………………………………………………….37

شکل 4 – 1 – نمونه کلی برای اعمال الگوریتم ………………………………………………………………………………40

شکل 4 – 2 – اتصال نود های منتخب الگوریتم …………………………………………………………………………….45