Community-level competitive influence payoff maximization
摘要
With the application of social networks in e-commerce and political campaigns, competitive influence maximization has gained significant attention as a way to maximize the influence spread in a competitive environment. Most previous studies have focused on maximizing the propagation coverage. However, in the real world, people are concerned with the spread of influence in different communities, such as religious groups or districts, and evaluate influence based on community-level payoffs. For example, in US elections, political parties are more concerned about how many districts they win and the total payoff they receive in all districts. Therefore, we define the competitive influence payoff maximization problem from a community perspective. To better study this problem, we introduce a novel competitive influence propagation model, competitive influence propagation with reconsideration (CIPR), which accounts for real scenarios in which users may choose less influential options when one of the competing influences on the same user is not significantly dominant. We demonstrate that the expected influence coverage function under CIPR is both monotone and submodular, and we use CIPR as the foundational model in this paper. Given the NP-hardness of finding the optimal seed set, we propose an evolutionary framework to derive approximate solutions. For the special case with minimal inter-community influence, due to strong homophily, we leverage the submodularity and monotonicity of the CIPR model to develop the greedy algorithm. Our experiments on real-world datasets verify the feasibility and accuracy of our proposed model and algorithm.