Factorization bandits for online influence maximization

Qingyun Wu; Zhige Li; Huazheng Wang; Wei Chen; Hongning Wang

doi:10.1145/3292500.3330874

Factorization bandits for online influence maximization

Qingyun Wu, Zhige Li, Huazheng Wang, Wei Chen, Hongning Wang

College of Information Sciences and Technology

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

26 Scopus citations

Abstract

In this paper, we study the problem of online influence maximization in social networks. In this problem, a learner aims to identify the set of “best influencers” in a network by interacting with the network, i.e., repeatedly selecting seed nodes and observing activation feedback in the network. We capitalize on an important property of the influence maximization problem named network assortativity, which is ignored by most existing works in online influence maximization. To realize network assortativity, we factorize the activation probability on the edges into latent factors on the corresponding nodes, including influence factor on the giving nodes and susceptibility factor on the receiving nodes. We propose an upper confidence bound based online learning solution to estimate the latent factors, and therefore the activation probabilities. Considerable regret reduction is achieved by our factorization based online influence maximization algorithm. Extensive empirical evaluations on two real-world networks showed the effectiveness of our proposed solution.

Original language	English (US)
Title of host publication	KDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Publisher	Association for Computing Machinery
Pages	636-646
Number of pages	11
ISBN (Electronic)	9781450362016
DOIs	https://doi.org/10.1145/3292500.3330874
State	Published - Jul 25 2019
Event	25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019 - Anchorage, United States Duration: Aug 4 2019 → Aug 8 2019

Publication series

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

Conference

Conference	25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019
Country/Territory	United States
City	Anchorage
Period	8/4/19 → 8/8/19

All Science Journal Classification (ASJC) codes

Software
Information Systems

Access to Document

10.1145/3292500.3330874

Cite this

Wu, Q., Li, Z., Wang, H., Chen, W., & Wang, H. (2019). Factorization bandits for online influence maximization. In KDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 636-646). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). Association for Computing Machinery. https://doi.org/10.1145/3292500.3330874

@inproceedings{50af01318d47423c83b794bd62c3aa00,

title = "Factorization bandits for online influence maximization",

abstract = "In this paper, we study the problem of online influence maximization in social networks. In this problem, a learner aims to identify the set of “best influencers” in a network by interacting with the network, i.e., repeatedly selecting seed nodes and observing activation feedback in the network. We capitalize on an important property of the influence maximization problem named network assortativity, which is ignored by most existing works in online influence maximization. To realize network assortativity, we factorize the activation probability on the edges into latent factors on the corresponding nodes, including influence factor on the giving nodes and susceptibility factor on the receiving nodes. We propose an upper confidence bound based online learning solution to estimate the latent factors, and therefore the activation probabilities. Considerable regret reduction is achieved by our factorization based online influence maximization algorithm. Extensive empirical evaluations on two real-world networks showed the effectiveness of our proposed solution.",

author = "Qingyun Wu and Zhige Li and Huazheng Wang and Wei Chen and Hongning Wang",

note = "Publisher Copyright: {\textcopyright} 2019 Association for Computing Machinery.; 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019 ; Conference date: 04-08-2019 Through 08-08-2019",

year = "2019",

month = jul,

day = "25",

doi = "10.1145/3292500.3330874",

language = "English (US)",

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

publisher = "Association for Computing Machinery",

pages = "636--646",

booktitle = "KDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

}

Wu, Q, Li, Z, Wang, H, Chen, W & Wang, H 2019, Factorization bandits for online influence maximization. in KDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery, pp. 636-646, 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019, Anchorage, United States, 8/4/19. https://doi.org/10.1145/3292500.3330874

Factorization bandits for online influence maximization. / Wu, Qingyun; Li, Zhige; Wang, Huazheng et al.
KDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2019. p. 636-646 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

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

TY - GEN

T1 - Factorization bandits for online influence maximization

AU - Wu, Qingyun

AU - Li, Zhige

AU - Wang, Huazheng

AU - Chen, Wei

AU - Wang, Hongning

PY - 2019/7/25

Y1 - 2019/7/25

N2 - In this paper, we study the problem of online influence maximization in social networks. In this problem, a learner aims to identify the set of “best influencers” in a network by interacting with the network, i.e., repeatedly selecting seed nodes and observing activation feedback in the network. We capitalize on an important property of the influence maximization problem named network assortativity, which is ignored by most existing works in online influence maximization. To realize network assortativity, we factorize the activation probability on the edges into latent factors on the corresponding nodes, including influence factor on the giving nodes and susceptibility factor on the receiving nodes. We propose an upper confidence bound based online learning solution to estimate the latent factors, and therefore the activation probabilities. Considerable regret reduction is achieved by our factorization based online influence maximization algorithm. Extensive empirical evaluations on two real-world networks showed the effectiveness of our proposed solution.

AB - In this paper, we study the problem of online influence maximization in social networks. In this problem, a learner aims to identify the set of “best influencers” in a network by interacting with the network, i.e., repeatedly selecting seed nodes and observing activation feedback in the network. We capitalize on an important property of the influence maximization problem named network assortativity, which is ignored by most existing works in online influence maximization. To realize network assortativity, we factorize the activation probability on the edges into latent factors on the corresponding nodes, including influence factor on the giving nodes and susceptibility factor on the receiving nodes. We propose an upper confidence bound based online learning solution to estimate the latent factors, and therefore the activation probabilities. Considerable regret reduction is achieved by our factorization based online influence maximization algorithm. Extensive empirical evaluations on two real-world networks showed the effectiveness of our proposed solution.

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

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

U2 - 10.1145/3292500.3330874

DO - 10.1145/3292500.3330874

M3 - Conference contribution

AN - SCOPUS:85071166404

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

SP - 636

EP - 646

BT - KDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

PB - Association for Computing Machinery

T2 - 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019

Y2 - 4 August 2019 through 8 August 2019

ER -

Wu Q, Li Z, Wang H, Chen W, Wang H. Factorization bandits for online influence maximization. In KDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery. 2019. p. 636-646. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/3292500.3330874

Factorization bandits for online influence maximization

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this