Paper Info
Title
Sampling Content Distributed Over Graphs.
Abstract
Despite recent effort to estimate topology characteristics of large graphs (i.e., online social networks and peer-to-peer networks), little attention has been given to develop a formal methodology to characterize the vast amount of content distributed over these networks. Due to the large scale nature of these networks, exhaustive enumeration of this content is computationally prohibitive. In this paper, we show how one can obtain content properties by sampling only a small fraction of vertices. We first show that when sampling is naively applied, this can produce a huge bias in content statistics (i.e., average number of content duplications). To remove this bias, one may use maximum likelihood estimation to estimate content characteristics. However our experimental results show that one needs to sample most vertices in the graph to obtain accurate statistics using such a method. To address this challenge, we propose two efficient estimators: special copy estimator (SCE) and weighted copy estimator (WCE) to measure content characteristics using available information in sampled contents. SCE uses the special content copy indicator to compute the estimate, while WCE derives the estimate based on meta-information in sampled vertices. We perform experiments to show WCE and SCE are cost effective and also ``{\em asymptotically unbiased}''. Our methodology provides a new tool for researchers to efficiently query content distributed in large scale networks.
Year
Venue
Field
2013
CoRR
Data mining,Graph,Vertex (geometry),Computer science,Enumeration,Maximum likelihood,Artificial intelligence,Sampling (statistics),Machine learning,Estimator
DocType
Volume
Citations 
Journal
abs/1311.3882
2
PageRank 
References 
Authors
0.37
17
5
Name
Order
Citations
PageRank
Ping-Hui Wang123633.39
Junzhou Zhao210418.36
John C.S. Lui33680279.85
Don Towsley4186931951.05
X. Guan51169137.97