عنوان ترجمه شده مقاله: یـک روش مستقـل از مــدل برای به حــداکثــر رســاندن نفـوذ اثرگـذار در شبکـه هـای اجتمــاعی

The well-known influence maximization problem (Kempe et al., in proceedings of the 9th SIGKDD international conference on knowledge discovery and data mining (KDD), pp 137–146, 2003) (or viral marketing through social networks) deals with selecting a few influential initial seeds to maximize the awareness of product(s) over the social network. As it is computationally hard (Kempe et al., in proceedings of the 9th SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp 137–146, 2003), a greedy approximation algorithm is designed to address the influence maximization problem. However, the major drawback of this greedy algorithm is that it runs extremely slow even on network datasets consisting of a few thousand nodes and edges (Leskovec et al., in proceedings of the 13th SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp 420–429, 2007; Checn et al., in proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp 937–944, 2009). Several efficient heuristics have been proposed in the literature (Checn et al., in proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp 937–944, 2009) to alleviate this computational difficulty; however, these heuristics are designed for specific influence propagation models such as linear threshold model and independent cascade model. This motivates the strong need to design an approach that not only works with any influence propagation model, but also efficiently solves the influence maximization problem. In this paper, we precisely address this problem by proposing a new framework which fuses both link and interaction data to come up with a backbone for a given social network, which can further be used for efficient influence maximization. We then conduct thorough experimentation with several real-life social network datasets such as DBLP, Epinions, Digg, and Slashdot and show that the proposed approach is efficient as well as scalable

چکیده

مسئله شناخته­ شده به حداکثر رساندن نفوذ اثرگذار (کمپ و همکاران، 2003) (یا بازاریابی ویروسی از طریق شبکه های اجتماعی) با انتخاب چند پیگرد اولیه تأثیرگذار جهت به حداکثر رسانیدن آگاهی از محصول (محصولات) در شبکه های اجتماعی سر و کار دارد. از آنجاکه مسئله به حداکثر رساندن  نفوذ اثرگذار به لحاظ محاسباتی دشوار است (کمپ و همکاران، 2003) یک الگوریتم تقریبی حریصانه به منظور پرداختن به آن طراحی شده است. با اینحال، اشکال اصلی این الگوریتم حریصانه آن است که چنین الگوریتمی حتی در پایگاه داده شبکه های متشکل از چندین هزار گره و لبه نیز به کُندی اجرا می شود (لسکویچ و همکاران، 2007؛ چکن و همکاران، 2009). چندین طرح اکتشافی کارآمد در متون و مقالات (چکن و همکاران، 2009) برای کاهش میزان دشواری محاسباتی پیشنهاد شده است. در هر صورت، این طرح های اکتشافی برای مدل های خاصِ گسترش اثرگذاری همچون مدل خطی آستانه و مدل آبشار مستقل طراحی شده اند. این نیاز شدید به طراحی روشی را تقویت می کند که نه تنها با تمام مدل های گسترش اثرگذاری کار کند، بلکه به شیوه ای مؤثر مسئله به حداکثر رساندن  نفوذ را نیز حل کند. ما در این مقاله با ارائه چارچوبی جدید بطور دقیق به این مسئله پرداختیم. این چارچوب هم داده های پیوند و هم داده های تعاملی را با هم ترکیب می نماید تا ساختار مستحکمی برای یک شبکه اجتماعی ایجاد نموده و بتوان از آن استفاده بیشتری در به حداکثر رساندن نفوذ اثرگذار نمود. سپس از طریق آزمایش مجموعه­ داده های چند شبکه اجتماعی واقعی همانند DBLP، Epinions، Digg، و Slashdot به نتیجه گیری رسیدیم و نشان دادیم که روش پیشنهادی مؤثر و مقیاس پذیر است.  

1-مقـــدمه

بسیاری از رسانه های اجتماعی آنلاین امروزی حجم عظیمی از داده ها را جمع آوری می کنند، این داده ها نه تنها در رابطه با اینکه چه کسی با چه افرادی پیوند خورده است (داده های لینک با نام مستعار) بلکه به اینکه چه کسی با چه افرادی تعامل دارد (داده های تعاملی با نام مستعار) نیز مربوط می شود. هم وجود تنوع و هم حجم در این پایگاه های داده موجب چالش های جدیدی به هنگام انجام تحلیل در شبکه های اجتماعی می شود...