Analyzing competitive influence maximization problems with partial information: An approximation algorithmic framework
Publication in refereed journal


Times Cited
Web of Science12WOS source URL (as at 14/01/2021) Click here for the latest count
Altmetrics Information
.

Other information
AbstractGiven the popularity of the viral marketing campaign in online social networks, finding a computationally efficient method to identify a set of most influential nodes so as to compete well with others is of the utmost importance. In this paper, we propose a general model to describe the influence propagation of multiple competing sources in the same network. We formulate the Competitive Influence Maximization with Partial information (CIMP) problem: given an influence propagation model and the probability of a node being in the competitor's seed set, how to find a set of k seeds so to trigger the largest expected influence cascade under the presence of other competitors? We propose a general algorithmic framework, Two-phase Competitive Influence Maximization (TCIM), to address the CIMP problem. TCIM returns a (1 - 1/e - epsilon)-approximate solution with probability of at least 1 n(-l), where l >= 1/2 is a parameter controlling the trade-off between the success probability and the computational efficiency. TCIM has an efficient expected time complexity of 0 (c(k+l) (m + n) log n/epsilon(2)), where n and m are the number of nodes and edges in the network, and c is a function of the given propagation model (which may depend on k and the underlying network). To the best of our knowledge, this is the first work which provides a general framework for the competitive influence maximization problem where the seeds of the competitor could be given as an explicit set of seed nodes or a probability distribution of seed nodes. Moreover, our algorithmic framework provides both quality guarantee of solution and practical computational efficiency. We conduct extensive experiments on real-world datasets under three specific influence propagation models, and show the efficiency and accuracy of our framework. In particular, for the case where the seed set of the competitor is given explicitly, we achieve up to four orders of magnitude speedup as compared to previous algorithms with the same quality guarantee. When the competitor's seed set is not given explicitly, running TCIM using the probability distribution of the competitor's seeds returns nodes with higher expected influence than those nodes returned by TCIM using an explicit guess of the competitor's seeds. (C) 2015 Elsevier B.V. All rights reserved.
All Author(s) ListLin YS, Lui JCS
Name of Conference33rd International Symposium on Computer Performance, Modeling, Measurements, and Evaluation / IFIP WG 7.3 Performance
Start Date of Conference19/10/2015
End Date of Conference21/10/2015
Place of ConferenceSydney
Journal namePerformance Evaluation,Performance Evaluation
Detailed descriptionorganized by IFIP WG 7.3. This conference was considered as a tier-A conference as classified by the external visiting committee in FoE in 2011. <
Year2015
Month9
Day1
Volume Number91
PublisherELSEVIER SCIENCE BV
Pages187 - 204
ISSN0166-5316
eISSN1872-745X
LanguagesEnglish-United Kingdom
KeywordsCompetitive influence maximization; Information diffusion; Social networks; Viral marketing
Web of Science Subject CategoriesComputer Science; Computer Science, Hardware & Architecture; Computer Science, Theory & Methods

Last updated on 2021-15-01 at 00:47