An Error Correction Algorithm for Random Walk Sampling in Social Networks
WANG Yongqiang
DONG Yunquan
Abstract：How to estimate the number of users in online social networks efficiently and accurately is a fundamental problem in the field of network science.The random walk sampling based estimation algorithms estimates the number of users of social net-work by randomly visiting some of the network users and counting the number of repeated visits of each user.However,the relative errors of current estimation algorithms would be quite large.In this paper,it is found that the main reason for the large relative error in the estimation results is the"false collision"caused by low degree nodes in the network.Therefore,this study proposes an error correction algorithm for collision counting based random walk sampling to improve the accuracy of the user number estimation of so-cial networks.Specifically,it corrects the collision error generated by"false collision"caused by low degree nodes.The experimen-tal verification on real social network data sets show that,compared with the traditional random walk-based sampling estimation al-gorithms,the proposed error correction algorithm can effectively reduce the relative error of the estimation.
Keywords：social networksestimation errorrandom walk samplingerror correction
Publication Date：2025-11-20
Online Publishing Date：2026-01-28(First online date of this platform, not the publication date of the document)
Pages：7( 2995-3000,3012 )