Community Influence Maximization Based on Flexible Budget in Social Networks

The influence maximization (IM) problem is a vital issue in social networks. In community structure, community influence maximization (CIM) chooses the seed nodes based on the characteristics of the community structure instead of blindly selecting seed nodes from the entire network. However, it depends on the community size, which results in high influence nodes not being selected due to a lack of budget. In this paper, we propose a budget allocation strategy for the CIM problem. To solve the problem of less influence spread in sparse community structure, we propose a community influence maximization algorithm based on a flexible budget and adopt the reverse influence sampling (RIS) approach to sample the network structure, which reduces the time complexity of the greedy algorithm. Then, we consider the imbalance of influence expansion between communities, and we propose a balanced community influence maximization algorithm, which maintains the relative balance of the influence spread ratio between communities. In addition, we analyze the time complexity of our proposed algorithms and give a theoretical guarantee. Finally, we conduct extensive experiments on three real datasets. Compared with other baseline algorithms, the results show that the proposed algorithms have a good performance in terms of influence maximization and community influence balance.