Influence Maximization: Seeding Based on Community Structure

Influence maximization problem attempts to find a small subset of nodes in a social network that makes the expected influence maximized, which has been researched intensively before. Most of the existing literature focus only on maximizing total influence, but it ignores whether the influential distribution is balanced through the network. Even though the total influence is maximized, but gathered in a certain area of social network. Sometimes, this is not advisable. In this article, we propose a novel seeding strategy based on community structure, and formulate the Influence Maximization with Community Budget (IMCB) problem. In this problem, the number of seed nodes in each community is under the cardinality constraint, which can be classified as the problem of monotone submodular maximization under the matroid constraint. To give a satisfactory solution for IMCB problem under the triggering model, we propose the IMCB-Framework, which is inspired by the idea of continuous greedy process and pipage rounding, and derive the best approximation ratio for this problem. In IMCB-Framework, we adopt sampling techniques to overcome the high complexity of continuous greedy. Then, we propose a simplified pipage rounding algorithm, which reduces the complexity of IMCB-Framework further. Finally, we conduct experiments on three real-world datasets to evaluate the correctness and effectiveness of our proposed algorithms, as well as the advantage of IMCB-Framework against classical greedy method.