متدهای به کار گیری الگوریتم ژنتیک در پیشبینی لینک(قسمت سوم)

با استفاده از مدل 2، می‌توانیم شبکه‌ی در شکل 2B را به دو اجتماع بخش‌بندی کنیم و لینک (2، 1) هم متعلق به دو اجتماع است.

                                    

شکل 2: اجتماعات لینک سه شبکه‌ی مجازی: (A) شبکه از 5 اجتماع مشترک تشکیل شده است. گره‌های 1، 7، 12، 16 گره‌های مشترک هستند. (B) شبکه شامل 2 اجتماع مشترک می‌شود، گره‌های 1 و 2 گره‌های مشترک هستند که به دو اجتماع متعلق دارند و لینک (2، 1) نیز متعلق به دو اجتماع است.

(C) شبکه از دو دسته‌ی مشترک تشکیل شده است و ساب‌گراف مشترک یک دسته‌ی 3 تایی است.

هر اجتماع یک دسته است و مقدار بهینه‌ی تابع عینی که مربوط به بخش است 1 می‌باشد. شکل 2C یک شبکه است که شامل دو دسته می‌شود که در یک دسته‌ی 3 تایی مشترک است. شبکه می‌تواند به دو اجتماع بخش‌بندی شود و هر اجتماع یک دسته باشد. دسته‌های مشترک به درستی تشخیص داده می‌شود زیرا هر لینک در بخش مشترک دسته‌ی 3 تایی به دو اجتماع در یک زمان تعلق دارد. مقدار بهینه‌ی تابع عینی بخش لینک 1 است.

                                      

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

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

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

توابع اصلی GA: (الگوریتم ژنتیک) اول از همه، ما باید یک نمایش کروموزومی طراحی کنیم که راه‌حل مسئله‌ی کشف اجتماع را کدگذاری کند. در این اجرا، کروموزوم با استفاده از ماتریکس B=(b_j.c) نشان داده شده است که در آن j=1, 2, … , M و C=1,2,…,k است. هر عامل b_j,c قدرتی است که با آن یک لینک شبکه e_j به اجتماع P_c متصل می‌شود. توجه کنید که b_j,c در محدوده و فاصله‌ی [0، 1، 0، 0] قرار دارد. هر لینک شبکه در معرض محدودیت زیر قرار دارد:

                                                     

معادله‌ی 13 برای هنجارسازی استحکامات عضویت می‌باشد بنابراین مجموع قدرت یک لینک متعلق به تمام اجتماعات مساوی 1 است. برای هر کروموزوم، یک ماتریکس بخش‌بندی D=(d_j,c) را طراحی کرده‌ایم که در آن j=1, 2, …, M و C=1,2,…,k است. هر عامل d_j,c یا 0 یا 1 است.

Discovering Link Communities in Complex Networks by an Integer Programming Model and a Genetic Algorithm

2013

Zhenping LiXiang-Sun ZhangRui-Sheng WangHongwei LiuShihua Zhang

                        http://dx.doi.org/10.1371/journal.pone.0083739