On Influence Maximization to Target Users: A Diffusion-Limited Model in the Presence of Multiple Acceptances

  • 張 健暐

Student thesis: Master's Thesis

Abstract

In this paper we study a novel problem of influence maximization in social networks: Given a period of promotion time and a set of target users each of which can be activated by its neighbors multiple times we aim at maximizing the total acceptance frequency of these target users by initially selecting k most influential seeds The promising viral marketing paradigm on social network is different from the current research in two main aspects First instead of maximizing the message spread over the entire social network we focus on the target market since the business vendors almost specify the target users before designing its marketing strategy Second the status of a user is no longer a binary indicator representing either active or inactive In the new model the user status turns to be an integer value reflecting the amount of influences delivered to that user In this paper we prove the NP-hard nature of this challenging problem We further present several strategies including two efficiently heuristic algorithms and a greedy algorithm as the baseline to select the initial k seeds in pursuit of resulting quality close to the optimal one As demonstrated in the empirical study on real data instead of only providing the flexibility of striking a compromise between the execution efficiency and the resulting quality our proposed heuristic algorithms can achieve high efficiency and meanwhile obtain the target acceptance frequency even better than the greedy result in some cases demonstrating its prominent feasibility to resolve the challenging problem efficiently
Date of Award2014 Aug 26
Original languageEnglish
SupervisorKun-Ta Chuang (Supervisor)

Cite this

'