LP: Link Prediction

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

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

با استفاده از مدل 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=(bj.c) نشان داده شده است که در آن j=1, 2, … , M و C=1,2,…,k است. هر عامل bj,c قدرتی است که با آن یک لینک شبکه ej به اجتماع Pc متصل می‌شود. توجه کنید که bj,c در محدوده و فاصله‌ی [0، 1، 0، 0] قرار دارد. هر لینک شبکه در معرض محدودیت زیر قرار دارد:


                

                                                     


معادله‌ی 13 برای هنجارسازی استحکامات عضویت می‌باشد بنابراین مجموع قدرت یک لینک متعلق به تمام اجتماعات مساوی 1 است. برای هر کروموزوم، یک ماتریکس بخش‌بندی D=(dj,c) را طراحی کرده‌ایم که در آن j=1, 2, …, M و C=1,2,…,k است. هر عامل dj,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

 

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

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

                                

                                                    

                   

                                             


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

مدل برنامه‌نویسی عدد صحیح برای قسمت‌بندی اجتماع لینک، اگر یک شبکه‌ی G=(V,E) با M لینک و N گره داشته باشیم. می‌توانیم فرض کنیم   که تعداد اجتماعات لینک K می‌باشد و قسمت‌بندی اجتماع لینک بهینه را با به حداکثر رساندن تراکم H بیابیم. این مسئله می‌تواند به درون یک مدل برنامه‌نویسی عدد صحیح فرمول‌بندی شود. فرض کنیم که V={V1, V2, … , VN}، مجموعه‌ی گره‌های G باشد و E={e1 , e2 , … , em} مجموعه‌ی کناره‌ی G باشد. ما R=(rij)N×M را به گونه‌ای تعریف می‌کنیم که ماتریکس برخورد شبکه‌ی G باشد که در آن rij=1 است اگر لینک ej با گره Vi برخورد کند و در غیر این صورت rij=0 است. ما همچنین متغیرهای دو دویی xjs و yis را برای نشان دادن عضویت لینک ej و گره Vi در اجتماع لینک 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

                                                       


1 2 3 >>