ژانویه 23, 2021

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

نمودار ۴: عملکرد الگوریتم ها بر روی شبکه با اندازه ۵۰۰۰ گره، µ=۰٫۰۳، میزان گره های همپوشان ۱۰% و اندازه تشکل ها بین ۲۰ تا ۱۰۰ گره
نمودار ۵: عملکرد الگوریتم ها بر روی شبکه با اندازه ۵۰۰۰ گره، µ=۰٫۰۳، میزان گره های همپوشان ۵۰% و اندازه تشکل ها بین ۱۰ تا ۵۰ گره
نمودار ۶: عملکرد الگوریتم ها بر روی شبکه با اندازه ۵۰۰۰ گره، µ=۰٫۰۳، میزان گره های همپوشان ۵۰% و اندازه تشکل ها بین ۲۰ تا ۱۰۰ گره
نتایج آزمایش ها بر روی مجموعه داده های واقعی
برای مشاهده عملکرد الگوریتم ها بر روی داده های واقعی، از شبکه روابط دوستی میان دانش آموزان یک دبیرستان استفاده شده است. این شبکه شامل ۶۹ دانش آموز می‌باشد که بنابر نتایج نظرسنجی از آنها، در ۶ تشکل قرار گرفته اند. میانگین درجه در این شبکه ۶٫۴ می‌باشد. حتی با وجود اینکه هیچ همپوشانی در میان این تشکل ها وجود ندارد، هر یک از الگوریتم ها تعدادی از گره ها را به عنوان همپوشان تشخیص داده است. نتایج حاصل از عملکرد الگوریتم ها در جدول ۲ آمده است (۹).
 
تصویر ۱۳: شبکه دوستی دانش آموزان دبیرستان و تشکل های آن
 
جدول ۲: نتایج حاصل از عملکرد الگوریتم های مورد آزمایش بر روی مجموعه داده شبکه دوستی دانش آموزان دبیرستان، به همراه تعداد تشکل های تشخیص داده شده، گره های همپوشان (یا تعداد آنها) و معیار NMI
تحلیل نتایج
با توجه به بررسی های انجام شده و نتایج به دست آمده از آزمایش ها، می‌توان نتیجه گرفت که الگوریتم های SLPA، OSLOM، LFM، COPRA و GCE در مقایسه با سایر الگوریتم ها، در شبکه های بزرگتر عملکرد بهتری داشته اند و الگوریتم های SLPA، LFM، CIS و Game در شبکه های تنک[۹۴]، کارایی بهتری ارائه داده اند. همچنین COPRA، GCE و UEOC در برخی از شبکه ها، دچار تشخیص بیش از حد شده اند که این موضوع می‌تواند باعث کاهش دقت و بازدهی آنها شود.
علاوه بر ارزیابی هایی که به آنها اشاره شد، معیارهای دیگری نیز در انتخاب الگوریتم مناسب تاثیرگذار هستند. یکی از مهم ترین این معیارها، پیچیدگی زمانی الگوریتم است. روشی که بتواند با پیچیدگی زمانی کمتری به نتایج مطلوب برسد برای کاربردهای واقعی گزینه مناسب تری محسوب می‌شود. از آنجا که تحلیل های ارائه شده، تنها بر روی گراف های بدون وزن و بدون جهت ارائه شد، در مواردی که نیاز به تحلیل شبکه های وزن دار یا جهت دار باشد، الگوریتم هایی که امکان پوشش این نوع شبکه ها را نیز داشته باشند، توانایی بهتری خواهند داشت. برای نمونه، الگوریتم های SLPA و CPM امکان تطابق برای کار روی گراف های وزن دار و جهت دار را نیز دارا می‌باشند.
تشخیص تشکل های همپوشان در شبکه های پویا
اگرچه کارهای بسیار زیادی برای تشخیص تشکل ها در شبکه های ایستا انجام پذیرفته است، هنوز کار عمده ای در زمینه شبکه های پویا صورت نگرفته است. برخی از دلایلی که می‌توان برای این مسئله بیان کرد به شرح زیر است:

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

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

البته از سوی دیگر، روز به روز نیاز بیشتری به روش ها و الگوریتم هایی که بتوانند بر روی شبکه های پویا عمل کنند، احساس می‌شود. به عنوان مثال، در شبکه های اجتماعی مجازی و یا شبکه های ارتباطی تلفن همراه و پست الکترونیک، هر لحظه اطلاعات زیادی در مورد روابط کاربران و ویژگی های آنها به سیستم اضافه می‌شود و با توجه به حجم زیاد این داده ها و محدودیت های فنی، نیاز به استفاده از روش هایی که کارایی بهتری داشته باشند بیش از پیش احساس می‌شود.
جمع بندی
شبکه ها را می‌توان بر اساس معیارهای مختلفی طبقه بندی کرد. یکی از این معیارها، تغییر پذیری با زمان می‌باشد که بر طبق آن، می‌توان شبکه را به دو دسته ایستا و پویا تقسیم کرد. ساختار شبکه های پویا در طول زمان تغییر می‌کند.
یکی از موضوعات کاربردی در زمینه تحلیل شبکه ها، تشخیص تشکل ها می‌باشد. هر تشکل توده‌ای متراکم از رئوس است که از طریق یالهای اندکی با تشکل‌های دیگر در ارتباط است. به عنوان مثال، طرفداران یک صفحه هنری در یک شبکه اجتماعی، یک تشکل محسوب می‌شوند. تشکل ها ممکن است اعضای مشترکی با یکدیگر داشته باشند که در این صورت به آنها تشکل های همپوشان می‌گویند.
روش های متعددی برای تشخیص تشکل های همپوشان در شبکه های ایستا ارائه شده اند اما تا بحال روش متمایزی برای شبکه های پویا مطرح نشده است. در اینجا به اختصار به برخی از این روش ها اشاره می‌کنیم:
نفوذ دسته: این روش بر این فرض استوار است که یک تشکل دربرگیرنده چندین مجموعه همپوشان از زیرگراف‌های کاملا متصل است و تشکل‌ها را با جستجو در دسته‌های مجاور تشخیص می‌دهد. در ابتدا دسته‌هایی با اندازه k پیدا شده و در قدم بعدی گراف جدیدی بر اساس اتصال این دسته‌ها را تشکیل می‌دهد که در آن هر گره نشان دهنده یک دسته است. بخش هایی که در گراف جدید اتصال بیشتری با یکدیگر دارند، یک تشکل را نشان می‌دهند. از آنجا که یک گره از گراف اصلی می‌تواند در چندین دسته حضور داشته باشد، بنابراین امکان تشخیص تشکل‌های همپوشان وجود خواهد داشت. این روش برای شبکه‌هایی که اتصالات زیادی دارند مناسب است. مطالعات عملی نشان داده است که مقدار کوچک k ( بین ۳ تا ۶ ) می‌تواند جواب خوبی را به همراه داشته باشد. CFinder یکی از الگوریتم‌های مبتنی بر این روش است و می‌تواند با پیچیدگی زمانی چند جمله ای به حل مسئله بپردازد. این الگوریتم در کار روی شبکه‌های واقعی با اندازه بزرگ، معمولا با مشکل مواجه می‌شود.
افراز گراف و دسته بندی یال ها: در این روش بجای جستجوی مستقیم تشکل‌ها، اتصالات بین گره‌ها به چند مجموعه افراز می‌شوند. گره‌ای در گراف اصلی که اتصالات آن در بیش از یک مجموعه افراز شده باشد، به عنوان همپوشان تشخیص داده می‌شود. اگرچه این روش برای تشخیص همپوشانی منطقی به نظر می‌رسد اما تضمینی وجود ندارد که تشخیص از روی یال ها نتایج بهتری نسبت به بررسی خود گره‌ها ارائه دهد، زیرا این روش تعریف روشنی از تشکل‌ها ندارد. CDAEO یکی از الگوریتم‌هایی است که بر پایه این روش طراحی شده‌اند.
بسط محلی و بهینه سازی: این روش بر اساس توسعه تشکل‌های طبیعی یا تشکل‌های جزیی استوار است. همچنین برای تشخیص کیفیت تشکل‌های مشخص شده از تابعی محلی استفاده می‌کند. یکی از نقاط ضعف این روش این است که کیفیت تشکل‌های نهایی شناسایی شده و نتایج به انتخاب هسته‌های اولیه بستگی دارد. البته روش‌هایی برای انتخاب هوشمندانه هسته‌های اولیه نیز ارائه شده است که تا حدی به رفع این مشکل کمک می‌کند. LFM، OSLOM و GCE نمونه‌هایی از الگوریتم‌های طراحی شده بر اساس این روش هستند.
تشخیص فازی: در این روش، برای هر گره یک بردار از درجه عضویت‌های آن در تشکل‌های مختلف محاسبه می‌شود. هدف این روش تعیین مناسب‌ترین مقادیر عضویت[۹۵] در تشکل‌ها برای هر گره، با استفاده از کمینه کردن یک تابع خطا می‌باشد. یکی از نقاط ضعف این روش، نیاز به انتخاب تعداد تشکل‌ها به عنوان یک پارامتر از ابتدا می‌باشد. برای حل این مشکل راه‌هایی از جمله اجرای الگوریتم به ازای مقادیر مختلف برای تعداد تشکل‌ها، تا جایی که جواب به دست آمده بهبود نیابد، ارائه شده است. MOSES از جمله الگوریتم‌هایی است که بر اساس روش تشخیص فازی طراحی شده‌اند.
الگوریتم های پویا و مبتنی بر عامل: انتشار برچسب نمونه‌ای از الگوریتم‌های پویا است که در آن گره‌هایی که یک برچسب را دارند یک تشکل را تشکیل می‌دهند و هر گره می‌تواند دارای چندین برچسب باشد. روش به این صورت است که در ابتدا به هر گره برچسبی (معمولا شناسه آن گره) نسبت داده می‌شود و در چندین مرحله این برچسب‌ها در شبکه گسترش یافته و برچسب‌هایی که طرفدار بیشتری دارند به عنوان برچسب یک تشکل شناخته می‌شوند. در برخی از نمونه‌ها، گره‌ها دارای حافظه‌ای می‌باشند که در آن اطلاعات برچسب‌هایی را که تا به حال مشاهده کرده‌اند نگهداری می‌کنند و از آن برای تصمیم‌گیری در مورد انتخاب برچسب بهره می‌برند. COPRA و SLPA دو نمونه از الگوریتم‌های پویا هستند.
همچنین روش‌های چند عامله[۹۶] مبتنی بر تئوری بازی‌ها نیز ارائه شده است که در آن هر گره به عنوان یک عامل خودخواه شناخته شده و می‌تواند با توجه به تصمیم خود، به یک تشکل ملحق شده و یا از آن خارج شود. این فرایند زمانی خاتمه می‌یابد که گره‌ها به تعادل[۹۷] برسند و تمایلی به تغییر در تشکل‌های خود نداشته باشند. زمان زیاد برای رسیدن به تعادل یکی از مشکلات این روش است. از الگوریتم‌هایی که بر اساس تئوری بازی‌ها طراحی شده‌اند، می‌توان به Game اشاره کرد.
روش های دیگر: علاوه بر موارد فوق، روش‌های متعددی با پیاده سازی مختلف وجود دارند که هر کدام دارای نقاط ضعف و قوت می‌باشند. برخی از این نقاط ضعف عبارتند از: زمان اجرای زیاد، حساسیت به شرایط اولیه، نیاز به تعیین مقادیر پارامترهای مختلف، عدم کارایی در گراف‌های با اتصال کم و عدم امکان مقیاس‌پذیری.
فصل سوم
فصل سوم: ارائه راه حل و روش های پیشنهادی
مقدمه
همانطور که در فصل قبل اشاره شد، روش های متعددی برای تحلیل شبکه های ایستا ارائه شده است اما تاکنون کار چندانی بر روی شبکه های پویا صورت نگرفته است. همچنین روش هایی که ارائه شده اند دارای نقاط ضعفی هستند که زمینه را برای مطالعه بیشتر به منظور ارتقا و بهبود آنها فراهم می‌آورد.
در این فصل به ارائه دو روش پیشنهادی می‌پردازیم:

  1. روش اول برای بهبود کارایی الگوریتم SLPA که با توجه به نتایج منتشر شده، در حال حاضر یکی از بهترین الگوریتم های موجود برای تشخیص تشکل ها در شبکه های ایستا می‌باشد، ارائه شده است.