Consideration of a Method Using Degree-Biased Random Walk to Estimate Important Eigenvalues of Graph Matrices
摘要
Important eigenvalues of graph matrices such as adjacency matrices, Laplacian matrices, and walk matrices have been utilized in the design and analysis of various graph algorithms. Generally, in order to calculate these eigenvalues, it is necessary to collect the complete information from the entire graph and explicitly construct the graph matrices. For large-scale graphs with high confidentiality such as social networks, collecting complete information is prohibitively costly. Therefore, in the previous study, cWalker has been proposed to estimate important eigenvalues by observing only a subset of nodes have been proposed. Through the evaluation, cWalker has been successful in estimating the eigenvalues of the adjacency matrix from partial information of the graph using node sampling with a simple random walk. In this paper, we discuss an extension of cWalker, named cWalker+ to estimate important eigenvalues of graph matrices including adjacency matrix and walk matrix. We design cWalker+ using a degree-biased random walk, and confirm the effectiveness of cWalker+ in estimating the important eigenvalue of the walk matrix for real social networks.