A recursive method for big network influence estimation

Wei Xue Lu, Chuan Zhou, Jia Wu, Chun-Yi Liu, Li Gao, Yue Hu

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

Influence maximization aims to find a set of highly influential nodes in a social network to maximize the spread of influence. The most difficult part of the problem is to estimate the influence spread of any seed set, which has been proved to be #P-hard. There is no efficient method to estimate the influence spread of any seed set till now. Thus, the most common way to obtain the approximate influence spread is Monte Carlo simulation and two popular simulating strategies are applied: one is propagation strategy, the other is snapshot strategy. The former only fits for particular seed set and the latter incurs heavy memory cost. In this paper, we present a new algorithm to estimate the influence spread of any seed set. Our algorithm recursively estimates the influence spread using reachable probabilities from node to node. Accordingly, we provide three strategies to start the recursion by integrating the memory cost and computing efficiency. Experiments demonstrate high performance of our influence estimation.

Original languageEnglish
Title of host publicationIJCNN 2016
Subtitle of host publicationProceedings of the 2016 International Joint Conference on Neural Networks
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages4709-4714
Number of pages6
ISBN (Electronic)9781509006205, 9781509006199
ISBN (Print)9781509006212
DOIs
Publication statusPublished - 31 Oct 2016
Externally publishedYes
Event2016 International Joint Conference on Neural Networks, IJCNN 2016 - Vancouver, Canada
Duration: 24 Jul 201629 Jul 2016

Conference

Conference2016 International Joint Conference on Neural Networks, IJCNN 2016
CountryCanada
CityVancouver
Period24/07/1629/07/16

Fingerprint

Dive into the research topics of 'A recursive method for big network influence estimation'. Together they form a unique fingerprint.

Cite this