دانلود رایگان ترجمه مقاله تشخیص ساختار جامعه (اسپرینگر 2015)

مبتدی (مناسب برای درک مفهوم کلی مطلب) 

1 تشخیص ساختار جامعه
هنگامی که شبکه داده شده با ساختار گراف، ساختار جامعه را به دست آورد می‌تواند به عنوان زیرگرافی محسوب شود که دارای کیفیت یا کمیتی مانند حداکثر ویژگی مشترک در خود، تعداد تعاملات، شباهت‌های موقعیتی و غیره است. گره‌هایی که عناصر این ساختارها هستند باید حداکثر تعامل و خواص مشترک را با گره‌های جامعه خود و تعامل کمتر و خواص مشترک را با گره‌های جامعه دیگر داشته باشند. گروهی از مردم که در محیط اجتماعی دارای ارتباطات قوی در شبکه‌های زیست محیطی هستند با یکدیگر و خوشه‌ای از کامپیوترها حداکثر همکاری و تبادل اطلاعات را دارند.
فرض کنید که ساختار گراف G(V,E) نشان‌دهنده یک شبکه نامنظم و بدون وزن باشد. گراف G دارای V گره (رأس) و مجموعه‌ای از لبه ها (یال‌ها) E است.

تشخیص ساختار جامعه با توجه به مقدار برازش با استفاده از Tasgin و همکارانش در سال 2007 بانام تشخیص جامعه در شبکه‌های مجتمع با استفاده از الگوریتم‌های ژنتیک انجام شده است [26]. در مقاله مشخص شده، الگوریتم پیشنهاد شده بانام GATHB [26، 27] نامگذاری شده است. پس از انتشار این مقاله، الگوریتم‌های تکاملی بسیاری برای مسائل CSD اعمال شد. الگوریتم AGA-net که ما پیشنهاد دادیم از تابع هدف یکسانی مانند الگوریتم GATHB استفاده کرده است که در معادله (2) نشان داده شده است.
1.2 الگوریتم ژنتیک
GA ها برای اولین بار توسط جان هلند در دهه 1960 نوشته شده و سپس توسط هلند و دانش‌جویان و همکارانش در دانشگاه میشیگان در دهه 1960 و 1970 توسعه یافته است. هدف هلند این بود که پدیده “سازگاری” را که در طبیعت اتفاق می‌افتد درک کند و روش‌هایی را که مکانیسم‌های سازگاری طبیعی را توسعه می‌دهند، توسعه دهد. کتاب اقتباس از طبیعت و سیستم‌های مصنوعی (هلند، 1975) GA را به عنوان انتزاعی از تکامل بیولوژیکی و چارچوب نظری برای انطباق تحت GA ارائه داده است [29]. GA یک الگوریتم مبتنی بر جمعیت است و می‌تواند بدون نیاز به هیچ مدلی یا دانش قبلی یا مفروضاتی عمل کند. بنابراین این الگوریتم را می‌توان برای مسائل و ساختار کلی با ویژگی خاص اعمال کرد.

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

2.1 نحوه نمایش ژنتیک
الگوریتم پیشنهادی از ساختار همجواری براساس مکان (LAR) برای نمایش براساس نمودار استفاده می‌کند [30]. هر ژن در کروموزوم دارای دو نوع اطلاعات متفاوت است (communityID و populationID). اطلاعات در مورد آنها در شکل 1 بیان شده است. اولین اطلاعات گره همسایه از گره ith انتخاب شده از بین همسایه‌ها را به‌طور تصادفی ذخیره می‌کند. اطلاعات دوم اطلاعات دانش جامعه (CommunityID) از گره ith برای جوامع تولید شده توسط اولین اطلاعات است. یک نمونه از شبکه با 8 گره در شکل 1 (الف) داده شده است، شکل 1(ب) یک نمونه از کروموزوم‌های تولید شده براساس شبکه داده شده و شکل1 (ج) ساختارهای اجتماعی تولید شده از اطلاعات کروموزوم داده شده را نشان می‌دهد. ساختارهای جامعه به دست آمده در رنگ‌های مختلف داده شده‌اند.

2 جمعیت اولیه
الگوریتم پیشنهاد شده کروموزوم را مانند اندازه جمعیت در ابتدای فرآیند تولید می‌کند. هر ژن در کروموزوم یک گره را نشان می‌دهد. دومین آرایه از آرایه‌های داده شده در شکل1 (ب) گره‌ای متناظر با همسایه را براساس ID آن انتخاب می‌کند. پس از آنکه تمام جمعیت تشکیل شد، آرایه 3 با توجه به آرایه 2 که در شکل داده شده است شکل می‌گیرد. آرایه دوم که در شکل 1 (ب) نشان داده شده است کل جامعه را در طول محاسبات modularity Q فراهم می‌کند.
درحالی‌که به هنگام تعیین CommunityID ژن در داخل کروموزوم باید با ژن موجود همسایه باشد. براساس این اصل، فضای راه‌حل محدود می‌شود و موجب صرفه‌جویی در زمان می‌شود.

2.3 تابع برازندگی
در این مقاله، modularity Q به‌عنوان تابع برازندگی استفاده می‌شود. این معیار ابتدا توسط نیومن و گیروان [15] در سال 2004 استفاده شد. این تابع در معادله 2 داده شده است. مسئله CSD را می‌توان به‌عنوان مسئله بهینه‌سازی ترکیبی با توجه به تابع هدف مشخص شده در نظر گرفت. تابع هدف در بهترین خوشه‌بندی گراف، به حداکثر مقدار Q می‌رسد. مقدار Q در محدوده -1 تا +1 متغیر است.

2.4 عملگرهای ژنتیک
نخبه‌کشی (elitism)، انتخاب، ترکیب (crossover) و جهش (mutation) در الگوریتم پیشنهادی مورد استفاده قرار گرفته است. پارامترهای هر عملگر که در این فرایند مورد استفاده قرار گرفته با مسئله CSD برای رسیدن به مناسب‌ترین راه‌حل سازگار است. برخلاف الگوریتم ژنتیک استاندارد جدید، پارامترها در عملگرهای نخبه‌کشی، ترکیب و جهش گنجانده شده‌اند. عملگرها و پارامترهای پیشنهاد شده توسط الگوریتم AGA-net با جزئیات در زیر ارائه شده است.

نخبه‌کشی (elitism): این عملگر در دو مرحله از الگوریتم استفاده می‌شود. در مرحله اول، برای انتقال کروموزوم با نرخ elitismRate (٪) انتخاب می‌شود که بهترین مقدار Q در جمعیت را به نسل بعدی به همراه دارد. در مرحله دوم، کروموزوم‌های جدید با مقادیر Q بهتر با کروموزوم بد جایگزین می‌شوند. نرخ elitism از حذف بدترین کروموزوم از خوشه را تضمین می‌کند. این پارامتر با نرخ‌های کوچک برای کاهش تنوع انتخاب کروموزوم مناسب نیست.

انتخاب (selection): فرآیند تولید نسل جدید با انتخاب چرخ رولت (RWS) انجام می‌شود [31]. در الگوریتم پیشنهادی، فرآیند انتخاب براساس روش RWS به شرح زیر انجام می‌شود.

ترکیب (crossover): دو پارامتر مختلف مرتبط با این عملگر توسط نام‌های نرخ ترکیب (CR) و انتخاب ترکیب (CC) تعریف شده است. پارامترهای CR موجب ترکیب افراد در جمعیت قرار می‎شوند و تعداد تکرار فر‌آیند مورد بررسی قرار می‌گیرد. سپس پارامتر CC موجب تولید دنباله کنترل تغییر برای جفت کروموزوم‌ها تحت فرآیند ترکیب می‌گردد. به‌طوری‌که مقدار CC اگر کوچکتر از عدد تصادفی تولید شده باشد، 0 می‌گردد و اگر بزرگتر باشد مقدار 1 را می‌گیرد. فرآیند ترکیب رخ داده در شکل 2 نشان داده شده است.
جهش ( Mutation): در الگوریتم پیشنهاد شده، فرآیند جهش در دو مورد انجام می‌شود، یک نقطه‌ای و چند نقطه‌ای. اولی جهش تک‌نقطه‌ای و دومی جهش چندنقطه‌ای است. همچنین دو پارامتر در روند جهش استفاده شده است. اولین پارامتر نرخ جهش (MR) و پارامتر دوم نرخ جهش چندنقطه‌ای (multiP) است. پارامتر MR با نسبت کوچک انتخاب شده است و تعیین خواهد کرد که آیا کروموزوم ورودی جهش می‌یابد یا نه. پارامتر multiP اجازه می‌دهد تا یکی از گزینه‌های جهش تک نقطه‌ای یا چندنقطه‌ای انتخاب شود. اگر مقدار این پارامتر کمتر از مقدار تولید شده به‌طور تصادفی باشد، جهش تک‌نقطه‌ای انتخاب می‌شود، اما اگر برابر یا بزرگتر از مقدار تولید شده به‌طور تصادفی باشد جهش چندنقطه‌ای اعمال می‌شود. نمونه‌های نمایشی نشان‌دهنده این روند در شکل 3 نشان داده شده است. در اینجا، هر ژن انتخاب شده توسط شرایط همسایگی، جهش یافته است (به شکل 1(الف) مراجعه شود).