Robust influence maximization

Wei Chen; Tian Lin; Zihan Tan; Mingfei Zhao; Xuren Zhou

doi:10.1145/2939672.2939745

Robust influence maximization

Wei Chen
, Tian Lin
, Zihan Tan
, Mingfei Zhao
, Xuren Zhou

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

148 Scopus citations

Abstract

In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem - the task of finding k seed nodes in a social network to maximize the influence spread. We propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization.

Original language	English (US)
Title of host publication	KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Publisher	Association for Computing Machinery
Pages	795-804
Number of pages	10
ISBN (Electronic)	9781450342322
DOIs	https://doi.org/10.1145/2939672.2939745
State	Published - Aug 13 2016
Externally published	Yes
Event	22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016 - San Francisco, United States Duration: Aug 13 2016 → Aug 17 2016

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Volume	13-17-August-2016

Other

Other	22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016
Country/Territory	United States
City	San Francisco
Period	8/13/16 → 8/17/16

Bibliographical note

Publisher Copyright:
© 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM.

Keywords

Influence maximization
Information diffusion
Robust optimization
Social networks

Publisher link

10.1145/2939672.2939745

Find It

Find It at U of M Libraries

Cite this

Chen, W., Lin, T., Tan, Z., Zhao, M., & Zhou, X. (2016). Robust influence maximization. In KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 795-804). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. 13-17-August-2016). Association for Computing Machinery. https://doi.org/10.1145/2939672.2939745

Robust influence maximization. / Chen, Wei; Lin, Tian; Tan, Zihan et al.
KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2016. p. 795-804 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. 13-17-August-2016).

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

Chen, W, Lin, T, Tan, Z, Zhao, M & Zhou, X 2016, Robust influence maximization. in KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, vol. 13-17-August-2016, Association for Computing Machinery, pp. 795-804, 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016, San Francisco, United States, 8/13/16. https://doi.org/10.1145/2939672.2939745

@inproceedings{66d2e35de7984098b4576c8f840fb31c,

title = "Robust influence maximization",

abstract = "In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem - the task of finding k seed nodes in a social network to maximize the influence spread. We propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization.",

keywords = "Influence maximization, Information diffusion, Robust optimization, Social networks",

author = "Wei Chen and Tian Lin and Zihan Tan and Mingfei Zhao and Xuren Zhou",

note = "Publisher Copyright: {\textcopyright} 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM.; 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016 ; Conference date: 13-08-2016 Through 17-08-2016",

year = "2016",

month = aug,

day = "13",

doi = "10.1145/2939672.2939745",

language = "English (US)",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery",

pages = "795--804",

booktitle = "KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

}

TY - GEN

T1 - Robust influence maximization

AU - Chen, Wei

AU - Lin, Tian

AU - Tan, Zihan

AU - Zhao, Mingfei

AU - Zhou, Xuren

PY - 2016/8/13

Y1 - 2016/8/13

N2 - In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem - the task of finding k seed nodes in a social network to maximize the influence spread. We propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization.

AB - In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem - the task of finding k seed nodes in a social network to maximize the influence spread. We propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization.

KW - Influence maximization

KW - Information diffusion

KW - Robust optimization

KW - Social networks

UR - https://www.scopus.com/pages/publications/84984973515

UR - https://www.scopus.com/pages/publications/84984973515#tab=citedBy

U2 - 10.1145/2939672.2939745

DO - 10.1145/2939672.2939745

M3 - Conference contribution

AN - SCOPUS:84984973515

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 795

EP - 804

BT - KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

PB - Association for Computing Machinery

T2 - 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016

Y2 - 13 August 2016 through 17 August 2016

ER -

Robust influence maximization

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this