How can we predict Smith's main hobby if we know the main hobby of Smith's friends? Can we measure the confidence in our predic- tion if we are given the main hobby of only a few of Smith's friends? In this paper, we focus on how to estimate the confidence on the node classi- fication problem. Providing a confidence level for the classification prob- lem is important because most nodes in real world networks tend to have few neighbors, and thus, a small amount of evidence. Our contributions are three-fold: (a) novel algorithm; we propose a semi-supervised learning algorithm that converges fast, and provides the confidence estimate (b) theoretical analysis; we show the solid theoretical foundation of our algo- rithm and the connections to label propagation and Bayesian inference (c) empirical analysis; we perform extensive experiments on three dif- ferent real networks. Specifically, the experimental results demonstrate that our algorithm outperforms other algorithms on graphs with less smoothness and low label density.
['Yuto Yamaguchi', 'Christos Faloutsos', 'Hiroyuki Kitagawa']
SocNL: Bayesian Label Propagation with Confidence