Community-based rumor blocking maximization in social networks: algorithms and analysis (Q2202013)

This paper studies the competitive independent cascade model based on the independent cascade diffusion in social network analysis. Given a network with \(m\) disjoint communities \(S=\{S_1,\cdots,S_m\}\) and budget \(b\), where a budget allocation is \(x=(x_1,\cdots,x_m)\) with \(\sum x_i=b\). The problem under consideration is to choose optimal node set \(D\) such that we can protect nodes from being infected by rumors as much as possible, where \(|D\cap S_i|\le x_i\) for any \(S_i\subseteq S\). The paper proposes a budget allocation algorithm using sub-modular function maximization over integer lattices, which gives an \(1-1/e\) approximation guarantee and the objective function is shown to be monotone and diminishing return sub-modular. A speedup algorithm is introduced. It ensures the performance but has lower time complexity. Simulations results have been presented to illustrate the theoretical results.