Tracking top-k influential users with relative errors

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

2 Scopus Citations
View graph of relations

Author(s)

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

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationCIKM 2019
Subtitle of host publicationProceedings of the 28th ACM International Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery
Pages1783-1792
ISBN (Print)978-1-4503-6976-3
Publication statusPublished - Nov 2019

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Conference

Title28th ACM International Conference on Information and Knowledge Management, CIKM 2019
PlaceChina
CityBeijing
Period3 - 7 November 2019

Abstract

Tracking influential users in a dynamic social network is a fundamental step in fruitful applications, such as social recommendation, network topology optimization, and blocking rumour spreading. The major obstacle in mining top influential users is that estimating users' influence spreads is #P-hard under most influence propagation models. Previous studies along this line either seek heuristic solutions or may return meaningless results due to the lack of prior knowledge about users' influence in the dynamic network. In this paper, we tackle the problem of tracking top-k influential individuals in a dynamic social network. When a top-k query is issued, our algorithm returns a set S of more than k users. With high probability, our algorithm guarantees that S contains all real top-k influential users and there exists a relative error ϵ < 1 such that the least influential user in S has influence at least (1 − ϵ)k, where k is the influence of the k-th most influential user and we can adjust ϵ via parameter settings. Controlling such a relative error enables us to obtain meaningful results even when we know nothing about the value of k or k changes over time in the dynamic network. In addition to the thorough theoretical results, our experimental results on large real networks clearly demonstrate the effectiveness and efficiency of our algorithm.

Research Area(s)

  • Sample complexity, Social influence, Top-k ranking

Bibliographic Note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Citation Format(s)

Tracking top-k influential users with relative errors. / Yang, Yu; Wang, Zhefeng; Jin, Tianyuan et al.

CIKM 2019 : Proceedings of the 28th ACM International Conference on Information and Knowledge Management. Association for Computing Machinery, 2019. p. 1783-1792 (International Conference on Information and Knowledge Management, Proceedings).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review