Title: Characterizing Directed and Undirected Networks via Multidimensional Walks with Jumps,
Abstract: Estimating distributions of node characteristics (labels) such as number of
connections or citizenship of users in a social network via edge and node
sampling is a vital part of the study of complex networks. Due to its low cost,
sampling via a random walk (RW) has been proposed as an attractive solution to
this task. Most RW methods assume either that the network is undirected or that
walkers can traverse edges regardless of their direction. Some RW methods have
been designed for directed networks where edges coming into a node are not
directly observable. In this work, we propose Directed Unbiased Frontier
Sampling (DUFS), a sampling method based on a large number of coordinated
walkers, each starting from a node chosen uniformly at random. It is applicable
to directed networks with invisible incoming edges because it constructs, in
real-time, an undirected graph consistent with the walkers trajectories, and
due to the use of random jumps which prevent walkers from being trapped. DUFS
generalizes previous RW methods and is suited for undirected networks and to
directed networks regardless of in-edges visibility. We also propose an
improved estimator of node label distributions that combines information from
the initial walker locations with subsequent RW observations. We evaluate DUFS,
compare it to other RW methods, investigate the impact of its parameters on
estimation accuracy and provide practical guidelines for choosing them. In
estimating out-degree distributions, DUFS yields significantly better estimates
of the head of the distribution than other methods, while matching or exceeding
estimation accuracy of the tail. Last, we show that DUFS outperforms uniform
node sampling when estimating distributions of node labels of the top 10%
largest degree nodes, even when sampling a node uniformly has the same cost as
RW steps.