  Partially-observed network data collected by link-tracing based sampling
methods is often being studied to obtain the characteristics of a large complex
network. However, little attention has been paid to sampling from directed
networks such as WWW and Peer-to-Peer networks. In this paper, we propose a
novel two-step (sampling/estimation) framework to measure nodal characteristics
which can be defined by an average target function in an arbitrary directed
network. To this end, we propose a personalized PageRank-based algorithm to
visit and sample nodes. This algorithm only uses already visited nodes as local
information without any prior knowledge about the latent structure of the
network. Moreover, we introduce a new estimator based on the approximate
importance sampling to estimate average target functions. The proposed
estimator utilizes calculated PageRank value of each sampled node as an
approximation for the exact visiting probability. To the best of our knowledge,
this is the first study on correcting the bias of a sampling method by
re-weighting of measured values that considers the effect of approximation of
visiting probabilities. Comprehensive theoretical and empirical analysis of the
estimator demonstrate that it is asymptotically unbiased even in situations
where stationary distribution of PageRank is poorly approximated.
