ژانویه 19, 2021

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

گراف تنک (یا خلوت)[۳۷]: به گرافی که تعداد یال های آن خیلی کمتر از گراف کامل نظیرش باشد، گراف تنک می‌گویند.
انگیزه انجام این پایان نامه
همانطور که پیشتر نیز اشاره شد، دانش شبکه ها، حوزه مطالعاتی نوینی است که از علوم گوناگون برای تحلیل سیستم های پیچیده بهره می‌برد و کاربردهای متنوع و وسیعی در زمینه های گوناگون از جمله: اقتصاد، سلامت، امنیت، ارتباطات، پژوهش، مدیریت، علوم اجتماعی و کامپیوتر دارد.
موضوعات پژوهشی در این بخش متنوع هستند و از آن جمله می‌توان به: تشخیص اجزای تاثیرگذار در شبکه، تغییرات در شبکه، زیرساختارهای مقاوم، رفتارهای غیر معمول و تشکل ها و گروه ها اشاره کرد. از این میان، بحث تشخیص تشکل ها در شبکه ها دارای کاربردهای عملی زیادی در دنیای واقعی است که برای مثال می‌توان از: تشخیص گروه ها در شبکه های اجتماعی مجازی، تبلیغات هدفمند، دسته بندی صفحات وب، طبقه بندی اسناد، رصد کاربران در شبکه های تلفن همراه و بسیار موارد دیگر نام برد.
در سال های اخیر پژوهشگران بسیاری در این عرصه فعالیت کرده و کارهای قابل توجهی ارائه داده اند، اما همچنان مسائل زیادی برای مطالعه و بررسی بیشتر وجود دارد. رسیدن به زمان اجرای بهتر، دقت بیشتر و قابلیت بکارگیری در مسائل متنوع برخی از معیارهایی است که همچنان برای ارتقای آنها تلاش می‌شود.
در این راستا، این پژوهش با هدف مطالعه روش های موجود و بررسی نقاط ضعف و قوت آنها و همچنین ارائه روش های بهتر آغاز گردید. در قدم اول، مقالات و الگوریتم های موجود مورد بررسی قرار گرفت. سپس معیارهای سنجش کیفیت نتایج که در مجامع علمی قابل استناد هستند و همچنین مجموعه داده‌های[۳۸] معتبر برای آزمایش الگوریتم‌ها گردآوری شد. در قدم بعدی، الگوریتم‌هایی که تاکنون از نتایج بهتری برخوردار بودند بررسی و مقایسه شدند. پس از آن، ایده‌های پیشنهادی، در دو بخش تشخیص تشکل های همپوشان در شبکه های ایستا و شبکه های پویا ارائه و با انجام آزمایش های متعدد، ویژگی ها و توانایی های آنها مورد بررسی قرار گرفت. در نهایت نیز دستاوردهای پژوهش به همراه الگوریتم های پیشنهادی، نتایج و مزایای آن در قالب این پایان نامه ارائه گردید.
نگاه کلی به فصول رساله
این پایان نامه مشتمل بر پنج فصل می‌باشد که در ادامه ی مقدمه، در فصل دوم به بررسی و تحلیل روش های ارائه شده در این حوزه خواهیم پرداخت. در فصل سوم، روش های پیشنهادی با تمامی جزئیات ارائه خواهد شد و در فصل چهارم نتایج حاصل از اجرای آن ها بر روی مجموعه داده های آزمایشی، به همراه تحلیل آورده شده است. در انتها، در فصل پنجم به نتیجه گیری و معرفی کارهای آینده پرداخته ایم.
فصل دوم
فصل دوم: پیشینه تحقیق
مقدمه
بشر همواره به دنبال شناخت و تفسیر هر چه بیشتر محیط و رویدادهای پیرامون خود، به منظور تعامل بهتر با آنها بوده است. مطالعه بر روی روابط اجتماعی، موجودات زنده، پدیده های طبیعی مانند سیل و زلزله و بسیاری موارد دیگر، نمونه هایی از اشتیاق انسان برای درک بیشتر دنیایی است که در آن زندگی می‌کند.
مطالعه و پژوهش بر روی ساختارهایی مانند: راه های ارتباطی، روابط خویشاوندی، تشابه میان موجودیت های مختلف و مواردی از این دست، سبب شد تا شاخه ای از دانش، با عنوان دانش شبکه ها شکل بگیرد. امروزه پژوهش در این عرصه، بیشتر در دو حوزه علوم کامپیوتر و جامعه شناسی مورد توجه است و در آن از ابزارهای مختلفی از جمله: مشاهدات میدانی، تجربیات، مدل ها و قوانین ریاضی استفاده می‌شود.
همانطور که در فصل قبل نیز اشاره شد، برای نتایج حاصل از تحلیل شبکه ها، می‌توان کاربردهای متعددی را در عرصه های مختلف بر شمرد. از جمله: تعیین بهینه راه های مواصلاتی شهری و بین شهری در مهندسی راه، تشخیص نقاط و مراحل حساس در تحلیل سیستم ها، پیش بینی نحوه شیوع یک بیماری واگیردار در علوم بهداشت، دسته بندی اسناد و کتاب های مختلف در طبقه بندی اطلاعات، بهینه سازی نحوه تبادل اطلاعات در شبکه های ارتباطی، طبقه بندی اجرام آسمانی در ستاره شناسی، تشخیص کاربران تاثیرگذار در شبکه های اجتماعی و بسیاری موارد دیگر.
در این فصل، به بررسی یکی از موضوعات مطالعه بر روی شبکه ها، تحت عنوان: تشخیص تشکل ها[۳۹] پرداخته خواهد شد. همچنین پس از آشنایی با مفهوم و تعاریف اولیه، برخی از روش هایی را که در سال های اخیر ارائه شده اند بررسی گردیده و ویژگی های هر یک از آنها به اختصار معرفی خواهند شد.
شبکه های ایستا و شبکه های پویا
از جهات مختلفی می‌توان گراف ها و شبکه ها را دسته بندی کرد. در واقع این دسته بندی ها نمایان گر ویژگی های مشترک اعضای آنها می‌باشد. به عنوان مثال، از لحاظ نوع یال ها، می‌توان گراف ها را به دو گروه گراف های جهت دار و بدون جهت؛ و گراف های وزن دار و بدون وزن تقسیم کرد.
یکی دیگر از مواردی که می‌توان شبکه ها را بر اساس آن دسته بندی کرد، عامل زمان است. شبکه هایی را که ساختار آنها در طول زمان تغییر نمی‌کند و یا برای بررسی، یک وضعیت خاص از آنها در نظر گرفته می‌شود را شبکه های ایستا[۴۰] و شبکه هایی را که با گذشت زمان، ساختار آنها تغییر می‌کند را شبکه های پویا[۴۱] می‌نامند.
به عنوان مثال، شبکه های اجتماعی، نمونه ای شبکه های پویا هستند. این شبکه ها دائما در طول زمان در حال تغییر می‌باشند. ورود اعضای جدید به شبکه، ایجاد رابطه های جدید بین اعضا، ترک شبکه توسط برخی از کاربران و یا قطع برخی از روابط بین اعضا، نمونه هایی از تغییرات ایجاد شده در ساختار شبکه های اجتماعی در طول زمان است. این تغییرات در ساختار شبکه، ایجاب می‌کند که تحلیل های مورد نیاز، دائما مورد بازبینی و بروز رسانی قرار گیرند.
تصویر ۱۱: نمونه یک شبکه پویا و تغییرات آن در چهار برش زمانی
تشکل های غیر همپوشان[۴۲] و تشکل های همپوشان[۴۳]
یکی از موضوعات کاربردی در زمینه تحلیل شبکه‌ها، شناسایی تشکل‌ها در شبکه است. می‌توان هر تشکل را توده‌ای متراکم از رئوس در نظر گرفت که از طریق یالهای اندکی با تشکل‌های دیگر در ارتباط است. به عنوان مثال دانشجویان یک دانشکده که در یک شبکه اجتماعی با یکدیگر ارتباط دارند، یک تشکل را تشکیل می‌دهند.
اگر اعضای یک شبکه، تنها امکان عضویت در یک تشکل را داشته باشند، تشکل های ایجاد شده غیر همپوشان خواهند بود، یعنی هیچ تشکلی با سایر تشکل ها عضو مشترک نخواهد داشت. به عنوان مثال، در شبکه بازیکنان فوتبال، هر بازیکن در یک دوره از مسابقات، تنها در یک تیم بازی می‌کند و نمی‌تواند در تیم دیگری نیز حضور داشته باشد.
اگر اعضای یک شبکه، بتوانند در یک یا چند تشکل عضو شوند، تشکل های ایجاد شده همپوشان خواهند بود، یعنی ممکن است در شبکه تشکل هایی وجود داشته باشند که با برخی از تشکل های دیگر یک یا چند عضو مشترک داشته باشند. به عنوان مثال، در یک شبکه اجتماعی، یک کاربر ممکن است در گروه همکلاسی های دوران دبیرستان خود عضو بوده و همزمان در یک گروه موسیقی نیز عضویت داشته باشد و یا از طرفداران یک باشگاه ورزشی هم باشد.
در واقع می‌توان گفت که تشکل های غیر همپوشان حالت خاصی از تشکل های همپوشان هستند. معمولا شبکه هایی که امروزه با آنها سر و کار داریم و بررسی و تحلیل آنها برای ما مورد توجه هستند، شبکه هایی هستند که دارای تشکل های همپوشان می‌باشند. شبکه های ارتباط های تلفنی و پیامکی کاربران تلفن همراه، نامه های الکترونیک کاربران پست الکترونیک، وب سایت های موجود در شبکه اینترنت، کاربران شبکه های اجتماعی، روابط خویشاوندی و بسیاری موارد دیگر، نمونه هایی از شبکه هایی هستند که دارای تشکل های همپوشان می‌باشند.
تصویر ۱۲: تشکل های غیر همپوشان (راست) و تشکل های همپوشان (چپ)
تعریف مسئله
به طور کلی مسأله شناسایی ساختارهای تشکل دارای همپوشانی در شبکه ها به صورت زیر تعریف می‌شود:
با در نظر گرفتن شبکه، به صورت گراف G=(N,E)، که در آن N مجموعه رأس ها و E مجموعه یال ها می‌باشد، هدف، پیدا کردن یک تقسیم بندی شبکه به زیرمجموعه های (خوشه های[۴۴]) N1، N2،….،NC از رأس های آن است، به طوریکه در کنار ارضا شدن دو شرط زیر، تقسیم بندی حاصل، هر چه بیشتر به تقسیم بندی ذاتی شبکه نزدیک تر باشد.
به ازای تعدادی از زیرمجموعه ها (به عبارت دیگر بعضی از زیرمجموعه ها با یکدیگر همپوشانی دارند).
شرط دوم، در شبکه هایی که ساختار تشکل آن ها دارای همپوشانی نیست به صورت بیان می‌شود. اگر در شبکه ی مورد نظر، هم ساختارهای تشکل دارای همپوشانی و هم ساختارهای تشکل غیر همپوشان داشته باشیم، هر دو حالت مورد نظر از شرط دوم، برقرار می‌باشد.
با این وجود، اگرچه به نظر می‌آید که حل مسأله ی تشخیص تشکل بدیهی است، اما مشکل عمده ی این حوزه این است که اجزای اصلی این مسأله (بخصوص تعریف ساختار تشکل) هنوز دارای تعریف مشخص و قطعی نیستند. در نتیجه اغلب ابهامات مختلف در تعاریف این اجزا وجود داشته و همین امر باعث شده است که روش های بسیاری برای حل این مسأله پیشنهاد شود.
یکی از این مشکلات، پیدا کردن یک معیار دقیق، قابل قبول و متناسب با تعریف ساختار تشکل است. با توجه به این که تعریف ساختار تشکل به شدت به نوع شبکه ی در دسترس و کاربرد آن وابسته است، هیچ معیاری که تماما مورد قبول باشد موجود نیست. با این حال تعریفی که بیشتر مورد استفاده قرار می‌گیرد، به صورت خیلی ساده بیان می‌کند که تعداد یال های هر تشکل نسبت به یال های بین تشکل های مختلف می‌بایست بسیار بیشتر باشد. این تعریف ساده اساس بسیاری از تعاریف موجود را تشکیل می‌دهد.
به طور کلی محققان شبکه های اجتماعی سه تعریف کلی را برای ساختار تشکل ارائه داده اند:

برای دانلود متن کامل این پایان نامه به سایت  fumi.ir  مراجعه نمایید.

  • محلی[۴۵] : طبق این تعریف، هر تشکل مستقل از کل گراف ارزیابی می‌شود.
  • جهانی[۴۶] : در اینجا هر تشکل با توجه به کل گراف بررسی می‌شود.
  • شباهت رأس[۴۷] : تشکل ها را گروه هایی از رئوس شبیه به یکدیگر در نظر می‌گیرند.