CT-IC: Continuously activated and Time-restricted Independent Cascade model for viral marketing

摘要

Influence maximization problem has gained much attention, which is to find the most influential people. Efficient algorithms have been proposed to solve influence maximization problem according to the proposed diffusion models. Existing diffusion models assume that a node influences its neighbors once, and there is no time constraint in activation process. However, in real-world marketing situations, people influence his/her acquaintances repeatedly, and there are often time restrictions for a marketing. This paper proposes a new realistic influence diffusion model Continuously activated and Time-restricted IC (CT-IC) model which generalizes the IC model. In CT-IC model, every active node activate its neighbors repeatedly, and activation continues until a given time. We first prove CT-IC model satisfies monotonicity and submodularity for influence spread. We then provide an efficient method for calculating exact influence spread for a directed tree. Finally, we propose a scalable influence evaluation algorithm under CT-IC model CT-IPA. Our experiments show CT-IC model finds seeds of higher influence spread than IC model, and CT-IPA is four orders of magnitude faster than the greedy algorithm while providing similar influence spread.