تاثیرگذاری حداکثری در شبکه های اجتماعی بزرگ

یکی از مسایل اساسی در شبکه های اجتماعی یافتن یک زیرمجموعه از گره های با نفوذ می باشد. بهطوری که هدف قرار دادن آنها (به منظور اتخاذ یک محصول جدید) بیشترین گسترش نفوذ را دربرداشته باشد (بیشترین اتخاذ محصول جدید). مشکل پیدا کردن با نفوذترین گره ها یک مساله NP-Hard است. ثابت شده است که الگوریتم حریصانه با تضمین تقریب قابل اثبات میتواند تقریبمناسبی را ارایه کند. با این حال این کار بسیار پر هزینه است، بخصوص جهت اجرا در شبکه هایبزرگ. در این مقاله یه استراتژی یافتن انجمنها به صورت محاسبات موازی انجام شده است. درروش مورد بررسی الگوریتم CGA جهت یافتن گره های تاثیرگذار در دو نوع شبکه استفاده شدهاست. این کار شامل دو مرحله است: 1- تقسیم شبکه اجتماعی با مقیاس بزرگ به چندین انجمن با استفاده از انتشار اطلاعات حساب و 2- انتخاب اجتماع ها و پیدا کردن گره های پرنفوذ از میان آنها با استفاده از برنامه نویسی پویا. سپس، برای بهبود بیشتر عملکرد، انتشار نفوذ را بر پایه انجمن ها با درنظر گرفتن انتشار نفوذ بر انجمن موازی سازی می شود. نتایج شبیه سازی نشان می دهد این الگوریتمدارای کارایی قابل قبولی در یافتن انجمنها، گره های تاثیرگذار با زمان اجرای قابل قبول می باشد.

کلیدواژه ها:

شبکه اجتماعی ، تاثیرگذاری حداکثری ، الگوریتم حریصانه