مقاله پردازش موازی و مقیاس پذیر بیشینه سازی نفوذ (تاثیر) برای شبکه های اجتماعی با مقیاس بزرگ
چکیده
بیشینه سازی نفوذ مساله کشف زیرمجموعه ای کوچک از گره ها در شبکه های اجتماعی است که نفوذ (تاثیر) کلی این زیرمجموعه ها برای انتشار یک پیام در شبکه های اجتماعی میتواند بیشینه شود. این مساله در سالهای اخیر بطور گسترده بررسی شده است و بسیاری الگوریتم های بیشینه سازی نفوذ (تاثیر) مطرح شده است. با این حال همه الگوریتمهای موجود بطور پیوسته اجرا میشوند. اگر آنها در شبکه های اجتماعی با مقیاس بزرگ اجرا شوند زمان بسیار زیادی به طول میانجامد. در این مقاله، الگوریتم های موازی برای دو مساله بیشینه سازی نفوذ (تاثیر) در شبکههای اجتماعی با مقیاس بزرگ مطالعه میشوند: بیشینه سازی نفوذ با محدودیت بودجه و بیشینه سازی نفوذ بدون محدودیت بودجه. در این مقاله دو الگوریتم موازی برای دو مساله مطرح میشوند، الگوریتم حداکثر درجه مبتنی بر جامعه (Community-based Max Degree) و الگوریتم نسبت هزینه حداکثر درجه (Max Degree Cost Ratio). هر دو الگوریتم بصورت موازی در پلتفرم هادوپ اجرا میشوند. آزمایشات بر مبنای چندین اندازه مختلف شبکههای اجتماعی انجام میشوند. نتایج به وضوح نشان میدهند که الگوریتمهای مطرح شده در این مقاله مقیاس پذیر هستند و بهتر از الگوریتمهای رایج کشف شده عمل میکنند.
کلید واژگان: بهینه سازی نفوذ، شبکه اجتماعی، پلت فرم هادوپ، الگوریتم موازی
- مقدمه
با پیشرفت صفحات وب و تکنولوژی اینترنت همراه، بسیاری از شبکههای اجتماعی مانند فیسبوک و توئیتر پدید آمدهاند. این نرم افزارها پل ارتباطی برای اشخاص در سرتاسر جهان میباشد و به آنها اجازه میدهند که باهم در تعامل باشند. همانطور که مردم بیشتری به شبکههای اجتماعی متصل میشوند، این شبکهها به رسانههای بازاریابی ارزشمندی برای رقابتهای بازاریابی مدرن تبدیل میشوند. بدلیل اینکه نفوذ (تاثیر) میتواند در شبکههای اجتماعی به سرعت انتشار یابد، یک مساله مهم برای کشف گرههای موثر شده است که این موضوع موجب انتشار میزان زیادی از اطلاعات میشود. هدف مساله بیشینه سازی نفوذ، کشف k گره است که گسترش نفوذ (تاثیر) از طریق این گرههای k در سرتاسر شبکههای اجتماعی افزایش مییابند.
بررسی و مطالعه مساله بشینهسازی نفوذ مورد توجه بسیاری از محققان قرار گرفته است، (مراجع ۱ و ۷ و ۱۲ و ۱۳). ریچاردسون و دامینگوس (مراجع ۱ و ۲) اولین کسانی بودند که مساله بیشینه سازی نفوذ را بصورت یک الگوریتم مطالعه کردند. آنها این مساله را به روش احتمال بررسی کردند و یک الگوریتم ابتکاری برای کشف مجموعههای بیشینه سازی مطرح کردند. کمپ و همکارانش مساله کشف تعدادی از گرههای موثر بصورت یک مساله بهینه سازی را بررسی کردند، (مرجع ۳). آنها اثبات کردند که مساله بیشینه سازی نفوذ یک NP-hard است و یک الگوریتم حریصانه (الگوریتمی است که بصورت ابتکاری و تصادفی مقدار بهینه در هر مرحله را انتخاب میکند، به امید اینکه مقدار بهینه را کشف کند) را برای حل آن ارائه دادند. بر اساس ویژگیهای پیمانهای (مطابق اندازه یا مقیاس)، لسکویچ و همکارانش یک الگوریتم بهینه حریصانه با عنوان ” Cost-Effective Lazy forward ” را مطرح کردند، (مرجع ۴). اگرچه این الگوریتم ۷۰۰ برابر سریعتر از الگوریتمهای حریصانه ساده پیشین بود اما فاقد مقیاس پذیری و اندازه بود. چن و همکارانش (مرجع ۵) یک الگوریتم حریصانه با عنوان “NewGreedy” را مطرح کردند و بر اساس این الگوریتم و الگوریتم ” Cost-Effective Lazy forward ” یک الگوریتم ترکیبی با عنوان MixedGreedy را ارائه دادند که نتایج بهتری در مقایسه با الگوریتم “NewGreedy” حاصل میکرد. همچنین آنها یک الگوریتم ابتکاری با عنوان “DegreeDiscount ” پیشنهاد دادند که سریعتر از الگوریتم حریصانه بود اما تضمینی بر صحت عملکرد این الگوریتم وجود نداشت، (مرجع ۵).
در این مطالعه، مساله بیشینه سازی نفوذ مبتنی بر جامعه و بیشینه سازی نفوذ بودجه مطالعه میشود. برای بسیاری از شبکههای اجتماعی حقیقی، ساختارهای اجتماعی طبیعی در آنها وجود دارد. ساختارهای اجتماعی برای شبکههای اجتماعی بسیار مهم هستند اما مطالعات کمی بر مساله بیشینه سازی نفوذ با توجه با ساختارهای اجتماعی صورت گرفته است. بر اساس ساختارهای اجتماعی طبیعی، این مقاله یک الگوریتم مبتنی بر اجتماع (جامعه) با عنوان حداکثر درجه مبتنی بر جامعه (Community-based Max Degree) را به منظور بررسی مساله بیشینه سازی نفوذ را پیشنهاد میدهد. این الگوریتم سه فاز دارد: تشخیص جامعه (Community
Detection)، انتخاب کاندید (Candidate Selection)، انتخاب دانه (Seed Selection). برای رقابتهای بازاریابی یک محصول، یک شرکت معمولا بودجه محدودی دارد. اینکه چگونه با این بودجه محدود مردم بیشتری این محصول را خریداری نمایند و یا با آن آشنایی پیدا کنند، یک موضوع مهم برای شرکتهاست. با توجه به این موضوع، در این مقاله یک الگوریتم مبتنی بر بودجه با عنوان نسبت هزینه حداکثر درجه (Max Degree Cost Ratio) برای حل مساله بیشینه سازی نفوذ بودجه پیشنهاد میشود. این دو الگوریتم ارائه شده (CMD and MDCR) بصورت موازی در پلتفرم هادوپ اجرا میشوند و برای شبکههای اجتماعی حقیقی با مقیاس بزرگ بصورت خودکار مقیاس پذیر هستند. بطور خلاصه اهداف اصلی این مطالعه عبارتند از:
- ارائه یک الگوریتم مبتنی بر جامعه با عنوان حداکثر درجه مبتنی بر جامعه (Community-based Max Degree) به منظور بیشینه سازی مساله نفوذ (تاثیر)
- ارائه یک الگوریتم ابتکاری با عنوان نسبت هزینه حداکثر درجه (Max Degree Cost Ratio) برای حل مساله بیشینه سازی نفوذ بودجه
- اجرای این دو الگوریتم در پلتفرم هادوپ بصورت موازی که موضوع مقیاس پذیری برای شبکههای اجتماعی با مقیاس بزرگ در نظر گرفته میشود.
ادامه این مقاله بدین صورت است: بخش دوم مطالعات مرتبط را ارائه میدهد. بخش سوم مقدمات و مدل سیستم را ارائه میدهد. بخش چهارم و پنجم دو الگوریتم CMD و MDCR را به ترتیب توصیف میکنند. بخش ششم آزمایشات در چند شبکه اجتماعی را با جزییات کامل ارائه میدهد و در پایان بخش هفتم نتیجه را بیان میکند.
هنوز بررسی‌ای ثبت نشده است.