On Random Walk Based Weighted Graph Sampling

Jiajun ZHOU  Bo LIU  Lu DENG  Yaofeng CHEN  Zhefeng XIAO  

IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.2   pp.535-538
Publication Date: 2018/02/01
Publicized: 2017/11/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017EDL8179
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
weighted graph sampling,  graph mining,  graph scale,  

Full Text: PDF(258.4KB)>>
Buy this Article

 | Errata[Uploaded on July 1,2018]

Graph sampling is an effective method to sample a representative subgraph from a large-scale network. Recently, researches have proven that several classical sampling methods are able to produce graph samples but do not well match the distribution of the graph properties in the original graph. On the other hand, the validation of these sampling methods and the scale of a good graph sample have not been examined on weighted graphs. In this paper, we propose the weighted graph sampling problem. We consider the proper size of a good graph sample, propose novel methods to verify the effectiveness of sampling and test several algorithms on real datasets. Most notably, we get new practical results, shedding a new insight on weighted graph sampling. We find weighted random walk performs best compared with other algorithms and a graph sample of 20% is enough for weighted graph sampling.