Efficient diversified influence maximization with adaptive policies

摘要

Influence maximization (IM) in social media aims at finding influential seed users to trigger large online cascading influence spread. Existing studies mainly focus on maximizing the number of the activated nodes, but the diversity of the activated nodes has been mostly ignored even though it is crucial in many real-world applications, e.g., diversity of the influenced crowd can reduce the risk of marketing campaigns, or diversity of recommended items can improve the recommendation quality. In this paper, we study the diversified influence maximization (DIM) problem which aims to select k nodes such that both the number of activated nodes and the diversity of the activated nodes can be maximized. By designing a practical diversity function to model the distribution of activated nodes among all communities, we model the DIM problem by maximizing a parameterized linear combination of the diversity and the active node number. To tackle the NP-hardness of the DIM problem, we propose an efficient diversified influence maximization algorithm, diversified influence maximization via martingale (DIMM), which returns a 1−1∕e−ε-approximate solution with at least 1−2∕nℓ probability. Moreover, as the influence spread is highly stochastic and the DIM setting leaves no reserved measures for handling unforeseen events, we present an improved version of the algorithm named adaptive diversified influence maximization via martingale (ADIMM) with the adaptive setting. With the adaptive RI-πα policy, ADIMM is able to return an α(1−e−1∕α)-approximate solution with at least 1−1∕nℓ probability. Finally, we experimentally evaluate our algorithm against existing algorithms on large-scale real-world datasets. The experimental results validate the effectiveness and efficiency of our proposed algorithms.