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

Abstract

با توســعة شبکه های اجتماعی، چالشهای بیشتری در تحلیل آنها ایجاد شده است که نیازمند روشهای دقیق تر و سریعتر هستند. یکی از آن چالشها، یافتن افراد تأثیرگذار در شبکه های اجتماعی است که کاربردهای متنوعی مانند بازاریابی، انتشار اطلاعات و پیشگیری از بیماری ها دارد. بیشتر روشهای پیشین این چالش را به عنوان یک مسئله تک هدفه دنبال می کردند؛ به حداکثر رساندن میزان انتشار در شبکه. در این راستا، تعداد مشخصی از افراد به عنوان افراد تاثیرگذار (یا اعضای بذر) انتخاب می شــوند و میزان انتشــار منجر از انتخاب آنها در شــبکه ارزیابی می شود. در حالــی که اهــداف دیگری مانند هزینــه انتخاب هر بذر نیز اهمیت ویــژه ای دارد؛ به خصوص در امور تبلیغاتی و راهبردهای مدیریتی. در این مقاله حداکثر رساندن انتشار به عنوان یک مسئلة تک هدفه و همچنین کمینه کردن هزینه انتخاب بذرها با توجه به حداکثر رساندن انتشار به عنوان یک مســئلة دو هدفه در نظر گرفته شــده اســت. نوآوری مقاله، استفاده از توابع درهم ساز در جهت افزایش سرعت اجرای چالــش یافتن اعضای بذر اســت. در این راســتا، الگورتیم GA-H (ترکیب الگوریتم ژنتیک و تابع درهم ساز) برای حل مســئلة تک هدفه و الگوریتم II-NSGA-H (ترکیب روش II-NSGA و تابع درهمساز) برای حل مسئلة دو هدفه پیشنهاد می شــود. در الگوریتم های پیشــنهادی، استفاده از توابع درهم ســاز باعث می شــود تا از تکرار محاسبات ارزیابی جلوگیری شود. بدین ترتیب، ضمن حفظ دقت حل مساله یافتن اعضای بذر، بهبود قابل توجهی در زمان اجرا ایجاد می شود؛ بهبود زمان اجرا به طور متوسط %8/21 در تمامی آزمایش ها.