حداکثرسازی نفوذ (influence maximization)

یک شبکه اجتماعی را گرافی فرض می‌شود که گره‌های آن کاربران و یال‌های آن پیوندهای اجتماعی بین کاربران است. حداکثرسازی نفوذ به دنبال مجموعه‌ای از کاربران با حداکثر تاثیر در گراف می‌باشد. تأثیر هر مجموعه دانه[1]بر اساس فرآیند انتشار اطلاعات در بین کاربران تعریف می شود. به عنوان مثال در بازاریابی ویروسی انتشار اطلاعات که در آن یک شرکت ممکن است بخواهد پذیرش یک محصول جدید را از طریق پیوندهای اجتماعی بین کاربران گسترش دهد. برای تعیین کمیت انتشار اطلاعات، مدل انتشار و نفوذ مورد استفاده قرار می‌گیرد.

مدل انتشار

یک مدل انتشار M فرآیند تصادفی را برای مجموعه‌ای از کاربران مدل می‌کند که اطلاعات را در گراف شبکه اجتماعی منتشر می‌کند. الگوریتم‌های استفاده شده در مدل انتشار عبارتند از:

الف) مدل آبشار مستقل[2]

ب) مدل آستانه خطی[3]

ج) مدل تحریک[4]

د) مدل انتشار آگاه از زمان[5]

ه) مدل انتشار غیرپیشرونده[6]

الگوریتم‌های حداکثرسازی نفوذ

1- رویکرد مبتنی بر شبیه سازی

رویکرد مبتنی بر شبیه‌سازی، شبیه‌سازی مونته کارلو[7] را به‌عنوان یک جعبه سیاه، که یک شمشیر دولبه است، در نظر می‌گیرد: کلیت مدل را حفظ می‌کند اما از طریق تحلیل و بهینه‌سازی فرآیند ارزیابی تأثیر با استفاده از ویژگی‌های مدل‌های انتشار، از بهبود عملکرد بیشتر جلوگیری می‌کند.

2- رویکرد مبتنی بر پروکسی

پروکسی‌های کاهش مدل انتشار مستقیماً از مدل‌های انتشار یعنی مدل IC یا LT برگرفته شده‌اند و به طور کامل از خواص این مدل‌ها برای تخمین تأثیر استفاده می‌کنند. در بیشتر موارد، آن‌ها می‌توانند با رویکردهای مبتنی بر شبیه‌سازی به کیفیت رقابتی دست یابند. با این حال، زمانی که تعداد مسیرهای نفوذ و محدوده تأثیر گره ها و مجموعه‌ها زیاد است، نمی‌توانند به تعادلی بین دقت و کارایی دست یابند. علاوه بر این، پراکسی‌های کاهش مدل انتشار اغلب فقط برای یک مدل خاص هستند و نمی توان آن‌ها را به مدل‌های دیگر تعمیم داد. براساس ویژگی‌های مدل‌های پراکسی، الگوریتم‌های مبتنی بر پروکسی را در دو شاخه بررسی می‌شود:

(1) پراکسی رتبه‌بندی تأثیر[8]

(2) پروکسی کاهش مدل انتشار[9]

3- رویکرد مبتنی بر طرح

تمرکز اصلی این رویکرد بهبود کارایی نظری روش‌های مبتنی بر شبیه‌سازی است گلوگاه رویکرد مبتنی بر شبیه‌سازی، اجرای مجدد تعداد زیادی شبیه‌سازی پرهزینه MC ، برای ارزیابی گسترش نفوذ هر مجموعه بذر مورد نظر است. برای جلوگیری از اجرای مجدد شبیه‌سازی‌های MC، رویکرد مبتنی بر طرح تعدادی از طرح‌ها را بر اساس مدل انتشار خاص از قبل محاسبه می‌کند و سپس از طرح‌ها برای ارزیابی گسترش نفوذ بهره‌برداری می‌کند. الگوریتم‌های این رویکرد را به دو شاخه طبقه‌بندی می‌شوند:

(1) یعنی طرح تأثیر رو به جلو[10]

(2) طرح قابل دسترسی معکوس[11]

-------------------------------------------------------------------------------------------------------------------------------------------------------

[1] Seed

[2] The Independent Cascade (IC) Model

[3] The Linear Threshold (LT) Model

[4] The Triggering (TR) Model

[5] Time-aware Diffusion Models

[6] Non-Progressive Diffusion Models

[7] Monte Carlo

[8] Influence Ranking Proxy

[9] Diffusion Model Reduction Proxy

[10] Forward Influence Sketch

[11] Reverse Reachable Sketch