Near-Optimal Convergent Approach for Composed Influence Maximization Problem in Social Networks

Abstract

Crowd psychology is a critical factor when considering information diffusion, which has been modeled as composed influence. The composed influence is represented as a hyperedge in a graph model. A hyperedge e = (He, v) contains the head node set He and tail node v. Then a social network is modeled as a hypergraph. e can only propagate this influence when all nodes in He become active first. In this paper, the Composed Influence Maximization (CIM) also aims to select k initially-influenced seed users in such a social network. The objective is to maximize the expected number of eventually-influenced users. We present an approximating method for this objective function by formulating a series of submodular functions and these functions are convergent. Then, we develop a lower bound and an upper bound problems whose objective functions are submodular. We design a greedy strategy based on the lower bound maximization for solving CIM. We formulate a sandwich approximation framework, which preserves the theoretical analysis result. Finally, we evaluate our algorithm on real world data sets. The results show the effectiveness and the efficiency of the proposed algorithm.

Keywords

• Composed influence
• influence maximization
• independent cascade
• social networks