Home >

news Help

Publication Information


Title
Japanese: 
English:Exploring Partially Observed Networks with Nonparametric Bandits 
Author
Japanese: Madhawa Kaushalya Pituwala kankanamge, 村田剛志.  
English: Kaushalya Madhawa, Tsuyoshi MURATA.  
Language English 
Journal/Book name
Japanese: 
English:Proceedings of the 7th International Conference on Complex Networks and Their Applications (Complex Networks 2018) 
Volume, Number, Page Vol. 2        pp. 158-168
Published date Dec. 11, 2018 
Publisher
Japanese: 
English:Springer 
Conference name
Japanese: 
English:7th International Conference on Complex Networks and Their Applications (Complex Networks 2018) 
Conference site
Japanese: 
English:Cambridge 
Official URL https://link.springer.com/chapter/10.1007%2F978-3-030-05414-4_13
 
DOI https://doi.org/10.1007/978-3-030-05414-4_13
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. In this paper we formalize the Adaptive Graph Exploring problem. 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 iKNN-UCB, a novel nonparametric multi-arm bandit (MAB) algorithm for determining which nodes to be queried in an adaptive manner. Using synthetic networks and real-world networks from different domains, we demonstrate that our proposed algorithm discovers up to 40% more nodes compared to existing state-of-the-art algorithms.

©2007 Tokyo Institute of Technology All rights reserved.