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

شبکه‌ی هم‌نشینی لغات:  

شبکه‌ی هم‌نشینی لغات از لیست هنجار انجمن آزاد فلوریدای جنوبی برگرفته شده است. (http://www.usf.edu/IreeAssociation). در لیست هنجار انجمن آزاد فلوراید جنوبی، سنگینی یک لینک هدایت شده از یک کلمه به کلمه دیگر نشان دهنده تعداد دفعات تکراری است که مردم در این تحقیق نقطه‌ی نهایی لینک را با نقطه‌ی آغازین پیوند می‌دهند. شبکه‌ی هم‌نشینی لغات بازی با یک لغت هدایت نشده جابجا شده است و در [36، 34]  آزمایش شده است.

این شبکه 53 گره نشان دهنده‌ی لغات مخلف و 197 کناره‌ی هم‌نشین دارد. با استفاده از الگوریتم ژنتیک با پارامترهای k=3 ، U=40 ، P=0/2 ، θ=0/2 ، α=0/1، β=0/2، T=1000 ما می‌توانیم این شبکه را به سه اجتماع مشترک با ارزش تناسب (تابع عینی) 3396/0 تفکیک کنیم. نتیجه در شکل زیر توصیف شده است. از نتایج تفکیک می‌توانیم ببینیم که لغات با همراهی متداول در اجتماعات یکسان قرار دارند. در این شبکه، لغت بازی به طور قوی به همراه اکثر لغات آمده است. بنابراین یک گره مشترک است. همچنین این نتیجه توسط روش نظری گراف برای تشخیص اجتماع گره به دست آمده است.

                                               

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

استفاده از الگوریتم ژنتیک در شبکه های واقعی 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

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

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

                                          

زمانیکه d_j,c=1 باشد، لینک e_j به اجتماع P_c تخصیص داده می‌شود در غیر این صورت، لینک e_j به اجتماع P_c تخصیص نمی‌یابد. ماتریکس D می‌تواند از ماتریکس B بر طبق معادله‌ی زیر محاسبه شود:

                                                  

شبکه با استفاده از ماتریکس وقوع R، ماتریکس مجاورت لینک A و ماتریکس مجاورت لینک سنگین Q نشان داده می‌شود. ماتریکس مجاورت لینک A می‌تواند توسط معادله‌ی A=R^TR محاسبه شود. در A، عناصر قطری 2 هستند و عناصر غیرقطری مقادیری را در {1، 0} به خود می‌گیرند تا نشان دهند که آیا دو لینک یک گره مشترک دارند یا نه. فرض کنیم که Z یک ماتریکس قطر می‌باشد که عناصر قطری آن معکوس درجه‌های گره هستند یک درجه‌ی گره تعداد لینک‌های متلاقی با آن است به عبارت دیگر:

                                        

ماتریکس مجاورت لینک سنگین به عنوان Q=R^TZR تعریف می‌شود که به معنای احتمال رفتن یک عابر تصادفی از یک لینک به یکی از لینک‌های مجاورش از طریق گره مشترک‌شان می‌باشد. این احتمال می‌تواند به عنوان احتمال تعلق دو لینک مجاور به اجتماع یکسان در نظر گرفته شود.

توابع اصلی GA (الگوریتم ژنتیک)

ورودی: تعداد گره‌های N و تعداد لینک‌های M از شبکه و حداکثر تعداد اجتماعات K را وارد کنید. ماتریکس رویداد R، ماتریکس مجاورت لینک A=R^TR و ماتریکس مجاورت سنگین Q=R^TZR را

محاسبه کنید. تعداد اشخاص U، دوره ماکسیسم T، احتمال تغییر P و پارامترهای SOM (آغاز پیام) یعنی α , β , θ را شرح دهید.

خروجی. ماتریکس بخش‌بندی لینک D* و مقدار تناسب آن H* (یعنی مقدار تراکم بخش‌بندی لینک) و ماتریکس بخش‌بندی گره F را خروجی می‌دهد. بر طبق D* و F شبکه را به اجتماعات بخش‌بندی کنید.

ارزش آغازی: t=0 به طور تصادفی یک جمعیت اولیه B_u(t), …, B₂(t), B₁(t) ایجاد کنید و مقادیر اولیه D* و T* را شرح دهید.

مرحله 1. تناسب جمعیت: برای تمام افراد در جمعیت B_u(t), …, B₂(t), B₁(t) ماتریکس‌های D_u(t), …, D₂(t), D₁(t) و مقادیر متناسب آن‌ها H_u(t), …, H₂(t), H₁(t) را محاسبه کنید.

مرحله 2: دسته‌بندی جمعیت B₁(t) ,B₂(t) , … , B_u(t) را بر طبق مقادیر تناسب‌شان به صورت نزولی دسته‌بندی کنید. فرض کنید که کروموزم‌های دسته‌بندی شده، B₁(t) ,B₂(t) , … , B_u(t) هستند که در آن H₁(t) ≥ H₂(t) ≥ … ≥ H_u(t) می‌باشد.

اگر H₁(t)>H* باشد، D*=D₁(t) و H*=H₁(t) خواهد بود.

اگر t=T باشد، متوقف شوید. D* و H* را خروجی کنید و ماتریکس F متناظر با آن را برای بخش‌بندی گره محاسبه کنید. در غیر این صورت به مرحله 3 بروید.

مرحله‌ی 3. تعویض جمعیت: برای 

فرض کنید که  باشد و برای ایجاد دو شخص موقت (ماتریکس‌های) w_i(t) و  آن‌ها را تعویض کنید. اگر U یک عدد فرد باشد، اینگونه فرض کنید که w_u(t)=B_u(t)

مرحله‌ی 4: تغییر جمعیت: به طور تصادفی اشخاص موقت P^U را انتخاب کنید و عملیات تغییر را بر روی هر شخص موقت انجام دهید.

مرحله 5: SOM (آغاز پیام) جمعیت: برای هر شخص موقت، عملیات آغاز پیام را انجام دهید.

مرحله 6: هنجارسازی جمعیت: هنجارسازی را برای هر شخص موقت انجام دهید. اشخاص هنجارشده را با استفاده از B₁(t+1) ,B₂(t+1) , … , B_u(t+1) مشخص کنید. t=t+1 در نظر بگیرید و به مرحله‌ی 1 بروید.

ماتریکس بخش‌بندی و ارزیابی تناسب برای هر شخص Bi، ماتریکس بخش‌بندی Di را طبق فرمول 14 محاسبه کنید. برای هر اجتماع Ps، 1≤S≤K فرض کنید که Di(:,S)، ستون Sام از ماتریکس Di 

باشد. سپس Ei(s)=R.Di(:,S) یک بردار ستونی است که عوامل آن اعداد صحیح غیرمنفی هستند. یک عامل غیرصفر در Ei(s) نشان می‌دهد که گره متناظر به ei(j,s)≥1 تعلق دارد. Fi(j,s)=1 به این معناست که گره Vj به اجتماع Ps تعلق دارد. تناسب مشخص Bi می‌تواند توسط معادله‌ی زیر محاسبه شود.

                                                                            

از آنجا که اغلب یک مقدار حداکثر در هر ردیف ماتریکس B وجود دارد، ما اغلب با استفاده از فرمول (14)، یک لینک را به یک و فقط یک اجتماع بخش‌بندی کنیم. زمانی که یک لینک، لینک مشترک بین دو اجتماع باشد، نمی‌تواند توسط فرمول 14 به طور مستقیم تشخیص داده شود.

برای تشخیص دو لینک مشترک به طور صحیح، ما می‌توانیم فرمول 14 را با استفاده از فرمول زیر یعنی فرمول 15 جایگزین کنیم.

                                                                            

با استفاده از فرمول 15، یک لینک مشترک می‌تواند به بیش از یک اجتماع بخش‌بندی شود. دسته‌بندی جمعیت B₁(t) ,B₂(t) , … , B_u(t) را طبق مقادیر تناسب‌شان به صورت نزولی دسته‌بندی کنید. فرض کنید که کروموزوم‌های دسته‌بندی شده B₁(t) ,B₂(t) , … , B_u(t) هستند که H₁(t) ≥ H₂(t) ≥ … ≥ H_u(t) است. اگر H₁(t)>H* باشد، D*=D₁(t) و H*=H₁(t) است.

تعویض جمعیت: برای  عملیات تعویض با استفاده از قوانین زیر بر روی s  انجام دهید. به طور تصادفی ستون s را انتخاب کنید ستون sام از   را با استفاده از ستون sام B_i(t) اصلاح کنید و دو فرد موقت w_i(t) و  را به دست آورید. فرض کنید که w_i(t)=

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

با استفاده از مدل 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

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

باتوجه به مثالی که در پست قبل آورده شد،برای شبکه‌ی در شکل 2A می‌توانیم آن را به 5 اجتماع مشترک {5، 4، 3، 2، 1} ، {11، 10، 9، 8، 7}، {15، 14، 13، 12} ، {18، 17، 16} ، {16، 12، 17} بخش‌بندی کنیم. و هر اجتماع یک دسته است. گره‌های 16 ، 12، 7، 1 است. ما می‌توانیم شبکه‌ی در شکل 2B را به دو اجتماع که هر کدام یک دسته هستند بخش‌بندی کنیم. گره 1 و گره 2 به دو اجتماع تعلق دارند و لینک (2، 1) به اجتماع بزرگ‌تر تعلق دارد. مقدار تابع عینی کمتر از 1 می‌باشد زیرا عضویت لینک (2، 1) در اجتماع منحصر به فرد است.

                                        

شکل 1. سه نتیجه‌ی بخش‌بندی مختلف یک شبکه‌ی درختی. (A) بخش‌بندی درست، (B,C) دو بخش‌بندی غیرشهودی. لینک‌های

قرمز و گره‌های مجاور، یک اجتماع را تشکیل می‌دهند، لینک‌های آبی و گره‌های مجاورشان، اجتماع دیگری را به وجود می‌آورند. گره

مشکی مشترک است. در مدل 1، از آنجا که هر لینک می‌تواند به فقط و فقط یک اجتماع تعلق داشته باشد، ممکن است به این نتیجه

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

                                 

در مدل 2، قید 8 به این معناست که هر لینک باید به حداقل یک اجتماع تعلق داشته باشد. لینک متعلق به بیش از یک اجتماع به عنوان چندین لینک در تابع عینی (7) در نظر گرفته می‌شود.

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