
For FullText 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
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E101D
No.2
pp.535538 Publication Date: 2018/02/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2017EDL8179
Type of Manuscript: LETTER Category: Fundamentals of Information Systems Keyword: weighted graph sampling, graph mining, graph scale,
Full Text: PDF(258.4KB) >>Buy this Article
Summary:
Graph sampling is an effective method to sample a representative subgraph from a largescale 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.

