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

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

Keywords:

پیشینه سازی نفوذ , شبکه اجتماعی علامت دار , PageRank