B0344
Title: A generalized influence maximization problem
Authors: Sumit Kumar Kar - University of North Carolina at Chapel Hill (United States) [presenting]
Nilay Tanik Argon - University of North Carolina at Chapel Hill (United States)
Shankar Bhamidi - University of North Carolina at Chapel Hill (United States)
Serhan Ziya - University of North Carolina at Chapel Hill (United States)
Abstract: Influence maximization problem (IMP) is an optimization problem with applications in viral marketing, epidemiology, etc. that aims at optimally choosing a specified number of nodes for seeding (i.e., actively influencing) in a social network. Seeded nodes start a discrete time passive viral process where influenced nodes influence their neighbours stochastically according to some diffusion model. IMP maximizes the expected total number of eventually influenced people. IMP is NP-hard but a greedy solution achieves a $(1-1/e)$ approximation guarantee under the triggering model. The current work (generalized IMP) maximizes the expected value of a much more generalized (possibly non-linear) reward function that brings possibly different rewards from different nodes and depends on the times at which they are influenced. Influence propagation may be observed until a pre-specified time, each node may be allocated multiple seeds, and seeded nodes are not necessarily influenced. Also, some nodes may be unavailable for seeding, others may have individual restrictions on how many seeds they may be allocated, and the probability of whether a seeded node is influenced is non-decreasing with the number of allocated seeds. This problem has been addressed by formulating a generalized Triggering model where a greedy algorithm has been shown to achieve a $(1-1/e)$ approximation guarantee.
