التفاصيل البيبلوغرافية
| العنوان: |
Social Influence Spectrum at Scale: Near-Optimal Solutions for Multiple Budgets at Once. |
| المؤلفون: |
HUNG T. NGUYEN, GHOSH, PREETAM, MAYO, MICHAEL L., THANG N. DINH |
| المصدر: |
ACM Transactions on Information Systems; 2018, Vol. 36 Issue 2, p1-26, 26p |
| مصطلحات موضوعية: |
SOCIAL influence, MARKETING, APPROXIMATION algorithms, SOCIAL psychology, MATHEMATICAL optimization, STATISTICAL decision making |
| مستخلص: |
Given a social network, the Influence Maximization (InfMax) problem seeks a seed set of k people that maximizes the expected influence for a viral marketing campaign. However, a solution for a particular seed size k is often not enough to make an informed choice regarding budget and cost-effectiveness. In this article, we propose the computation of Influence Spectrum (InfSpec), the maximum influence at each possible seed set size k within a given range [klower, kupper], thus providing optimal decision making for any availability of budget or influence requirements. As none of the existing methods for InfMax are efficient enough for the task in large networks, we propose LISA (sub-Linear Influence Spectrum Approximation), an efficient approximation algorithm for InfSpec (and also InfMax) with the best-known worst-case guarantees for billion-scale networks. LISA returns an (1 - 1/e - ϵ )-approximate influence spectrum with high probability (1 - δ ), where ϵ, δ are precision parameters provided by users. Using statistical decision theory, LISA has an asymptotic optimal running time (in addition to optimal approximation guarantee). In practice, LISA surpasses the state-of-the-art InfMax methods, taking less than 15 minutes to process a network of 41.7 million nodes and 1.5 billions edges. [ABSTRACT FROM AUTHOR] |
|
Copyright of ACM Transactions on Information Systems is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
