بخشی از مقاله
چکیده
در دهه فعلی، شبکههای اجتماعی با رشد روز افزونی در حال توسعه هستند. یکی از ویژگیهای بسیار مهم در شبکههای اجتماعی وجود جوامع در آنها است. در روش پیشنهادی قصد داریم الگوریتم رقابت استعماری را با ضریب خوشهبندی و گشت بسته ترکیب کنیم تا دقت تشخیص جامعه را در شبکههای اجتماعی نسبت به روشهای قبلی بالا ببریم. برای این منظور در الگوریتم رقابت استعماری برای تعیین استعمارگرها و همچنین در هنگام محاسبه هزینه کل امپراتوری از ضریب خوشهبندی و گشت بسته استفاده میکنیم. برای ارزیابی روش پیشنهادی از دو معیار اطلاعات متقابل هنجارسازی شده و پیمانه استفاده شده است؛
همچنین مقایسهها را بر روی دو مجموعه داده یوتیوب و فیسبوک انجام دادهایم. نتایج نشان میدهد روش پیشنهادی از نظر معیار اطلاعات متقابل هنجارسازی شده بر روی مجموعه داده یوتیوب، در مقایسه با روش Walktrap به میزان 0,065 درصد و بر روی مجموعه داده فیسبوک در مقایسه با روش GCE به میزان 0,074 درصد بهبود داشته است؛ همچنین روش پیشنهادی از نظر معیار پیمانه بر روی مجموعه داده یوتیوب، در مقایسه با روش CNM به میزان 0,027 درصد و بر روی مجموعه داده فیسبوک در مقایسه با روش COPRA به میزان 0,028 درصد بهبود داشته است. به طور کلی روش پیشنهادی، تشخیص جامعه را نسبت به روشهای دیگر بهبود بیشتری میدهد.
کلید واژه- الگوریتم رقابت استعماری، ضریب خوشهبندی، گشت بسته، تشخیص جامعه
.1 مقدمه
معنای عمومی جامعه در شبکههای اجتماعی، گردآمدن تعدادی گره - کاربران، مقالات و غیره - میباشد، به طوری که اعضای این جامعه بیشترین تعاملات را با یکدیگر داشته باشند و روابط خارج از جامعه آنها کمترین مقدار را به خود اختصاص دهد. یک اجتماع از نظر درونی ارتباطات متراکمتر و چگالتری نسبت به جوامع بیرونی دارد. جوامع اطلاعات ارزشمندی در مورد نوع ارتباط کاربران، نحوه انتقال اطلاعات بین آنها و نحوه توزیع کاربران در شبکههای اجتماعی فراهم میکنند و در واقع به عنوان جزء اصلی این شبکهها محسوب میشوند.
مسئله تشخیص جوامع از مسائل مهم در بسیاری از زمینهها مثل شبکههای کامپیوتری، سیستمهای توصیهگر و شبکههای بیسیم است و لذا محققان زیادی از رشتههای مختلف، تحقیقات متنوعی را پیرامون آن انجام دادهاند. ما با تشخیص جوامع میتوانیم رفتارهای گروهی متداول را دستهبندی و مطالعه هر قسمت را به صورت متمرکز انجام دهیم. این حوزه تحقیقاتی، هنوز یک موضوع چالشبرانگیز در شبکههای اجتماعی به حساب میآید، از این رو این روشها هنوز هم در حال گسترش و بهبود کارایی هستند .[1]
.2 کارهای پیشین
در مقاله [2 ] یک الگوریتم سلسله مراتبی جدید برای تشخیص جامعه ارائه شده است. رویکرد این روش مبتنی بر سقوط تراکم بین هر جفت از گرههای پدر و فرزند در نمودار دندروگرام1 است. بر این اساس کاهش چگالی بالاتر، احتمال اینکه فرزند یک جامعه مستقل را تشکیل دهد، بیشتر میکند؛ بنابراین بر اساس قضیه حداکثر جریان حداقل برش2، یک الگوریتم جدید که میتواند یک مجموعه بهینه از جوامع محلی را به طور خودکار پیدا کند، پیشنهاد شده است. در مقاله [3 ] برای تشخیص جوامع یک الگوریتم مبتنی بر انتشار ساده که نیاز به هیچ پیشبینی دانشی ندارد، پیشنهاد شده است. ایده اصلی این روش، ارائه انواع مختلف خوشهها از طریق یک روش ظریفسازی خوشه سلسله مراتبی مناسب است.
در مقاله [4] یک استراتژی برای بهبود الگوریتمهای تشخیص جامعه موجود، پیشنهاد میشود که در آن با اضافه کردن یک مرحله پیشپردازش، به یالها با توجه به مرکزیتشان در توپولوژی شبکه وزن داده میشود. در این روش، مرکزیت یال نشان دهنده همکاری آن در تراگذری3 گراف است. در این استراتژی به طور موثر تلاش میشود اطلاعات در مورد توپولوژی شبکه کامل شود و بتوانیم آن را به عنوان یک ابزار اضافی به منظور ارتقاء تشخیص جامعه مورد استفاده قرار دهیم. محاسبه مرکزیت یال با انجام گشتهای متعدد تصادفی با طول محدود بر روی شبکه انجام میشود، که باعث میشود محاسبات مرکزیت یال در شبکههایی در مقیاس بزرگ نیز عملی شود.
مقاله [5] از مفهوم تئوری فازی و خوشهبندی فازی برای تشخیص جامعه الهام گرفته است. در این روش میزان تعلق هر عضو در شبکه اجتماعی با استفاده از یک معیار فازی مشخص شده و سپس بر اساس این درجههای عضویت، تعلق گرههای مختلف در شبکه تعیین میشود. در مقاله [6] از مفهوم خوشهبندی زیر فضا برای تشخیص جامعه استفاده شده است. در این روش تلاش شده تا جوامعی با حداکثر تراکم به عنوان جوامع نهایی شناخته شوند، که برای این کار از مفهوم گشت تصادفی استفاده شده است.
.3 روش پیشنهادی
الگوریتم رقابت استعماری4 یکی از قدرتمندترین الگوریتمهای تکاملی است که توسط آتش پز و لوکاس [7] ابداع شد و تاکنون در مسائل زیادی مانند طراحی ساختار اسکلت [8]، موتور القایی خطی [9] و غیره استفاده شده است. دلایل استقبال زیاد از این الگوریتم علاوه بر کارایی مناسب، سرعت همگرایی و توانایی بهینهسازی بالا در مقایسه با سایر الگوریتمهای موجود در حوزه بهینهسازی است. این الگوریتم همانند سایر روشهای بهینهسازی تکاملی، با تعدادی جمعیت اولیه تصادفی شروع میشود که هر کدام از آنها یک کشور نامیده میشوند. کشورها شامل دو دسته هستند. استعمارگر5 که تعدادی از بهترین عناصر جمعیت است و با علامت ستاره آن را نشان میدهیم و مستعمره6 که باقیمانده جمعیت است و با علامت دایره نشان داده میشود. مستعمرات و استعمارگر، با هم تعدادی امپراتوری اولیه را تشکیل میدهند.
در روش پیشنهادی قصد داریم الگوریتم رقابت استعماری را با ضریب خوشهبندی و گشت بسته ترکیب کنیم، تا دقت تشخیص جامعه را در شبکههای اجتماعی نسبت به روشهای قبلی بالا ببریم. در مقاله پایه [10] یک روش جدید برای تشخیص جامعه با ادغام دو مفهوم ضریب خوشهبندی7 و گشت بسته8 پیشنهاد شده است، که چشم انداز جدیدی را برای فهم ساختار جامعه در شبکههای پیچیده فراهم میکند. بنابراین طبق فلوچارت شکل 1، در روش پیشنهادی از این دو مفهوم برای تعیین استعمارگرها و محاسبه هزینه کل امپراتوری در الگوریتم رقابت استعماری استفاده میکنیم. • ضریب خوشهبندی یال ضریب خوشهبندی یال شبیه به مفهوم ضریب خوشهبندی گره است و برابر است با تعداد ساختارهای حلقوی که یک یال مشخص به آن تعلق دارد، تقسیم بر تعداد ساختارهای حلقوی که ممکن است به طور بالقوه شامل آن یال باشد. در صورتی
