A Measurement Framework for Directed Networks

TitleA Measurement Framework for Directed Networks
Publication TypeJournal Article
Year of Publication2013
AuthorsSalehi, M., and H. R. Rabiee
JournalIEEE JSAC Special Issue on Network Science
Start Page1007
Date Published06/2013
KeywordsDirected Networks, Estimation, Importance Sampling, Link-tracing
AbstractPartially-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 (e.g., the number of copies of a file in a peer-to-peer 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. To the best of our knowledge, this is the first study to introduce a complete measurement framework for directed networks. Comprehensive theoretical and empirical analysis of the estimator demonstrates that it is nearly unbiased (the bias diminishes to 0 as the number of samples increases) even in situations where stationary distribution of PageRank is poorly approximated.
URL<a href="/dmlsite/?q=%3Ca%20href%3D%22/dmlsite/%3Fq%3D%253Ca%2520href%253D%2522/dmlsite/%253Fq%253D%25253Ca%252520href%25253D%252522/dmlsite/%25253Fq%25253D%2525253Ca%25252520href%2525253D%25252522/dmlsite/%2525253Fq%2525253D%252525253Ca%2525252520href%25
DOI<a href="http://dx.doi.org/10.1109/JSAC.2013.130603&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp