A recursive method for big network influence estimation

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

doi:10.1109/IJCNN.2016.7727818

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 proceeding › Conference proceeding contribution › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	IJCNN 2016
Subtitle of host publication	Proceedings of the 2016 International Joint Conference on Neural Networks
Place of Publication	Piscataway, NJ
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	4709-4714
Number of pages	6
ISBN (Electronic)	9781509006205, 9781509006199
ISBN (Print)	9781509006212
DOIs	https://doi.org/10.1109/IJCNN.2016.7727818
Publication status	Published - 31 Oct 2016
Externally published	Yes
Event	2016 International Joint Conference on Neural Networks, IJCNN 2016 - Vancouver, Canada Duration: 24 Jul 2016 → 29 Jul 2016

Conference

Conference	2016 International Joint Conference on Neural Networks, IJCNN 2016
Country/Territory	Canada
City	Vancouver
Period	24/07/16 → 29/07/16

Access to Document

10.1109/IJCNN.2016.7727818

Cite this

@inproceedings{fc30b112d9b5402192843235ec4a4152,

title = "A recursive method for big network influence estimation",

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.",

author = "Lu, {Wei Xue} and Chuan Zhou and Jia Wu and Chun-Yi Liu and Li Gao and Yue Hu",

year = "2016",

month = oct,

day = "31",

doi = "10.1109/IJCNN.2016.7727818",

language = "English",

isbn = "9781509006212",

pages = "4709--4714",

booktitle = "IJCNN 2016",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "2016 International Joint Conference on Neural Networks, IJCNN 2016 ; Conference date: 24-07-2016 Through 29-07-2016",

}

Lu, WX, Zhou, C, Wu, J, Liu, C-Y, Gao, L & Hu, Y 2016, A recursive method for big network influence estimation. in IJCNN 2016: Proceedings of the 2016 International Joint Conference on Neural Networks. Institute of Electrical and Electronics Engineers (IEEE), Piscataway, NJ, pp. 4709-4714, 2016 International Joint Conference on Neural Networks, IJCNN 2016, Vancouver, Canada, 24/07/16. https://doi.org/10.1109/IJCNN.2016.7727818

A recursive method for big network influence estimation. / Lu, Wei Xue; Zhou, Chuan; Wu, Jia et al.

IJCNN 2016: Proceedings of the 2016 International Joint Conference on Neural Networks. Piscataway, NJ : Institute of Electrical and Electronics Engineers (IEEE), 2016. p. 4709-4714.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - A recursive method for big network influence estimation

AU - Lu, Wei Xue

AU - Zhou, Chuan

AU - Wu, Jia

AU - Liu, Chun-Yi

AU - Gao, Li

AU - Hu, Yue

PY - 2016/10/31

Y1 - 2016/10/31

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85007155091&partnerID=8YFLogxK

U2 - 10.1109/IJCNN.2016.7727818

DO - 10.1109/IJCNN.2016.7727818

M3 - Conference proceeding contribution

AN - SCOPUS:85007155091

SN - 9781509006212

SP - 4709

EP - 4714

BT - IJCNN 2016

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, NJ

T2 - 2016 International Joint Conference on Neural Networks, IJCNN 2016

Y2 - 24 July 2016 through 29 July 2016

ER -

A recursive method for big network influence estimation

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this