Influence efficiency maximization: How can we spread information efficiently?

Zhu Xiang

doi:10.1016/j.jocs.2017.11.001

Influence efficiency maximization: How can we spread information efficiently?

2018-09-01

4

PRE

AI

DOI：10.1016/j.jocs.2017.11.001

Original

Original request for help

Save

Abstract

En 中文

Influence maximization problem, due to its popularity, has been studied extensively these years. It aims at targeting a set of seed nodes for maximizing the expected number of activated nodes at the end of the information diffusion process. During the process of information diffusion, an active node will try to influence its neighbors in the next iteration. Thus, it will cost several iterations before a node is activated except seed nodes, which is called propagation time delay. However, it is not discussed in influence maximization problem. Thus, there is a need to understand the influence efficiency in the network. Motivated by this demand, we propose a novel problem called Influence Efficiency Maximization problem, which takes the propagation time delay into consideration. We prove that the proposed problem is NP-hard under independent cascade model and the influence efficiency function is submodular. Furthermore, we also prove the computation of influence efficiency is #P-hard under independent cascade model. After that, several algorithms are proposed to solve the influence efficiency maximization problem. Finally, we conduct a series of experiment with real-world data sets to verify the proposed algorithms. The experimental results demonstrate the performance of the proposed algorithms. (C) 2017 Elsevier B.V. All rights reserved.

Keywords:

Influence maximization

Information diffusion

Influence efficiency

Social network

Influence efficiency maximization: How can we spread information efficiently?

Abstract

AI Summary

Journal

Organization