Provided is a reject rate-controllable Metropolis-Hastings graph sampling algorithm. The algorithm comprises: firstly, moving about on a graph randomly to collect samples; and secondly, constructing unbiased estimation according to the collected samples.The method can effectively solve the problem of extracting a uniform sample from a 'concealed' on-line social network, well balances the 'large deviation' problem of RW algorithm and the 'sample rejection' problem of MH algorithm, and is widely applicable to the technical field of social network analysis, graph data management, map data excavation and the like.
展开▼
