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

تراکم قسمت‌بندی اجتماع لینک: اگر یک شبکه با M لینک و N گره داشته باشیم P={P₁, … , P_C}، قسمتی از لینک‌های درون زیرمجموعه است. تعداد لینک‌ها در اجتماع P_s، m_s=|P_s| است. تعداد گره‌های ایجاد شده از اجتماع Ps،  است. تراکم جدید لینک Hs از اجتماع Ps به صورت زیر تعریف می‌شود:

                                                    

                                             

می‌توانیم ببینیم که مقدار ماکسیمم H، 1 و مقدار مینیمم آن 0 است. زمانی که هر اجتماع یک دسته باشد H=1 و زمانی که هر اجتماع یک گراف خالی باشد H=0 است. با داشتن تعداد اجتماعات، می‌توانیم قسمت‌بندی بهینه‌ی اجتماع لینک را با به حداکثر رساندن مقدار H پیدا کنیم. برای شبکه‌ی در شکل 1، بخش O در شکل 1A مقدار حداکثر H را دارد. بنابراین می‌توانیم به آسانی قسمت‌بندی بهینه را با به حداکثر رساندن H بیابیم.

مدل برنامه‌نویسی عدد صحیح برای قسمت‌بندی اجتماع لینک، اگر یک شبکه‌ی G=(V,E) با M لینک و N گره داشته باشیم. می‌توانیم فرض کنیم   که تعداد اجتماعات لینک K می‌باشد و قسمت‌بندی اجتماع لینک بهینه را با به حداکثر رساندن تراکم H بیابیم. این مسئله می‌تواند به درون یک مدل برنامه‌نویسی عدد صحیح فرمول‌بندی شود. فرض کنیم که V={V₁, V₂, … , V_N}، مجموعه‌ی گره‌های G باشد و E={e₁ , e₂ , … , e_m} مجموعه‌ی کناره‌ی G باشد. ما R=(rij)_N×M را به گونه‌ای تعریف می‌کنیم که ماتریکس برخورد شبکه‌ی G باشد که در آن r_ij=1 است اگر لینک e_j با گره V_i برخورد کند و در غیر این صورت r_ij=0 است. ما همچنین متغیرهای دو دویی x_js و y_is را برای نشان دادن عضویت لینک e_j و گره V_i در اجتماع لینک Ps تعریف می‌کنیم.

                                                          

                                                                                                                                                

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

                                                                      

تابع عینی (1) برای به حداکثر رساندن تراکم بخش‌بندی لینک جدید H است.

قید (2) به این معناست که هر لینک به یک اجتماع تعلق دارد.

قید (3) بیان می‌کند که اگر یک یا بیشتر لینک در اجتماع Ps وجود داشته باشد که با گره Vi برخورد داشته باشند، بنابراین گره Vi باید به اجتماع Ps تعلق داشته باشد.

قید (4) بیان می‌کند که اگر گره Vi به اجتماع Ps تعلق داشته باشد، بنابراین حداقل یک لینک متلاقی با گره Vi وجود دارد که متعلق به اجتماع φs می‌باشد.

از آنجا که فرمول قیدها ساده است، می‌توانیم مدل برنامه‌نویسی عدد صحیح را با استفاده از نرم‌افزار lingo برای شبکه‌های کوچک باز کنیم تا ببینیم که آیا مدل می‌تواند اجتماعات مشترک را به درستی پیدا کند یا نه. با استفاده از تابع کمیت و مدل برنامه‌نویسی عدد صحیح، ما قادر هستیم که چندین شبکه را به اجتماعات لینک بخش‌بندی کنیم و به نتایج درست دست پیدا کنیم.

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