بخشی از مقاله
چکیده
مسئله تشخیص جوامع از مسائل مهم در بسیاری از زمینهها مثل شبکههای کامپیوتری، سیستمهای توصیهگر و شبکههای بیسیم است و لذا محققان زیادی از رشتههای مختلف، تحقیقات متنوعی را پیرامون آن انجام دادهاند. در روش پیشنهادی قصد داریم ابتدا معایب الگوریتم رقابت استعماری را با استفاده از عملگرهای اصلی الگوریتم ژنتیک رفع کنیم و سپس با ترکیب الگوریتم رقابت استعماری با ضریب خوشهبندی و گشت بسته دقت تشخیص جامعه را در شبکههای اجتماعی نسبت به روشهای قبلی بالا ببریم. برای این منظور در الگوریتم رقابت استعماری از عملگر برش در هنگام حرکت مستعمرهها به سمت استعمارگر و از عملگر جهش برای انتخاب یکی از کشورها به صورت تصادفی استفاده کرده و همچنین برای تعیین استعمارگرها و محاسبه هزینه کل امپراتوری از ضریب خوشهبندی و گشت بسته استفاده میکنیم.
برای ارزیابی روش پیشنهادی از دو معیار اطلاعات متقابل هنجارسازی شده و پیمانه استفاده شده است؛ همچنین مقایسهها را بر روی دو مجموعه داده یوتیوب و فیسبوک انجام دادهایم. نتایج نشان میدهد روش پیشنهادی از نظر معیار اطلاعات متقابل هنجارسازی شده بر روی مجموعه داده یوتیوب، در مقایسه با روش Fast Greedy به میزان 0,41 درصد و بر روی مجموعه داده فیسبوک در مقایسه با روش GCE به میزان 0,37 درصد بهبود داشته است؛ همچنین روش پیشنهادی از نظر معیار پیمانه بر روی مجموعه داده یوتیوب، در مقایسه با روش DDA-M1 به میزان 0,11 درصد و بر روی مجموعه داده فیسبوک در مقایسه با روش DDA-M2 به میزان 0,24 درصد بهبود داشته است. به طور کلی روش پیشنهادی، تشخیص جامعه را نسبت به روشهای دیگر بهبود بیشتری میدهد.
.1 مقدمه
در دهه فعلی، شبکههای اجتماعی با رشد روز افزونی در حال توسعه هستند. یکی از ویژگیهای بسیار مهم در شبکههای اجتماعی وجود جوامع در آنها است. ما با تشخیص جوامع میتوانیم رفتارهای گروهی متداول را دستهبندی و مطالعه هر قسمت را به صورت متمرکز انجام دهیم .[1] در روش پیشنهادی تلاش شده تا با ترکیب الگوریتم رقابت استعماری با دو مفهوم ضریب خوشهبندی و گشت بسته، یک روش جدید برای تشخیص جامعه ارائه شود. الگوریتم رقابت استعماری روشی در حوزه محاسبات تکاملی است که به یافتن پاسخ بهینه مسائل مختلف بهینهسازی میپردازد. این الگوریتم با مدلسازی ریاضی فرایند تکاملی اجتماعی- سیاسی انسان، الگوریتمی برای حل مسائل ریاضی بهینهسازی ارائه میدهد.
.2 کارهای پیشین
مقاله [2] از مفهوم تئوری فازی و خوشهبندی فازی برای تشخیص جامعه الهام گرفته است. در این روش میزان تعلق هر عضو در شبکه اجتماعی با استفاده از یک معیار فازی مشخص شده و سپس بر اساس این درجههای عضویت، تعلق گرههای مختلف در شبکه تعیین میشود. در مقاله [3] از مفهوم خوشهبندی زیر فضا برای تشخیص جامعه استفاده شده است. در این روش تلاش شده تا جوامعی با حداکثر تراکم به عنوان جوامع نهایی شناخته شوند، که برای این کار از مفهوم گشت تصادفی استفاده شده است. در مقاله [4] با استفاده از روش معیار مرکزیت یال، یک روش جدید برای تشخیص جامعه ارائه شده است. نتایج شبیهسازی نشان میدهد که این روش هم در شبکههای اجتماعی وزندار و هم بدون وزن میتواند با دقت مناسبی جوامع را تشخیص دهد.
در مقاله [5] یک روش مبتنی بر شباهت برای تشخیص جامعه ارائه شده است. در این روش تلاش شده تا مشکل روشهای پیشتر ارائه شده برای تشخیص جامعه که از روشهای سنتی خوشهبندی استفاده میکنند، حل شود. همچنین در مقاله [6] از مفهوم همسایگی محلی برای تشخیص جامعه استفاده شده است. در این روش یک معیار جدید با استفاده از مفهوم جوامع محلی ارائه شده است و با استفاده از این مفهوم به تشخیص جامعه پرداخته میشود.
.3 روش پیشنهادی
الگوریتم رقابت استعماری1، همانند سایر روشهای بهینهسازی تکاملی، با تعدادی جمعیت اولیه شروع میشود. در این الگوریتم هر عنصر جمعیت، یک کشور نامیده میشود. کشورها به دو دسته استعمارگر2 و مستعمره3 تقسیم میشوند. هر استعمارگر، بسته به قدرت خود تعدادی از کشورهای مستعمره را به سلطه خود درآورده و آنها را کنترل میکند. سیاست جذب و رقابت استعماری، هسته اصلی این الگوریتم را تشکیل میدهند. سیاست جذب توسط کشورهای استعمارگر در مستعمراتشان اعمال میشود. در این الگوریتم، این سیاست با حرکت دادن مستعمرات یک امپراتوری صورت میپذیرد.
در روش پیشنهادی قصد داریم ابتدا معایب الگوریتم رقابت استعماری را با استفاده از عملگرهای اصلی الگوریتم ژنتیک رفع کرده و سپس با ترکیب آن با ضریب خوشهبندی و گشت بسته دقت تشخیص جامعه را در شبکههای اجتماعی نسبت به روشهای قبلی بالا ببریم. برای این منظور در الگوریتم رقابت استعماری از عملگر برش در هنگام حرکت مستعمرهها به سمت استعمارگر و از عملگر جهش برای انتخاب یکی از کشورها به صورت تصادفی استفاده کرده و همچنین برای تعیین استعمارگرها و محاسبه هزینه کل امپراتوری از ضریب خوشهبندی و گشت بسته استفاده میکنیم. در مقاله پایه [7] یک روش جدید برای تشخیص جامعه با ادغام دو مفهوم ضریب خوشهبندی4 و گشت بسته5 پیشنهاد شده است، که چشم انداز جدیدی را برای فهم ساختار جامعه در شبکههای پیچیده فراهم میکند. فلوچارت شکل 1، مراحل روش پیشنهادی را نشان میدهد.
.1-3 مزایای الگوریتم رقابت استعماری
الگوریتم رقابت استعماری نسبت به سایر روشهای الهام گرفته شده از طبیعت مزایای زیادی دارد.
· نو بودن ایده پایهای الگوریتم
· مبتنی بر رفتار اجتماعی انسان که هوشمندانهتر از رفتارهای بیولوژیکی او است.
· توانایی بهینهسازی توابعی با تعداد متغیرهای بسیار زیاد
.2-3 معایب الگوریتم رقابت استعماری
الگوریتم رقابت استعماری اگر چه الگوریتمی بسیار قدرتمند برای بهینهسازی توابع چند متغیره است، اما ایراداتی نیز دارد. ضعف در جستجوی کامل محیط: وقتی ابعاد مسئله بسیار زیاد شود، الگوریتم از جستجوی کامل فضای حالت عاجز خواهد شد. همگرایی بسیار سریع: الگوریتم، بسیار سریع به نقاط بهینهی محلی میل میکند و بنابراین باید بارها دوباره اجرا شود. قفل کردن: گاهی وضعیتی بوجود میآید که باعث میشود تغییراتی که توسط عملگر الگوریتم اتفاق میافتد - جابهجایی کشورها بین امپراتوریها - در یک حلقه بسته بارها و بارها تکرار شود و تنها راه حل این خواهد بود که الگوریتم دوباره اجرا شود. عملگرهای اصلی الگوریتم ژنتیک - عملگر برش و عملگر جهش - میتوانند معایب الگوریتم رقابت استعماری را بهبود دهند .[8] - 1 جستجوی کاملتر محیط - 2 رفع همگرایی سریع - 3 باز کردن قفل الگوریتم
.3-3 ویژگیهای الگوریتم ژنتیک
الگوریتم ژنتیک در مسائلی که فضای جستجوی بزرگی داشته باشند میتواند به کار گرفته شود . در مسائلی با فضای فرضیه پیچیده که تأثیر اجزای آن در فرضیه کلی ناشناخته باشد میتوان از الگوریتم ژنتیک برای جستجو استفاده نمود. این الگوریتم برای بهینهسازی گسسته بسیار مورد استفاده قرار میگیرد، و میتوان به راحتی آن را به صورت موازی اجرا نمود.
