Influence efficiency maximization : How can we spread information efficiently?

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

6 Scopus Citations
View graph of relations

Author(s)

  • Xiang Zhu
  • Zhefeng Wang
  • Yu Yang
  • Bin Zhou
  • Yan Jia

Detail(s)

Original languageEnglish
Pages (from-to)245-256
Journal / PublicationJournal of Computational Science
Volume28
Online published11 Nov 2017
Publication statusPublished - Sep 2018
Externally publishedYes

Abstract

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.

Research Area(s)

  • Influence maximization, Information diffusion, Influence efficiency, Social network

Citation Format(s)

Influence efficiency maximization : How can we spread information efficiently? / Zhu, Xiang; Wang, Zhefeng; Yang, Yu et al.

In: Journal of Computational Science, Vol. 28, 09.2018, p. 245-256.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review