بیشینه سازی نفوذ در شبکه های اجتماعی با محدودسازی میزان کاهش نفوذ
چکیده
بیشینه‌سازی نفوذ یکی از مسائل بنیادی تحقیقاتی در شبکه‌های اجتماعی به شمار می‌آید. در بازاریابی ویروسی که یکی از کاربردهای این مقوله است، دسته کوچکی از کاربران برای قبول یک محصول انتخاب شده و اثر شفاهی متعاقب آن می‌تواند به پذیرش عظیم این محصول در شبکه‌های اجتماعی منتهی گردد. مسئله بیشینه‌سازی نفوذ، انتخاب مجموعه‌ای متشکل از K گره از یک شبکه اجتماعی به گونه‌ای است که میزان گسترش نفوذ آن در شبکه را به حداکثر مقدار خود برساند. در پژوهش قبلی انجام شده در خصوص استخراج K گره بالای بانفوذ، فرض شده است که تمامی K گره انتخاب شده می‌توانند نفوذ خود را مطابق انتظار گسترش دهند. با این وجود برخی از گره‌های انتخابی در عمل چندان به خوبی عمل نمی‌نمایند که همین مسئله به اتلاف یا کاهش K گره بالای بانفوذ منتهی می‌گردد. در این مقاله، مسئله بیشینه‌سازی نفوذ دیگری را مورد بررسی قرار خواهیم داد که به طور طبیعی محدودیت اطمینان‌پذیری گره‌ها در شبکه‌های اجتماعی، آن را برمی‌انگیزند. هدف ما یافتن K گره بالای بانفوذ می‌باشد که آستانه کاهش نفوذ ناشی از شکست مجموعه‌ای از R (<K) گره را به ما می‌دهد. برای حل گونه جدیدی از مسئله بیشینه‌سازی نفوذ، روشی مبتنی بر انسجام‌بخشی محدود شبیه‌سازی شده را ارائه و عملکرد آن را از طریق برآورد کاهش نفوذ، بیشتر بهبود خواهیم بخشید. برای پشتیبانی بیشتر از این موضوع، نتایج تجربی مربوط به چندین شبکه اجتماعی دنیای واقعی را ارائه می‌نماییم. همچنین این تحقیق از کاربردهای عملی شبکه‌های اجتماعی در حوزه‌های مختلف به ویژه در جاهایی که اطمینان‌پذیری، یکی از دغدغه‌های اصلی در توسعه یک سیستم است، نیز پشتیبانی خواهد نمود.
1. مقدمه
شبکه‌های اجتماعی، نمایشی بصری در خصوص ارتباطات فردی ارائه نموده و الگوهای رفتاری جالب توجه در جمعیت‌های مختلف کاربران را نمایش می‌دهد (واسرمن و فاوست، 1994). تحلیل شبکه اجتماعی توجه بیشتر حوزه‌های مختلف را به خود معطوف داشته و به ابزاری مهم برای توسعه سیستم‌های هوشمند در توصیه، خدمات انبوه‌سپاری و غیره مبدل شده است (دومینگوز و ریچاردسون (2001)، زعفرانی، عباسی و لیو (2014)، سان، لین و خو (2015)، زنگ و همکاران (2015)).
6. نتیجه‌گیری
مسئله IMIL تحت تاثیر تفکرات عملی در خصوص بازاریابی ویروسی گسترش یافته است. در این مقاله درصدد یافتن K گره بالای بانفوذ هستیم که قید کاهش نفوذ در شبکه‌های اجتماعی را ارائه می‌نمایند. ثابت شده است که این مسئله NP دشوار بوده و روش‌های کنونی در ارائه جواب‌های منطقی خوب با شکست مواجه شده‌اند. برای حل این مسئله، چارچوب مبتنی بر CSA را ارائه نموده‌ایم که در عین اعمال فشار برای ارضای قید کاهش نفوذ، K جواب بالا را بهینه‌سازی می‌کند. توسعه الگوریتم‌های CSA در متن مسئله جدید چندان بدیهی نیست چون لازم است براساس یک تابع جریمه‌ای مبتنی بر حوزه خاص و جایگذاری پارامترهای عملی، همگرایی الگوریتمی را مورد بررسی قرار دهیم. همچنین نسخه بهبود یافته‌ای از الگوریتم CSA را ارائه نموده‌ایم که از تابع جریمه‌ای جدیدی استفاده کرده و بهبود بازدهی الگوریتمی قابل ملاحظه آن را نشان داده‌ایم.
Abstract
Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, aims to select a small set of users to adopt a product, so that the word-of-mouth effect can subsequently trigger a large cascade of further adoption in social networks. The problem of influence maximization is to select a set of K nodes from a social network so that the spread of influence is maximized over the network. Previous research on mining top-K influential nodes assumes that all of the selected K nodes can propagate the influence as expected. However, some of the selected nodes may not function well in practice, which leads to influence loss of top-K nodes. In this paper, we study an alternative influence maximization problem which is naturally motivated by the reliability constraint of nodes in social networks. We aim to find top-K influential nodes given a threshold of influence loss due to the failure of a subset of R(<K) nodes. To solve the new type of influence maximization problem, we propose an approach based on constrained simulated annealing and further improve its performance through efficiently estimating the influence loss. We provide experimental results over multiple real-world social networks in support. This research will further support practical applications of social networks in various domains particularly where reliability would be a main concern in a system deployment.
1. Introduction
Social networks provide an intuitive representation about individual connections and display interesting behavioral patterns across various populations of users (Wasserman & Faust, 1994). Social network analysis is attracting more and more attention from different research areas and becomes an important tool for developing intelligent systems in recommendation, crowdsourcing service and so on Domingos and Richardson (2001), Zafarani, Abbasi, and Liu (2014), Sun, Lin, and Xu (2015), Zeng et al. (2015).
6. Conclusions
The IMIL problem is motivated by practical thoughts on viral marketing. We aim to find top-K influential nodes given influence loss constraint in social networks. This problem is proved to be NP-hardness and existing methods fail to provide reasonably good solutions. To solve the problem, we developed a CSA based framework that optimizes top-K solutions while enforcing satisfaction of influence loss constraint. The development of CSA algorithms is not trivial in the new problem context as we need to investigate algorithmic convergence according to a particular domain based penalty function and practical parameter settings. We further proposed an enhanced version of the CSA algorithm that employs a new penalty function, and showed its significant improvement on the algorithmic efficiency.
(جهت بزرگ نمایی روی عکس کلیک نمایید)
چکیده
1. مقدمه
2. پژوهش‌های مرتبط انجام شده در این زمینه
2. 1. مسئله بیشینه‌سازی نفوذ
2. 2. روش‌های مسیر گستره نفوذ
3. فرمول‌بندی مسئله
4. روش‌های مورد استفاده
4. 1. غیرعملی بودن الگوریتم‌های حریصانه تخت
4. 2. روش‌های مبتنی بر CSA
4. 3. CSA بهبود یافته: CSA-Q
4. 4. پیچیدگی‌های زمانی و مکانی
5. آزمایش‌ها
5. 1. جایگذاری پارامترها
5. 2. نتایج تجربی
6. نتیجه‌گیری
Abstract
1. Introduction
2. Related work
2.1. Influence maximization problem
2.2. Influence spread path methods
3. Problem formulation
4. Our methods
4.1. Infeasibility of plain greedy algorithms
4.2. CSA based approaches
4.3. Improved CSA: CSA-Q
5. Experiments
4.4. Time and space complexities
5. Experiments
5.1. Parameter settings
5.2. Experimental results
6. Conclusions
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه