Online Influence Maximization with Local Observations

Gábor Lugosi, Gergely Neu, Julia Olkhovskaya
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:557-580, 2019.

Abstract

We consider an online influence maximization problem in which a decision maker selects a node among a large number of possibilities and places a piece of information at the node. The information then spreads in the network on a random set of edges. The goal of the decision maker is to reach as many nodes as possible, with the added complication that feedback is only available about the degree of the selected node. Our main result shows that such local observations can be sufficient for maximizing global influence in two broadly studied families of random graph models: stochastic block models and Chung–Lu models. With this insight, we propose a bandit algorithm that aims at maximizing local (and thus global) influence, and provide its theoretical analysis in both the subcritical and supercritical regimes of both considered models. Notably, our performance guarantees show no explicit dependence on the total number of nodes in the network, making our approach well-suited for large-scale applications.

Cite this Paper

BibTeX
@InProceedings{pmlr-v98-lugosi19a, title = {Online Influence Maximization with Local Observations}, author = {Lugosi, G\'abor and Neu, Gergely and Olkhovskaya, Julia}, booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory}, pages = {557--580}, year = {2019}, editor = {Garivier, Aurélien and Kale, Satyen}, volume = {98}, series = {Proceedings of Machine Learning Research}, month = {22--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v98/lugosi19a/lugosi19a.pdf}, url = {https://proceedings.mlr.press/v98/lugosi19a.html}, abstract = {We consider an online influence maximization problem in which a decision maker selects a node among a large number of possibilities and places a piece of information at the node. The information then spreads in the network on a random set of edges. The goal of the decision maker is to reach as many nodes as possible, with the added complication that feedback is only available about the degree of the selected node. Our main result shows that such local observations can be sufficient for maximizing global influence in two broadly studied families of random graph models: stochastic block models and Chung–Lu models. With this insight, we propose a bandit algorithm that aims at maximizing local (and thus global) influence, and provide its theoretical analysis in both the subcritical and supercritical regimes of both considered models. Notably, our performance guarantees show no explicit dependence on the total number of nodes in the network, making our approach well-suited for large-scale applications.} }
Endnote
%0 Conference Paper %T Online Influence Maximization with Local Observations %A Gábor Lugosi %A Gergely Neu %A Julia Olkhovskaya %B Proceedings of the 30th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Aurélien Garivier %E Satyen Kale %F pmlr-v98-lugosi19a %I PMLR %P 557--580 %U https://proceedings.mlr.press/v98/lugosi19a.html %V 98 %X We consider an online influence maximization problem in which a decision maker selects a node among a large number of possibilities and places a piece of information at the node. The information then spreads in the network on a random set of edges. The goal of the decision maker is to reach as many nodes as possible, with the added complication that feedback is only available about the degree of the selected node. Our main result shows that such local observations can be sufficient for maximizing global influence in two broadly studied families of random graph models: stochastic block models and Chung–Lu models. With this insight, we propose a bandit algorithm that aims at maximizing local (and thus global) influence, and provide its theoretical analysis in both the subcritical and supercritical regimes of both considered models. Notably, our performance guarantees show no explicit dependence on the total number of nodes in the network, making our approach well-suited for large-scale applications.
APA
Lugosi, G., Neu, G. & Olkhovskaya, J.. (2019). Online Influence Maximization with Local Observations. Proceedings of the 30th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 98:557-580 Available from https://proceedings.mlr.press/v98/lugosi19a.html.

Related Material