Influence maximization based on maximum inner product search

In recent years, with the rapid development of social networks, the scale of social networks has grown dramatically. The relationship of people in social networks plays a key role in information propagation. Due to its huge social value, the issue of influence maximization has attracted more and more researchers’ attention. With the increase of network scale, the running time has become a key issue. To resolve it, many heuristic algorithms for the influence maximization problem has been proposed. These algorithms have been verified to be be very efficient, but their effectiveness cannot be guaranteed for many networks in the real word. Therefore, it has become highly urgent to choose an influence maximization algorithm that is simultaneously efficient and effective. This paper proposes an algorithm based on the greedy algorithm framework, which converts the influence maximization problem into a maximum inner product search problem. This method can complete the selection of seed nodes for large-scale networks in nearly linear time. Compared with other algorithms, this algorithm has more application value.