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

در بسیاری کاربردهای گراف همچون بازاریابی ویروسی در شبکه های اجتماعی، یافتن مجموعه ای از نودها با هدف پیگیری میزان انتشار اطلاعات مدنظر است. این مسئله با عنوان بیشینه سازی نفوذ در شبکه های اجتماعی مطرح می شود که هدف آن یافتن مجموعه ای از افراد اولیه به نحوی است که بیشترین میزان انتشار نفوذ را در شبکه ایجاد کنند. تاکنون الگوریتم های بسیاری برای حل این مسئله ارائه شده است اما به دلیل رشد روزافزون شبکه های اجتماعی و نیاز به سرعت بالا همراه با افزایش نفوذ نهایی، این مسئله همچنان موضوعی چالشی است که مورد توجه پژوهشگران است. در این راستا، در این مقاله الگوریتم تکاملی ترکیبی GABC ارائه شده است. درروش فرا اکتشافی پیشنهادی، الگوریتم ABC با بهره گیری از روش انتخاب همسایه ی الگوریتم SA به منظور تولید جواب های متنوع تر ارائه شده است. همچنین از عملگرهای ترکیب و جهش الگوریتم GA در مراحل جستجوی محلی و جستجوی سراسری الگوریتم ABC به منظور فرار از بهینه ی محلی استفاده شده است. نتایج تجربی الگوریتم GABC روی دو مجموعه داده ی NetHEPT و NetGR-QC در مقایسه با الگوریتم های مورد ارزیابی نشان می دهد که الگوریتم پیشنهادی، میزان انتشار نفوذ بالا به همراه زمان اجرای پایین، ارائه می دهد.

Keywords:

شبکه های اجتماعی , تجزیه و تحلیل شبکه های اجتماعی , بیشینه سازی نفوذ , بازاریابی ویروسی , الگوریتم های فرا اکتشافی.