Abstract:
Information diffusion has been a crucial issue in social network research. The influence maximization problem asks for ways to identify nodes that are able to maximally diffuse information through a network. Recently, game-theoretical methods emerged that partitions a network into coalitions, and facilitate influence maximization. A notable example is a method based on Shapley value [13]. A major disadvantage with this approach is the lack of consideration of externality on coalition formation. In this paper, we propose consensus value for influence maximization (CVIM) to overcome this limitation. After forming coalitions using consensus value, the method selects initial coalitions based on the gain of each coalition, and finally chooses seed nodes in the selected coalitions. Empirical evidence over several real-world networks demonstrates that CVIM produces better results of influence maximization while significantly reducing the running time as compared to existing approaches.
