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

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

Keywords:

شبکه های اجتماعی , گسترش تاثیر , بیشینه سازی تاثیر , مدل آستانه خطی , الگوریتم ازدحام قطعی