Maximizing Time-aware Welfare for Mixed Items

Welfare maximization (WM) aims to select a group of seed nodes to allocate different items for marketing, so that the whole welfare after diffusion over a social network is maximized. It has attracted much attention due to the practical applications such as viral marketing and online advertisements, where the economic incentives are incorporated into users' adoption behaviors. However, existing studies ignore the time impact on the diffusion and consider a single item type. In this paper, we propose an effective time-aware utility-driven independent cascade (TUIC) model, that incorporates the time-aware multi-item propagation, utility-driven item adoption, and mixed item relationships together. We identify and formulate the time-aware welfare maximization problem. We develop a general framework to address the problem for mixed competitive, complementary, and independent items. It derives item allocation with the$(1 -1/e-\epsilon)$approximate social welfare in special cases. Extensive experiments on several real-life social networks demonstrate the effectiveness of TUIC model and the efficiency of the proposed framework, compared to the state of the arts.