Home >

news Help

Publication Information


Title
Japanese: 
English:A multi-armed bandit approach for exploring partially observed networks 
Author
Japanese: Madhawa Kaushalya Pituwala kankanamge, 村田剛志.  
English: Kaushalya Madhawa, Tsuyoshi MURATA.  
Language English 
Journal/Book name
Japanese: 
English:Applied Network Science 
Volume, Number, Page Vol. 6    No. 26    pp. 1-18
Published date May 31, 2019 
Publisher
Japanese: 
English:Springer 
Conference name
Japanese: 
English: 
Conference site
Japanese: 
English: 
Official URL https://appliednetsci.springeropen.com/articles/10.1007/s41109-019-0145-0
 
DOI https://doi.org/10.1007/s41109-019-0145-0
Abstract Real-world networks such as social and communication networks are too large to be observed entirely. Such networks are often partially observed such that network size, network topology, and nodes of the original network are unknown. Analysis on partially observed data may lead to incorrect conclusions. We assume that we are given an incomplete snapshot of a large network and additional nodes can be discovered by querying nodes in the currently observed network. The goal of this problem is to maximize the number of observed nodes within a given query budget. Querying which set of nodes maximizes the size of the observed network? We formulate this problem as an exploration-exploitation problem and propose a novel nonparametric multi-armed bandit (MAB) algorithm for identifying which nodes to be queried. Our proposed nonparametric multi-armed bandit algorithm outperforms existing state-of-the-art algorithms by discovering over 40% more nodes in synthetic and real-world networks. Moreover, we provide theoretical guarantee that the proposed algorithm has sublinear regret. Our results demonstrate that multi-armed bandit based algorithms are well suited for exploring partially observed networks compared to heuristic based algorithms.

©2007 Tokyo Institute of Technology All rights reserved.