بررسی تشخیص جوامع در شبکه‌های پیچیده مبتنی بر الگوریتم‌های فراابتکاری

بخش اول:

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

 

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

شبکه‌های پیچیده از دهه 1930 مورد مطالعه و رشد قرار گرفته‌اند. یکی از مشکلات تحلیل شبکه‌های پیچیده، شناسایی و استخراج جوامع از یک گراف است. بسیاری از شبکه‌های اجتماعی لینک‌های درون جامعه قوی‌تری نسبت به گره‌های سایر جوامع دارند. چندین روش برای شناسایی جوامع در سال‌های اخیر پیشنهاد شده است. با این حال، تشخیص دقیق یک جوامع و طبقه‌بندی اعضای آن همچنان مسئله دشواری است. تکنیک‌های تشخیص جامعه غیرهمپوشان NOCD  و تشخیص جامعه همپوشان OCDNOC و تشخیصجامعه ساختاری استفاده شده است. با تجزیه و تحلیل محتوای گره‌های متعلق به یک جامعه که نمایه‌ها یا علایق مشترک دارند، رویکرد تشخیص جوامع را می‌توان به تکنیک‌های تشخیص مبتنی بر محتوا و ترکیبی ساختار و محتوا تقسیم کرد   بسیاری از مطالعات قبلی نشان داده‌اند که استفاده از اطلاعات ساختار یا محتوا به تنهایی برای شناسایی جوامع دقت کمتری دارد. در بیشتر مواردNOCD ساختاری دارای مسائلی مانند بی‌توجهی به محتوا در فرآیند تشخیص جامعه، نرسیدن به پارتیشن‌های بهینه از نظر تناسب ساختار-محتوا، تولید تنها یک پارتیشن از شبکه (به عنوان خروجی پارتیشن بهینه از دیدگاه ساختاری) است. با این حال، OCD ساختاری اغلب با دو موضوع مواجه است: تشکیل جوامع با محتوای متفاوت و تولید تنها یک پارتیشن شبکه. در نتیجه، روش‌های مبتنی بر ساختار، صرفاً بر روی اتصالات و ساختارهای گراف شبکه‌های پیچیده تمرکز می‌کنند و تعاملات و علایق کاربر و همچنین تأثیر نفوذ آنها به شبکه‌های پیچیده را نادیده می‌گیرند.

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