Title: Towards Optimal Strategy for Adaptive Probing in Incomplete Networks,
Abstract: We investigate a graph probing problem in which an agent has only an
incomplete view $G' \subsetneq G$ of the network and wishes to explore the
network with least effort. In each step, the agent selects a node $u$ in $G'$
to probe. After probing $u$, the agent gains the information about $u$ and its
neighbors. All the neighbors of $u$ become \emph{observed} and are
\emph{probable} in the subsequent steps (if they have not been probed). What is
the best probing strategy to maximize the number of nodes explored in $k$
probes? This problem serves as a fundamental component for other
decision-making problems in incomplete networks such as information harvesting
in social networks, network crawling, network security, and viral marketing
with incomplete information.
While there are a few methods proposed for the problem, none can perform
consistently well across different network types. In this paper, we establish a
strong (in)approximability for the problem, proving that no algorithm can
guarantees finite approximation ratio unless P=NP. On the bright side, we
design learning frameworks to capture the best probing strategies for
individual network. Our extensive experiments suggest that our framework can
learn efficient probing strategies that \emph{consistently} outperform previous
heuristics and metric-based approaches.