Predictive Simulation Framework of Stochastic Diffusion Model for Identifying Top-K Influential Nodes

Kouzou Ohara, Kazumi Saito, Masahiro Kimura, Hiroshi Motoda
Proceedings of the 5th Asian Conference on Machine Learning, PMLR 29:149-164, 2013.

Abstract

We address a problem of efficiently estimating the influence of a node in information diffusion over a social network. Since the information diffusion is a stochastic process, the influence degree of a node is quantified by the expectation, which is usually obtained by very time consuming many runs of simulation. Our contribution is that we proposed a framework for predictive simulation based on the leave-N-out cross validation technique that well approximates the error from the unknown ground truth for two target problems: one to estimate the influence degree of each node, and the other to identify top-K influential nodes. The method we proposed for the first problem estimates the approximation error of the influence degree of each node, and the method for the second problem estimates the precision of the derived top-K nodes, both without knowing the true influence degree. We experimentally evaluate the proposed methods using the three real world networks, and show that they can serve as a good measure to solve the target problems with far fewer runs of simulation ensuring the accuracy if N is appropriately chosen, and that estimating the top-K nodes is easier than estimating the influence degree, which means one can identify the influential nodes without knowing exactly their influence degree.

Cite this Paper

BibTeX
@InProceedings{pmlr-v29-Ohara13, title = {Predictive Simulation Framework of Stochastic Diffusion Model for Identifying Top-K Influential Nodes}, author = {Ohara, Kouzou and Saito, Kazumi and Kimura, Masahiro and Motoda, Hiroshi}, booktitle = {Proceedings of the 5th Asian Conference on Machine Learning}, pages = {149--164}, year = {2013}, editor = {Ong, Cheng Soon and Ho, Tu Bao}, volume = {29}, series = {Proceedings of Machine Learning Research}, address = {Australian National University, Canberra, Australia}, month = {13--15 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v29/Ohara13.pdf}, url = {https://proceedings.mlr.press/v29/Ohara13.html}, abstract = {We address a problem of efficiently estimating the influence of a node in information diffusion over a social network. Since the information diffusion is a stochastic process, the influence degree of a node is quantified by the expectation, which is usually obtained by very time consuming many runs of simulation. Our contribution is that we proposed a framework for predictive simulation based on the leave-N-out cross validation technique that well approximates the error from the unknown ground truth for two target problems: one to estimate the influence degree of each node, and the other to identify top-K influential nodes. The method we proposed for the first problem estimates the approximation error of the influence degree of each node, and the method for the second problem estimates the precision of the derived top-K nodes, both without knowing the true influence degree. We experimentally evaluate the proposed methods using the three real world networks, and show that they can serve as a good measure to solve the target problems with far fewer runs of simulation ensuring the accuracy if N is appropriately chosen, and that estimating the top-K nodes is easier than estimating the influence degree, which means one can identify the influential nodes without knowing exactly their influence degree. } }
Endnote
%0 Conference Paper %T Predictive Simulation Framework of Stochastic Diffusion Model for Identifying Top-K Influential Nodes %A Kouzou Ohara %A Kazumi Saito %A Masahiro Kimura %A Hiroshi Motoda %B Proceedings of the 5th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Cheng Soon Ong %E Tu Bao Ho %F pmlr-v29-Ohara13 %I PMLR %P 149--164 %U https://proceedings.mlr.press/v29/Ohara13.html %V 29 %X We address a problem of efficiently estimating the influence of a node in information diffusion over a social network. Since the information diffusion is a stochastic process, the influence degree of a node is quantified by the expectation, which is usually obtained by very time consuming many runs of simulation. Our contribution is that we proposed a framework for predictive simulation based on the leave-N-out cross validation technique that well approximates the error from the unknown ground truth for two target problems: one to estimate the influence degree of each node, and the other to identify top-K influential nodes. The method we proposed for the first problem estimates the approximation error of the influence degree of each node, and the method for the second problem estimates the precision of the derived top-K nodes, both without knowing the true influence degree. We experimentally evaluate the proposed methods using the three real world networks, and show that they can serve as a good measure to solve the target problems with far fewer runs of simulation ensuring the accuracy if N is appropriately chosen, and that estimating the top-K nodes is easier than estimating the influence degree, which means one can identify the influential nodes without knowing exactly their influence degree.
RIS
TY - CPAPER TI - Predictive Simulation Framework of Stochastic Diffusion Model for Identifying Top-K Influential Nodes AU - Kouzou Ohara AU - Kazumi Saito AU - Masahiro Kimura AU - Hiroshi Motoda BT - Proceedings of the 5th Asian Conference on Machine Learning DA - 2013/10/21 ED - Cheng Soon Ong ED - Tu Bao Ho ID - pmlr-v29-Ohara13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 29 SP - 149 EP - 164 L1 - http://proceedings.mlr.press/v29/Ohara13.pdf UR - https://proceedings.mlr.press/v29/Ohara13.html AB - We address a problem of efficiently estimating the influence of a node in information diffusion over a social network. Since the information diffusion is a stochastic process, the influence degree of a node is quantified by the expectation, which is usually obtained by very time consuming many runs of simulation. Our contribution is that we proposed a framework for predictive simulation based on the leave-N-out cross validation technique that well approximates the error from the unknown ground truth for two target problems: one to estimate the influence degree of each node, and the other to identify top-K influential nodes. The method we proposed for the first problem estimates the approximation error of the influence degree of each node, and the method for the second problem estimates the precision of the derived top-K nodes, both without knowing the true influence degree. We experimentally evaluate the proposed methods using the three real world networks, and show that they can serve as a good measure to solve the target problems with far fewer runs of simulation ensuring the accuracy if N is appropriately chosen, and that estimating the top-K nodes is easier than estimating the influence degree, which means one can identify the influential nodes without knowing exactly their influence degree. ER -
APA
Ohara, K., Saito, K., Kimura, M. & Motoda, H.. (2013). Predictive Simulation Framework of Stochastic Diffusion Model for Identifying Top-K Influential Nodes. Proceedings of the 5th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 29:149-164 Available from https://proceedings.mlr.press/v29/Ohara13.html.

Related Material