For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Random Walk Based Weighted Graph Sampling
Jiajun ZHOU Bo LIU Lu DENG Yaofeng CHEN Zhefeng XIAO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2018/02/01
Online ISSN: 1745-1361
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.