A Query Approach for Influence Maximization on Specific Users in Social Networks
Authors:
- 13 June 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 27 (2) , 340-353
Abstract
Influence maximization is introduced to maximize the profit of viral marketing in social networks. The weakness of influence maximization is that it does not distinguish specific users from others, even if some items can be only useful for the specific users. For such items, it is a better strategy to focus on maximizing the influence on the specific users. In this paper, we formulate an influence maximization problem as query processing to distinguish specific users from others. We show that the query processing problem is NP-hard and its objective function is submodular. We propose an expectation model for the value of the objective function and a fast greedy-based approximation method using the expectation model. For the expectation model, we investigate a relationship of paths between users. For the greedy method, we work out an efficient incremental updating of the marginal gain to our objective function. We conduct experiments to evaluate the proposed method with real-life datasets, and compare the results with those of existing methods that are adapted to the problem. From our experimental results, the proposed method is at least an order of magnitude faster than the existing methods in most cases while achieving high accuracy.Keywords
Funding Information
- National Research Foundation of Korea
- Korean government (NRF-2014R1A1A2002499)
This publication has 18 references indexed in Scilit:
- Profit Maximization over Social Networks2012
- IRIE: Scalable and Robust Influence Maximization in Social Networks2012
- On minimizing budget and time in influence propagation over social networksSocial Network Analysis and Mining, 2012
- A data-based approach to social influence maximizationProceedings of the VLDB Endowment, 2011
- CELF++2011
- Efficient influence maximization in social networks2009
- Competitive Influence Maximization in Social Networks2007
- Maximizing influence in a competitive social network2007
- Cost-effective outbreak detection in networks2007
- Mining the network value of customers2001