Tracking Influential Individuals in Dynamic Networks

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

24 Scopus Citations
View graph of relations

Author(s)

  • Yu Yang
  • Zhefeng Wang
  • Jian Pei
  • Enhong Chen

Detail(s)

Original languageEnglish
Article number7999292
Pages (from-to)2615-2628
Journal / PublicationIEEE Transactions on Knowledge and Data Engineering
Volume29
Issue number11
Online published1 Aug 2017
Publication statusPublished - Nov 2017
Externally publishedYes

Abstract

In this paper, we tackle a challenging problem inherent in a series of applications: tracking the influential nodes in dynamic networks. Specifically, we model a dynamic network as a stream of edge weight updates. This general model embraces many practical scenarios as special cases, such as edge and node insertions, deletions as well as evolving weighted graphs. Under the popularly adopted linear threshold model and independent cascade model, we consider two essential versions of the problem: finding the nodes whose influences passing a user specified threshold and finding the top-k most influential nodes. Our key idea is to use the polling-based methods and maintain a sample of random RR sets so that we can approximate the influence of nodes with provable quality guarantees. We develop an efficient algorithm that incrementally updates the sample random RR sets against network changes. We also design methods to determine the proper sample sizes for the two versions of the problem so that we can provide strong quality guarantees and, at the same time, be efficient in both space and time. In addition to the thorough theoretical results, our experimental results on five real network data sets clearly demonstrate the effectiveness and efficiency of our algorithms.

Research Area(s)

  • dynamic networks, Social influence

Citation Format(s)

Tracking Influential Individuals in Dynamic Networks. / Yang, Yu; Wang, Zhefeng; Pei, Jian et al.

In: IEEE Transactions on Knowledge and Data Engineering, Vol. 29, No. 11, 7999292, 11.2017, p. 2615-2628.

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