استفاده از الگوریتم ژنتیک در شبکه های واقعی The karate club network

شبکه‌ی باشگاه کاراته:

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

اولین مثالی که در نظر می‌گیریم یک شبکه‌ی باشگاه معروف کاراته است که توسط Zachary تجزیه و تحلیل شده است. همچنین توسط بسیاری از مطالعات تشخیص اجتماع مورد تحلیل قرار گرفته است. این شبکه از 34 عضو باشگاه کاراته به عنوان گره‌ها و 78 کناره بیان کننده‌ی دوستی بین اعضای باشگاه که در طی دو سال مشاهده شد، تشکیل شده است.

ما روش‌مان را برای شبکه‌ی باشگاه کاراته با استفاده از پارامترهای k=3، N=600 ، P=0/2، θ=0/2 ، α=0/6، β=0/2، T=1000 به کار می‌بریم.

نتیجه در شکل زیر به تصویر کشیده شده است. چگالی متوسط لینک 3349/0 است. رنگ لینک‌ها نشان می‌دهد که اجتماعات لینک با استفاده از الگوریتم ژنتیک ما کشف می‌شوند و رنگ گره‌ها نشان‌دهنده‌ی اجتماعات گره است که از اجتماعات لینک استنباط شده‌اند. در این شبکه‌ی باشگاه کاراته، اجتماعات لینک‌ها نشان می‌دهند که گره 1 متعلق به سه اجتماع است و گره‌های 2 و 3 به دو اجتماع تعلق دارند. بخش مشترک یک دسته‌ی 3 تایی است که توسط روش‌های قبلی تشخیص داده نشده بود.

                                                     

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