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

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

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

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

کشف اجتماع در رشته‌های مختلف کاربردهای فراوان و مهمی دارد. برای مثال در زیست‌شناسی، کشف اجتماع برای یافتن ماجول‌های تابعی پروتئین و پیش‌بینی توابع پروتئینی به کار برده شده است. در جامعه شناسی، ساختار اجتماع، یک ویژگی جغرافیایی مهم در ملاحظه‌ی مداخلات واکسیناسیون بیماری‌های عفونی در شبکه‌های تماس و فهم انتشار ویروس در شبکه‌های اجتماعی است.

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

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

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

در یک مطالعه‌ی اخیر، نویسندگان، دانسیته (تراکم) لینک در یک اجتماع لینک و تراکم بخش را تعریف کردند، تا کیفیت یک بخش از اجتماع لینک را ارزیابی کنند. اگر یک شبکه با m لینک و n گره داشته باشیم، P= {P₁, … , P_C} قسمتی از لینک‌های در زیر مجموعه‌های C است. تعداد لینک‌ها در زیرمجموعه‌ی m_s=|P_s| , P_s است. تعداد گره‌های ایجاد شده  است. تراکم لینک Ds در اجتماع Ps به این صورت تعریف می‌شود:

                                                           

تراکم قسمت D به عنوان میانگین Ds تعریف می‌شود. یعنی:

                                                         

می‌توانیم ببینیم که مقدار ماکسیمم D، عدد 1 است. اما می‌تواند مقادیر کمتر از 0 را داشته باشد. هنگامی که هر اجتماع یک دسته باشد. D=1 و زمانیکه هر اجتماع یک درخت باشد D=0 است. زمانیکه یک شبکه به صورت درختی است نمی‌توان با به حداکثر رساندن D آن را به اجتماعات مناسب تقسیم‌بندی کرد. زیرا تعداد زیادی بخش بهینه‌ی مختلف وجود دارند و هر قسمت تراکم بخش یکسان و D=0 را دارد. برای مثال، شبکه‌ی در شکل 1 از دو اجتماع با یک گره مشترک تشکیل شده است و هر اجتماع یک نمودار ستاره‌ای است. اگر بخواهیم شبکه را با به حداکثر رساندن D به دو اجتماع تقسیم کنیم. یافتن نتیجه‌ی درست نشان داده شده در شکل (A) سخت خواهد بود زیرا بخش‌های در شکل 1B و شکل 1C نیز D=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://journals.plos.org/plosone/article?id=10.1371/journal.pone.0083739