Predictive Simulation Framework of Stochastic Diffusion Model for Identifying TopK Influential Nodes

5th Asian Conference on Machine Learning

数学科学;计算机科学

Kouzou Ohara [e-mail] ; School of Administration and Informatics, University of Shizuoka ; Department of Electronics and Informatics, Ryukoku University ; Institute of Scientific and Industrial Research ; Osaka University

PID  :  123073

来源: CEUR

【 摘 要 】

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 leaveNout 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 topK 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 prob lem estimates the precision of the derived topK 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 topK nodes is easier than estimating the influence degree, which means one can identify the influential nodes without knowing exactly their influence degree.