چكيده
ساختارهاي اجتماعي در شبكه‌اي وجود دارد كه داراي پيچيدگي‌هاي زيستي، اجتماعی، تکنولوژیکی و حاوی اطلاعات مهم باشد. ساختارهای شبکه و جامعه در سیستم‌های کامپیوتری به ترتیب توسط نمودارها و زیرگراف‌ها نمایش داده می‌شود. مسئله تشخیص ساختار جامعه یک مسئله‌‌ی NP سخت است، به ویژه نتایج نهایی بهترین ساختارهای اجتماعی برای شبکههای بزرگ پیچیده ناشناخته هستند. در این مقاله، برای حل مسئله تشخیص ساختار جامعه یک الگوریتم مبتنی بر الگوریتم ژنتیک، AGA-net که یکی از تکنیک‌های تکاملی است پیشنهاد شده است. این الگوریتم دارای ویژگی همگرایی سریعی به مقدار بهینه بدون اینکه در بهینه محلی به دام بیافتد است بنابراین توسط پارامترهای جدید پشتیبانی شده است. شبکه دنیای واقعی که اغلب در کارهای گذشته استفاده می‌شود به‌عنوان داده‌های آزمایشی مورد استفاده قرار گرفته و نتایج به دست آمده با10 الگوریتم متفاوت مقایسه شده است. پس از تجزیه‌وتحلیل نتایج آزمون مشاهده شده است که الگوریتم پیشنهادی نتایج خوبی در مورد شبکههای پیچیده ارائه می‌دهد.
معرفی
درک شبکه‌ها اطلاعات مهمی درباره استخراج اطلاعات معنی‌دار از سیستم‌های پیچیده ارائه می‌دهد. در بیان معنی‌دار اطلاعات از این شبکه‌ها، اهمیت ساختارهایی که با عنوان ساختارهای اجتماعی نامگذاری شده‌اند، زیاد است. ساختارهای گراف برای ارائه شبکههای جهان واقعی استفاده می‌شوند. ساختارهای اجتماعی یا خوشه‌ها می‌تواند به‌عنوان زیرگراف محسوب شود که در ساختارهای گراف به طور جزئی یا کاملا مستقل از یکدیگر هستند. به‌عنوان مثال، بافت یا اندام‌هایی که در بدن انسان نقش مشابه‌ای دارند به‌عنوان خوشه‌ها در نظر گرفته می‌شوند [1]. تشخیص ساختار جامعه (CSD) برای درک شبکههای زیست‌شناسی، اقتصادی، اجتماعی، فن‌آوری و غیره مهم است. این شبکه‌ها می‌توانند شبکههای مصنوعی یا دنیای واقعی باشند. در دنیای واقعی شبکه‌ها می‌توانند از نمونه‌هایی مانند شبکههای ساختار اقتصادی [2]، شبکههای غذایی [3]، شبکههای تعامل شیمیایی بین پروتئین‌ها و مولکول‌ها در سلولها [4-6] و شبکههای اجتماعی مانند شبکههای تعیین دوستی در گروه‌ها، شبکههای تحلیل رابطه و شبکههای تشخیص حملات تروریستی باشند [7].
اشیاء و اتصالات در شبکه‌ها به ترتیب با گره‌ها و لبه‌ها ارائه می‌شوند. ساختارهای گراف که برای نشان دادن شبکههای داده شده مورد استفاده قرار می‌گیرند به‌عنوان ساده‌ترین شکل از شبکههای نامنظم نامیده می‌شوند [8].
تشخیص ساختار جامعه
هنگامی که شبکه داده شده با ساختار گراف، ساختار جامعه را به دست آورد می‌تواند به عنوان زیرگرافی محسوب شود که دارای کیفیت یا کمیتی مانند حداکثر ویژگی مشترک در خود، تعداد تعاملات، شباهت‌های موقعیتی و غیره است. گره‌هایی که عناصر این ساختارها هستند باید حداکثر تعامل و خواص مشترک را با گره‌های جامعه خود و تعامل کمتر و خواص مشترک را با گره‌های جامعه دیگر داشته باشند. گروهی از مردم که در محیط اجتماعی دارای ارتباطات قوی در شبکههای زیست محیطی هستند با یکدیگر و خوشه‌ای از کامپیوترها حداکثر همکاری و تبادل اطلاعات را دارند.
الگوریتم پیشنهادی
در این مقاله برای حل مشکل CSD، الگوریتم AGA-net پیشنهاد شده است که براساس الگوریتم ژنتیک است. همانطور که هر گره از شبکه در مسئله CSDتعداد محدودی همسایه دارد احتمال اینکه همسایه انتخاب شده دوباره انتخاب شود بسیار بالا است. این وضعیت، جستجو برای بهترین راه‌حل ممکن است و باعث ورود به چرخه حیرت‌انگیز در شبکههای مختلف می‌شود. این مشکل با کمک اپراتورهای ژنتیکی که در بخش 2.4 ارائه شده قابل حل است. بنابراین برای همگرایی سریع به بهترین راه‌حل، راه‌حل‌های بهتر توسط نخبه‌گرایی انتخاب شده و از طریق مکانیزم ترکیب و جهش مهار می‌شوند. الگوریتم پیشنهاد شده دارای ویژگی همگرایی بهترین مدولار Qبدون اینکه در بهینه محلی قرار داشته باشد است. AGA-net دارای پیچیدگی زمانی خطی است. علاوه‌بر پارامترهای اساسی و عملگرهای الگوریتم ژنتیک استاندارد، تغییرات خاصی برای مسائل CSD و پارامترهای جدید انجام گرفته است. الگوریتم پیشنهادی باعنوان الگوریتم ژنتیک سازگار (AGA-net) نامگذاری شده است. اصطلاح تطبیقی که در اینجا استفاده می‌شود نشان می‌دهد که هر مکانیسم الگوریتم را می‌توان به تمام شبکه‌ها منطبق کرد. الگوریتم پیشنهاد شده می‌تواند بر روی تمام شبکه‌ها در CSDبدون وابستگی به هر داده داخلی یا خارجی با پارامترهای خاص جدید اعمال شود. مراحل الگوریتم پیشنهاد شده در زیر بخش‌های جداگانه بیان شده است.
نحوه نمایش ژنتیک
الگوریتم پیشنهادی از ساختار همجواری براساس مکان (LAR) برای نمایش براساس نمودار استفاده می‌کند [30]. هر ژن در کروموزوم دارای دو نوع اطلاعات متفاوت است (communityID و populationID). اطلاعات در مورد آنها در شکل 1 بیان شده است. اولین اطلاعات گره همسایه از گره ith انتخاب شده از بین همسایه‌ها را به‌طور تصادفی ذخیره می‌کند. اطلاعات دوم اطلاعات دانش جامعه (CommunityID) از گره ithبرای جوامع تولید شده توسط اولین اطلاعات است. یک نمونه از شبکه با 8 گره در شکل 1 (الف) داده شده است، شکل 1(ب) یک نمونه از کروموزوم‌های تولید شده براساس شبکه داده شده و شکل1 (ج) ساختارهای اجتماعی تولید شده از اطلاعات کروموزوم داده شده را نشان می‌دهد. ساختارهای جامعه به دست آمده در رنگ‌های مختلف داده شده‌اند.
نتایج تجربی
در این بخش، الگوریتم AGA-net بر روی 5 شبکه واقعی که مربوط به (Z) Zachary’s Karate Club، (D) شبکه اجتماعی دلفینها [33]، (A) کالج فوتبال آمریکایی [13]، (B) کتاب‌هایی درباره سیاست ایالات متحده [14] و (C) تعاملات Cattle Protein (IntAct) [34] است آزمایش شده است. این شبکه‌ها به‌صورت غیرمستقیم و بدون وزن سازماندهی شده‌اند. هر گره در شبکه توسط شناسه مشخص می‌شود. برای مثال گره اول شبکه تعاملات Cattle Protein (IntAct) که AATM_BOVINاست [35] با شناسایی 1 مشخص شده است. شبکه‌ها و خواص مورد استفاده آنها در آزمایشات جدول 1 ارائه شده است. تمام آزمایشات بر روی کامپیوتری انجام شده است که دارای مشخصات زیر است:
سیستم عامل مایکروسافت ویندوز 7 (x64) ، پردازنده اینتل هفت هسته‌ای (TM) i7-3632QM ،2.20 گیگاهرتز و 4 گیگابایت رم.
نتیجه گیری
در این مقاله، مسئله CSD که اغلب در تجزیه‌وتحلیل شبکههای پیچیده مورد استفاده قرار می‌گیرد بحث شده و اطلاعات معنادار از شبکه دنیای واقعی تعیین شده است. برای تست دقت الگوریتم توصیه شده، نتایج به‌دست آمده با روش‌های پیشرفته در کارهای پیشین مقایسه شده است. در آزمایشات، چهار شبکه اجتماعی و یک شبکه بیولوژیکی استفاده شده است. علاوه بر عملگرهای موجود و پارامترهای الگوریتم ژنتیک استاندارد AGA-net توسط عملگرها و پارامترهای الگوریتم ژنتیک پیشنهادی پشتیبانی می‌شود که در بخش 2.4 ارائه شده است. این اپراتورها و پارامترها سرعت همگرایی بالایی در الگوریتم پیشنهادی با بهترین مقادیر Q دارند. هنگام تجزیه‌وتحلیل نتایج تجربی مشاهده شده است که الگوریتم AGA-net بهترین مقادیر Q را کنون برای تمام شبکههای شناخته شده به دست آورده است. این نتایج نشان می‌دهد که الگوریتم‌های MA-Net [8] و MA-COM [39] نتایج مشابه‌ای با الگوریتم پیشنهاد ارائه می‌کنند. درحالی‌که الگوریتم پیشنهادی با الگوریتم GACD [37] در 3 شبکه (Z، D و B) نتایج مشابهی به دست آورده است و درمقایسه با شبکه A نتایج بهتری به‌دست آورده است. به‌همین ترتیب الگوریتم پیشنهادی با الگوریتم DECD [10] در شبکه A نتایج مشابهی کسب کرده است و نسبت به شبکه Z نتیجه بهتری بدست آورده است. همچنین الگوریتم پیشنهادی در مقایسه با الگوریتم MENSGA [38] در شبکه Z نتایج یکسانی بدست آورده است ولی در شبکههای دیگر نتایج بهتری داشته است.
در نتیجه، موفقیت و سازگاری الگوریتم پیشنهاد شده از هر دو جدول مقایسه و جداول استاندارد قابل درک است. علاوه‌براین، AGAnet هیچ دانش قبلی‌ای نیاز ندارد و به‌سرعت کار می‌کند. بنابراین، با استفاده از الگوریتم پیشنهاد شده تقریبا 20 درصد در زمان هر شبکه صرفه‌جوییمی‌شود. این الگوریتم به‌گونه‌ای طراحی شده که اندازه گره‌ها و لبه‌های آن را در نظر نمی‌گیرد بنابراین می‌تواند به تمام شبکههای مجازی و دنیای واقعی اعمال شود. پس از تجزیه‌وتحلیل نتایج آزمون مشاهده شد که الگوریتم پیشنهاد شده نتایج خوبی برای تعیین جوامع معنی‌دار از شبکههای پیچیده ارائه می‌دهد.
این مقاله در سال 2015 در نشریه اسپرینگر و در مجموعه مقالات در سازگاری، یادگیری و بهینه سازی، توسط گروه مهندسی کامپیوتر منتشر شده و در سایت ای ترجمه جهت دانلود ارائه شده است. در صورت نیاز به دانلود رایگان اصل مقاله انگلیسی و ترجمه آن می توانید به پست دانلود ترجمه مقاله الگوریتم ژنتیک تطبیقی جدید برای تشخیص ساختار در سایت ای ترجمه مراجعه نمایید.
