Logo image
Back
OASNET: an optimal allocation approach to influence maximization in modular social networks
Conference proceeding

OASNET: an optimal allocation approach to influence maximization in modular social networks

Tianyu Cao, Xindong Wu, Song Wang and Xiaohua Hu
Proceedings of the 2010 ACM Symposium on applied computing, pp 1088-1094
22 Mar 2010
DOI: https://doi.org/10.1145/1774088.1774314

Abstract

influence maximization modular social network optimal allocation
Influence maximization in a social network is to target a given number of nodes in the network such that the expected number of activated nodes from these nodes is maximized. A social network usually exhibits some degree of modularity. Previous research efforts that made use of this topological property are restricted to random networks with two communities. In this paper, we firstly transform the influence maximization problem in a modular social network to an optimal resource allocation problem in the same network. We assume that the communities of the social network are disconnected. We then propose a recursive relation for finding such an optimal allocation. We prove that finding an optimal allocation in a modular social network is NP-hard and propose a new optimal dynamic programming algorithm to solve the problem. We name our new algorithm OASNET (Optimal Allocation in a Social NETwork). We compare OASNET with equal allocation, proportional allocation, random allocation and selecting top degree nodes without any allocation strategy on both synthetic and real world datasets. Experimental results show that OASNET outperforms these four heuristics.

Metrics

5 Record Views
48 citations in Scopus

Details

Logo image