متدهای به کار گیری الگوریتم ژنتیک در پیشبینی لینک(قسمت دوم)
باتوجه به مثالی که در پست قبل آورده شد،برای شبکه‌ی در شکل 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