2-3-1. تعریف جریان شبکه……………………………. 20

2-4. انواع حملات……………………………….. 22

3- پیشینه تحقیق…………………………….. 28

3-1. مقدمه………………………… 28

3-2. روش مبتنی بر جریان در برابر روش مبتنی بر محتوا……………. 28

3-2-1. داده جریان شبکه……………………………. 29

3-2-2. روش های مبتنی بر بسته……………………………. 30

3-2-3. روش های مبتنی بر جریان…………………………….. 30

3-2-4. کرم ها…………………………… 31

3-2-5. محدود کننده سرویس………………………………. 34

3-2-6. پویش………………………………. 36

3-2-7. Botnet……………………………

4- روش پیشنهادی…………………………….. 43

 

4-1. مقدمه……………………………43

4-2. مجموعه داده ……………………….43

4-3. معیارهای شباهت……………………………… 45

4-3-1. معیارهای مبتنی بر گراف……………………………… 45

4-3-1-1. ضریب خوشه بندی محلی…………………………….. 45

4-3-1-2. ضریب خوشه بندی وزن دار محلی……………… 46

4-3-2. معیارهای مبتنی بر گره…………………………… 48

4-3-2-1. میانگین شباهت محلی…………………………….. 48

4-3-2-2. نسبت درجه گره…………………………… 49

4-3-2-3. معیار Zscore…………………………….

4-4. شناسایی نفوذگران…………………………….. 51

5- آزمایشات و نتایج…………………………….. 53

5-1. مقدمه…………………………. 53

5-2. شبیه سازی گراف شبکه……………………………. 53

این مطلب را هم بخوانید :

5-3. ساخت گراف یک سویه…………………………….56

5-4. مقایسه معیارهای شباهت……………………………… 57

5-5. نتایج………………………………………….. 58

فهرست منابع…………………………….. 60

3-2-1- ویژگی‏های شبه هار…………………… 39

3-2-2- انتخاب و تعیین اهمیت ویژگی‏ها برای تشکیل یک طبقه‏ بندی ‏کننده قوی…….. 41

3-2-3- درخت تصمیم آبشاری تقویت‏ شده………………….. 42

3-3- ردیابی چهره………………….. 44

3-3-1- پنجره جستجو…………………… 45

3-3-2- معیار تطابق……………………. 46

3-4- استخراج ویژگی‏های مربوط به کاهش هوشیاری……………………. 47

3-4-1- ویژگی‏های ناحیه چشم…………………… 47

3-4-2- ویژگی‏های ناحیه چهره و سر…………………… 55

3-5- تشخیص کاهش هوشیاری……………………. 58

3-5-1- سیستم خبره فازی……………………. 58

3-5-2- تولید خروجی نهایی……………………. 64

4- نتایج آزمایش‏ها و ارزیابی سیستم…………………… 69

4-1- نحوه آزمایش سیستم…………………… 69

4-2- معیار‏های ارزیابی……………………. 72

4-3- آشکارسازی چهره………………….. 73

4-4- ردیابی چهره …………………..75

 

4-5- استخراج ویژگی‏های ناحیه چشم…………………… 77

4-6- استخراج ویژگی‏های ناحیه سر و چهره …………………..82

4-7- تشخیص کاهش هوشیاری……………………. 86

4-8- ارزیابی کلی سیستم و الگوریتم‏ها………………….. 93

4-8-1- بررسی سرعت پردازش سیستم پیشنهادی……………………. 93

4-8-2- بررسی پیچیدگی محاسباتی الگوریتم‏ها………………….. 94

5- نتیجه‏گیری و پیشنهادات…………………….. 95

6- مراجع……………………99

چکیده:

هر ساله تصادفات رانندگی زیادی به دلیل خواب‏آلودگی و عدم تمرکز حواس راننده در سراسر دنیا رخ می‏دهد که خسارت‏های جانی و مالی فراوانی به همراه دارند. یکی از روش‏های تشخیص خستگی و عدم تمرکز حواس، استفاده از سیستم‏های نظارت چهره راننده است. سیستم‏های نظارت چهره راننده با دریافت تصاویر از دوربین و پردازش آنها، نشانه‏های خواب‏آلودگی و عدم تمرکز حواس را از چشم، سر و چهره استخراج می‏کنند. در این پایان‏ نامه یک سیستم نظارت چهره راننده طراحی شده است که با استخراج نشانه‏های خستگی و عدم تمرکز حواس از ناحیه چشم و چهره، کاهش هوشیاری راننده را تخمین می‏زند. در این سیستم چهار ویژگی شامل درصد بسته بودن چشم (PERCLOS)، نرخ پلک زدن، کاهش فاصله بین پلک‏ها و میزان چرخش سر استخراج می‏شود. سه ویژگی اول مربوط به نشانه‏های بروز خستگی و عدم تمرکز حواس در ناحیه چشم و ویژگی آخر مربوط به نشانه‏های کاهش هوشیاری در ناحیه چهره و سر می‏باشد. ویژگی‏های ناحیه چشم بر اساس تغییرات پروجکشن افقی ناحیه چشم و ویژگی‏های ناحیه چهره بر اساس بررسی قالب چهره استخراج می‏گردد. سپس این ویژگی‏ها توسط یک سیستم خبره فازی مورد پردازش قرار می‏گیرد تا میزان خستگی و عدم تمرکز حواس راننده تخمین ‏زده شود. تصویربرداری سیستم پیشنهادی در طیف مرئی و با دوربین سطح خاکستری انجام شده است. نتایج آزمایش‏ها بر روی فیلم‏های تهیه شده در محیط واقعی و آزمایشگاهی نشان می‏دهد که روش پیشنهادی دقت بسیار خوبی در استخراج ویژگی و تشخیص کاهش هوشیاری راننده دارد. از لحاظ سرعت اجرای الگوریتم، سرعت سیستم پیشنهادی حدود 5 فریم در ثانیه می‏باشد که می‏توان آن را سیستم بلادرنگ محسوب کرد.

پیشگفتار:

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

این مطلب را هم بخوانید :

 

 میلادی مطرح شد، اما عمده تحقیقات در این زمینه مربوط به بعد از سال 2000 میلادی می‏باشد.

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

سعی شده نوشتار پایان‏ نامه به نحوی روشن و ساده بیانگر روش پیشنهادی باشد، با این وجود خواننده گرامی می‏تواند در صورت داشتن سوال، بیان نظرات یا ارائه انتقاد از طریق پست الکترونیک hoseyn@sigari.ir یا hoseyn_sigari@engineer.com با اینجانب مکاتبه نماید.

1- مقدمه

1-1- تعریف سیستم های نظارت چهره راننده

همراه با توسعه صنعت خودرو در جهان، کاربرد فناوری‏های نوین در اتومبیل نیز افزایش یافته است. سیستم‏های حمل و نقل هوشمند[1] یا به اختصار ITS، کاربرد کامپیوتر و فناوری اطلاعات و ارتباطات در شبکه‏های حمل و نقل انسان و کالا است. سیستم پیشرفته دستیار راننده[2] یکی از بخش‏های سیستم حمل و نقل هوشمند محسوب می‏گردد. این سیستم‏ها برای بهبود کارایی خودرو و افزایش امنیت راننده و سرنشینان آن

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

نتایج بدست آمده از ارزیابی سیستم ارائه شده در این پژوهش، حاکی از آن است که بازیکن به کمک این دستیار هوشمند می ­تواند عملکرد بهتری نسبت به سایر بازیکنان داشته باشد.

فصل اول: مقدمه

1-1- مقدمه

مسائل بسیاری وجود دارند که محدود به یک راه­حل منحصر به فرد نمی­باشند. علاوه براین، برخی از مسائل ممکن است تعداد نامحدودی مسیرهای پاسخ مشابه، داشته باشند. یک ناسازگاری[1] هنگامی روی می­دهد که تصمیم­های گوناگونی، متناظر با مسیرهای پاسخ متمایز، فراهم باشد.

 

به طور کلی در سیستمی که دارای مجموعه­های نسبتاً بزرگی از قوانین و حقایق باشد، درج یک حقیقت می ­تواند منجر به صحیح شدن ارزش چندین قانون و در نتیجه فعال شدن آنها گردد. هر ترتیبی از اجرای این قوانین، می ­تواند نتایج متفاوتی را به دنبال داشته باشد که در این صورت این مجموعه از قوانین، مجموعه­ی قوانین ناسازگار نامیده می­شوند. یک استراتژی رفع ناسازگاری ترتیبی را برای اجرای این مجموعه از قوانین تعیین می­نماید.

سیستم­های هوشمند از قبیل سیستم­های مبتنی بر قانون، ابزارهای برنامه ­ریزی، و ساختارهای وابسته به دانش، از استراتژی­های متفاوتی برای رفع ناسازگاری استفاده می­ کنند] 2[.

در این پژوهش در ابتدا در رابطه با این شیوه ­های متفاوت توضیحاتی ارائه می­گردد و پس از آن ایده­ایی که به منظور رفع ناسازگاری در سیستم پیشنهادی بکار برده شده، شرح داده می­شود. سیستم پیشنهادی یک سیستم تصمیم­همیار هوشمند است که به منظور یاری رساندن به یک بازیکن در یک بازی استراتژیک بلادرنگ طراحی و پیاده­سازی شده و شرح ساختار و ویژگی­های آن در فصول آتی آمده است. همچنین در این پایان نامه در ارتباط با سیستم­های تصمیم­همیار هوشمند و ساختارهای مختلفی که محققان برای پیاده­سازی این سیستم­ها در نظر گرفته­اند، نیز مطالبی ارائه شده است.

2-1- رفع ناسازگاری

در بسیاری از سیستم­های مبتنی بر قانون، موتور استنتاج، یک مولفه­ی نرم­افزاری است که در هنگام اجرای برنامه­ی کاربردی، بر روی مجموعه ­ایی از قوانین، استنتاج می­ کند. از جمله مهمترین وظایفی که توسط موتور استنتاج صورت می­گیرد، رفع ناسازگاری است] 47[. به طور کلی، رفع ناسازگاری، یک استراتژی، برای انتخاب ترتیب اجرای قوانین است هنگامی که بیش از یک قانون بتواند اجرا شود.

این مطلب را هم بخوانید :

برای رفع ناسازگاری روش­های مختلفی وجود دارد. ساده­ترین راه­حل، انتخاب تصادفی قوانین است. در برخی از استراتژی­ها، از جمله مهمترین فاکتورهایی که در انتخاب قوانین موثر است مقدار اولویتی است که توسط سازنده­ی سیستم به هر قانون اختصاص داده می­شود که در این روش برای قوانین با الویت یکسان باید از روش دیگری استفاده گردد. روش­های خبره­تر از اطلاعات آماری مرتبط با موفقیت­ها و عدم موفقیت­های پیشین در هنگام بکار بردن قوانین مختلف، به منظور پی­بردن به احتمال موفقیت، استفاده می­ کنند. همچنین برخی از روش­ها، هزینه­ های قوانین را که نشان­دهنده­ی تلاش­هایی است که حل­کننده­ مسئله برای انجام اعمال بدان نیازمند است (مانند زمان) بحساب می­آورند] 2[.

روشی که در این پژوهش به منظور رفع ناسازگاری بکار برده شده، با در نظر گرفتن یک خط استنتاج جداگانه برای هر یک از قوانین ناسازگار در طی روند استنتاج، تمامی حالات ممکن برای اولویت­بندی در اجرای

روش موثر پایین به بالا ارائه می دهد تا یک درخت الگوی مکرر دینامیک نامرتب UDFP-tree و یک درخت الگوی مکرر دینامیک مرتب ODFP-tree بسازد. اولین روش ترتیب آیتم ها را در نظر نمی گیرد، در حالیکه دومین روش ترتیب آیتم ها را اعمال می کند.

بعلاوه، چارچوب پیشنهادی الگوهای نوظهور قوی را استخراج می کند تا یک کلاسه بند قوی و سریع ایجاد کند که می تواند با نویز مقابله کند.

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

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

ارزیابی تجربیات ما بر روی محدوده وسیعی از داده ها، اثربخشی روش پیشنهادی را در مقایسه با دیگر روش های شناخته شده از نظر دقت پیش بینی، تعداد الگوهای استخراجی و زمان اجرا نشان می دهد.

فصل اول: مقدمه

1-1- مقدمه

کلاسه بندی[1] یکی از وظایف اساسی در داده کاوی[2] است که بطور وسیعی در زمینه یادگیری ماشین[3]، شبکه های عصبی[4] و تشخیص الگو[5] مورد مطالعه واقع شده است. ورودی، مجموعه ای از نمونه های آموزشی[6] است که شامل چندین ویژگی[7] است. ویژگی ها با توجه به دامنه مقادیرشان به دو دسته ویژگی های گسسته[8] و ویژگی های پیوسته[9] قابل تفکیک هستند. در حالت کلی، یک کلاسه بند[10]، توصیف مختصر و معنادار (مدل[11]) برای هر برچسب کلاس[12] در رابطه با ویژگی ها تولید می کند. سپس، مدل برای پیش بینی برچسب کلاس نمونه های ناشناخته[13] بکار می رود. کلاسه بندی همچنین بعنوان یادگیری با ناظر[14] نیز شناخته می شود که در آن هر نمونه آموزشی دارای برچسب کلاس است. در حالی که، یادگیری بدون ناظر[15] یا خوشه بندی[16] جستجو می کند و گروه های همگن از اشیا را بر اساس مقادیر ویژگی هایشان دسته بندی می کند؛ در واقع، نمونه ها دارای برچسب کلاس نیستند. کلاسه بندی در محدوده وسیعی از کاربردها از جمله آزمایشات علمی[17]، تشخیص دارو[18]، پیش بینی آب و هوا[19]، تایید اعتبار[20]، تقسیم بندی مشتری[21]، بازاریابی هدف[22] و تشخیص تقلب[23] بطور موفقیت آمیزی بکار می رود.

کلاسه بندی بر پایه الگوها[24]، یک متدلوژی جدید محسوب می شود. کشف الگوهایی که نشاندهنده تمایز بین کلاس های مختلف هستند، یکی از موضوعات مهم در داده کاوی محسوب می شود. در این تحقیق، ما کلاسه بندی را بر اساس الگوهایی به نام الگوهای نوظهور[25] (Emerging Patterns) که تمایز بین کلاس ها را بصورت بارزی نشان می دهند، از مجموعه داده ها[26] استخراج می کنیم و سپس، بر اساس آنها، کلاسه بندی را انجام می دهیم.

2-1-  مفهوم الگوهای نوظهور

مفهوم الگوهای نوظهور برای استخراج دانش از پایگاه داده ها توسط Dong و Li پیشنهاد شده است تا تغییرات قابل توجه بین کلاس ها را به تصویر بکشند [1]. یک الگوی نوظهور، ترکیب عطفی بین ویژگی هایی است که میزان احتمال حضور آن در یک کلاس نسبت به دیگر کلاس ها بطور قابل توجهی تغییر می کند [1،2]. این الگوها مفید هستند به این دلیل که قادر هستند تا وجه تمایز بین کلاس ها را بیان کنند. در صورتی که میزان فراوانی[27] هر الگو که در یک کلاس نسبت به دیگر کلاس ها قابل توجه باشد، نشاندهنده آن است که این الگو، بطور خاص به این کلاس اختصاص دارد و از طرفی این نوع الگوها برای پایگاه داده هایی که بحث محدودیت زمانی برای استخراج دانش از آنها مطرح است، اهمیت ویژه ای می یابند.

استخراج الگوهای نوظهور بدین صورت مطرح می شود: « پیدا کردن آیتم هایی که نرخ رشد[28] آن (که بصورت نسبت احتمال آن آیتم بین کلاس های مختلف تعریف می شود) از مقدار آستانه ای بیشتر باشد.» این مقدار آستانه باید بگونه ای انتخاب شود که الگوهای استخراجی ، تفاوت و تمایز بین کلاس های مختلف را نشان دهند. این الگوها در واقع مجموعه ای از آیتم ها هستند که بیان کننده ترکیب عطفی بین مقادیر ویژگی ها هستند [2].

نوعاً، تعداد الگوهای استخراجی بسیار زیاد است اما فقط شمار کمی از این الگوها برای تحلیل داده ها و کلاسه بندی مطلوب و مفید هستند. از آن جایی که مقدار زیادی

 از این الگوها بی ربط[29] و تکراری[30] هستند، دانش جدیدی را فراهم نمی کنند و لذا تاثیر نامطلوبی بر روی دقت کلاسه بند دارند که موجب کاهش دقت پیش بینی[31] می شوند. برای افزایش کارایی[32] و دقت، بایستی روالی را توسعه داد که الگوهای وابسته و غیر مفید حذف شوند تا شمار این الگوها کاهش یابد.

یک الگوی نوظهور با احتمال بالا در کلاس خودش و احتمال پایین در کلاس مقابلش می تواند برای تعیین یک نمونه تست بکار رود. قدرت این الگو توسط معیارهایی مثل فراوانی نسبی[33] و نرخ رشد ( نسبت احتمال الگو در یک کلاس نسبت به دیگر کلاس ها) آن بیان می شود.

در بسیاری از زمینه های کاربردی مانند کشف دانش از داده های ژنی[34] ، پردازش تصویر[35]، کشف نفوذ[36] ، کشف برون هشته[37]، کشف کلاهبرداری[38] ، داده های نامتوازن[39] ، جریان داده ها[40] ، بیوانفورماتیک[41] ، سیستم های پیشنهاد دهنده[42] ، نیاز است که تغییر ناگهانی در داده ها تشخیص داده شود. الگوهای نوظهور تغییرات ناگهانی و تفاوت های قابل توجه را از داده ها استخراج می کنند. الگوهای نوظهور، در زمینه پردازش تصویر برای قطعه بندی بدین گونه عمل می کند که سعی می کند در پیکسل هایی که تغییر ناگهانی شدت[43] بوجود می آید را بعنوان یک قطعه جدید معرفی کند. در زمینه کشف نفوذ و کلاهبرداری، رفتار داده ها پیگیری می شود، زمانی که رفتار داده ها بصورت ناگهانی تغییر کند، بعنوان نفوذ تشخیص داده می شود. در سیستم های پیشنهاد دهنده، سیستم به دنبال رفتارهای خاص و مختص هر کاربر است تا با کشف ویژگی های خاص هر کاربر، به او محصولات مطابق با علایق و استعدادهای او را پیشنهاد دهد. لذا الگوهای نوظهور در این راستا نقش بسزایی دارند.

3-1- مفهوم ویژگی های جریانی[44]

در داده های جریانی[45]، نمونه ها به مرور زمان دریافت می شوند در حالیکه تعداد ویژگی ها ثابت می باشد. اما در ویژگی های جریانی، تعداد داده های یادگیری ثابت می باشد ولی ویژگی ها بصورت دینامیک تولید می شوند و الگوریتم یادگیری به مرور زمان ویژگی ها را دریافت می دارد [31، 32]. در ویژگی های جریانی روال بدین صورت است ویژگی های توسط روش های تولید ویژگی مانند روش های یادگیری رابطه ای آماری[46] و تعاملات بین ویژگی ها[47]، تولید می شوند. مشکلاتی که در پی تولید ویژگی ها توسط این روش ها بروز می کند بدین شرح است که: 1) میلیون ها و یا حتی بیلیون ها ویژگی تولید می شوند که بدلیل محدودیت های حافظه امکان نگهداری این حجم از ویژگی وجود دارد و از طرفی زمان بسیار زیادی بایستی صرف شود تا فرایند یادگیری شروع شود. 2) ویژگی ها توسط کوئری های موجود در SQL تولید می شوند که اجرای این کوئری ها محدود به زمان پروسسور[48] است تقریبا پروسسور هر صدهزار کوئری را در 24 ساعت اجرا می کند. از طرفی بسیاری از ویژگی ها تولیدی بی ربط و تکراری هستند[49]. این موضوع نشان می دهد که شمار کمی از این ویژگی های تولیدی در عمل در فرایند یادگیری موثر است و لذا تولید ویژگی ها هزینه بر است [32]. بر این اساس برای فائق آمدن بر این مشکلات، مفهوم ویژگی های جریانی شکل گرفت و تلاش شد تا با تولید دینامیک ویژگی ها و بررسی این ویژگی ها در زمان تولید و تاثیر آن بر روال یادگیری فرایند تولید ویژگی ها را هدایت کنند.

برای برخورد با چالش های مطرح شده، بایستی فرایند یادگیری قابلیت پاسخگویی به ویژگی های جریانی را داشته باشد. در واقع، روال یادگیری بایستی بصورت افزایشی با دریافت هر ویژگی قابل بروزرسانی شدن داشته باشد بدون اینکه به اولین مرحله یادگیری بازگردد. لذا در راستای استخراج الگوهای قوی بایستی در ابتدا ویژگی ها بررسی شوند و ویژگی هایی که بی ربط هستند را حذف کرد، سپس از روی ویژگی های مفید و قوی ، الگوها را استخراج کرد.

[1] Classification

[2] Data mining

[3] Machine learning

[4] Neural networks

[5] Pattern recognition

[6] Training instances

[7] Features

[8] Nominal

[9] Numerical

این مطلب را هم بخوانید :

[10] Classifier

[11] Model

[12] Class label

[13] Unknown

[14] Supervised learning

[15] Unsupervised learning

[16] Clustering

[17] Scientific experiments

[18] Medical diagnosis

[19] Weather prediction

[20] Credit approval

مقدمه…………………………………………………………………………………………… 52

بهبود کارایی روش انتشار برچسب در شبکه های ایستا………………………………. 52

پیاده سازی روش پایه………………………………………………………………………… 52

پیاده سازی روش پیشنهادی………………………………………………………………. 53

مجموعه داده ها………………………………………………………………………………… 53

معیار ارزیابی………………………………………………………………………………… 54

نتایج آزمایش ها……………………………………………………………………………. 54

تحلیل نتایج…………………………………………………………………………………. 57

تحلیل پیچیدگی زمانی…………………………………………………………………… 58

تشخیص تشکل های همپوشان در شبکه های پویا…………………………………… 58

مجموعه داده ها………………………………………………………………………….. 59

معیارهای ارزیابی……………………………………………………………………………… 60

نتایج آزمایش ها……………………………………………………………………………… 60

تحلیل نتایج………………………………………………………………………………… 63

تحلیل پیچیدگی زمانی……………………………………………………………………… 64

فصل پنجم: بحث و نتیجه گیری………………………………………………………. 66

نتیجه گیری……………………………………………………………………………………….. 66

 

پیشنهاد ها برای کارهای آینده…………………………………………………………….. 67

منابع و مآخذ…………………………………………………………………………………… 69

چکیده:

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

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

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

فصل اول: مقدمه

مقدمه:

در دنیای امروز، ما با سیستم های پیچیده ای[1] در پیرامون خود احاطه شده ایم، از جامعه که در آن میلیون ها عضو با یکدیگر در حال تعامل هستند تا شبکه های تلفن همراه و کامپیوتر که میلیون ها کاربر را به یکدیگر متصل می‌کنند. همچنین توانایی ما برای استنتاج و درک محیط اطراف، وابسته به شبکه ای از میلیاردها سلو

این مطلب را هم بخوانید :

 

ل عصبی[2] در مغز ماست. این سیستم های پیچیده نقش های بسیار مهمی در جنبه های مختلف زندگی ما ایفا می‌کنند. درک، توصیف، پیش بینی و کنترل این سیستم ها از جمله بزرگترین چالش های ما در جهان مدرن است.

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

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

با توجه به اینکه از سال ها پیش بسیاری از این سیستم ها، مانند: ساختارها و واکنش های زیستی، راه های ارتباطی، روابط اجتماعی و نظایر آن و همچنین دانش مطالعه بر روی سیستم ها و شبکه ها شناخته شده اند، پرسشی که ممکن است مطرح شود این است که چرا اهمیت این موضوع تنها در چند دهه اخیر آشکار شده است؟ پاسخی که می‌توان داد این است که در گذشته ابزارهای مناسبی برای جمع آوری، نگهداری و