The diffusion of influence in a social network has been recently investigated in various fields. In this paper, we study the problem of minimizing the expected complete influence time of a social network under the resource constraint. We focus on the case where the budget for influencing the initial target set of individuals is limited. The incremental chance model is adopted to characterize the diffusion of influence, and a lower bound for the expected complete influence time is presented. In order to solve the problem effectively, we modify the well-known heuristic search approach, the A* algorithm, and provide a series of strategies for designing the heuristic functions. Finally, we perform experiments to show that the proposed algorithm generally performs better than widely used trivial heuristic methods.
展开▼
