Logo image
Back
Maximizing influence spread in modular social networks by optimal resource allocation
Journal article   Open access   Peer reviewed

Maximizing influence spread in modular social networks by optimal resource allocation

Tianyu Cao, Xindong Wu, Song Wang and Xiaohua Hu
Expert systems with applications, v 38(10), pp 13128-13135
15 Sep 2011
DOI: https://doi.org/10.1016/j.eswa.2011.04.119
url
http://manuscript.elsevier.com/S0957417411006464/pdf/S0957417411006464.pdfView
Accepted (AM)Open Access (Publisher-Specific),  Open

Abstract

Influence maximization Modular social network Optimal allocation
► We transform the influence maximization problem in modular socialnetworks to a resource allocation problem. ► We derive a recursive relationship for optimal allocation in a modular social network. ► We prove that the optimal allocation problem is NP-hard. ► We give a dynamic programming algorithm to solve the optimal resource allocation problem. ► We validate the effectiveness of the proposed algorithm OASNET on three real world networks. 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. 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 dynamic programming algorithm to solve the problem. We name our new algorithm OASNET (Optimal Allocation in a Social NETwork). We compare OASNET with the high degree heuristics, the single degree discount heuristics, and the degree discount heuristics on three real world datasets. Experimental results show that OASNET outperforms comparison heuristics significantly on the independent cascade model when the diffusion probability is greater than a certain threshold.

Metrics

7 Record Views
25 citations in Web of Science
33 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
International collaboration
Web of Science research areas
Computer Science, Artificial Intelligence
Engineering, Electrical & Electronic
Operations Research & Management Science
Logo image