CoFIM : A community-based framework for influence maximization on large-scale networks

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

80 Scopus Citations
View graph of relations

Author(s)

  • Jiaxing Shang
  • Shangbo Zhou
  • Xin LI
  • Lianchen Liu
  • Hongchun Wu

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)88-100
Journal / PublicationKnowledge-Based Systems
Volume117
Online published30 Sep 2016
Publication statusPublished - 1 Feb 2017

Abstract

Influence maximization is a classic optimization problem studied in the area of social network analysis and viral marketing. Given a network, it is defined as the problem of finding k seed nodes so that the influence spread of the network can be optimized. Kempe et al. have proved that this problem is NP hard and the objective function is submodular, based on which a greedy algorithm was proposed to give a near-optimal solution. However, this simple greedy algorithm is time consuming, which limits its application on large-scale networks. Heuristic algorithms generally cannot provide any performance guarantee. To solve this problem, in this paper we propose CoFIM, a community-based framework for influence maximization on large-scale networks. In our framework the influence propagation process is divided into two phases: (i) seeds expansion; and (ii) intra-community propagation. The first phase is the expansion of seed nodes among different communities at the beginning of diffusion. The second phase is the influence propagation within communities which are independent of each other. Based on the framework, we derive a simple evaluation form of the total influence spread which is submodular and can be efficiently computed. Then we further propose a fast algorithm to select the seed nodes. Experimental results on synthetic and nine real-world large datasets including networks with millions of nodes and hundreds of millions of edges show that our algorithm achieves competitive results in influence spread as compared with state-of-the-art algorithms and it is much more efficient in terms of both time and memory usage.

Research Area(s)

  • Community structure, Computational complexity, Diffusion model, Influence maximization, Large-scale networks

Citation Format(s)

CoFIM : A community-based framework for influence maximization on large-scale networks. / Shang, Jiaxing; Zhou, Shangbo; LI, Xin; Liu, Lianchen; Wu, Hongchun.

In: Knowledge-Based Systems, Vol. 117, 01.02.2017, p. 88-100.

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