Two-hop walks indicate PageRank order. (November 2019)

• Record Type: Journal Article
• Authors: Tang, Ying
• Is Part Of: Pattern recognition. Volume 95(2019:Nov.)
• Page Start: 201
• Page End: 210
• Publication Date: 2019-11
• Subjects: Spectral ranking -- PageRank -- Two-Hop; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2019.06.010
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: This paper opens a new door for studying PageRank based on the spectral distribution law of random matrices. We provide a method for pairwise comparisons in PageRank in O (1) without computing the exact value of the principle eigenvectors of Google matrices from a probabilistic view. We provide a method for extracting the top k list in O ( kn ), where n is the total number of involved items Abstract: This paper shows that pairwise PageRank orders emerge from two-hop walks. The main tool used here refers to a specially designed sign-mirror function and a parameter curve, whose low-order derivative information implies pairwise PageRank orders with high probability. We study the pairwise correct rate by placing the Google matrix G in a probabilistic framework, where G may be equipped with different random ensembles for model-generated or real-world networks with sparse, small-world, scale-free features, the proof of which is mixed by mathematical and numerical evidence. We believe that the underlying spectral distribution of aforementioned networks is responsible for the high pairwise correct rate. Moreover, the perspective of this paper naturally leads to an O (1) algorithm for any single pairwise PageRank comparison if assuming both A = G − I n, where I n denotes the identity matrix of order n, and A 2 are ready on hand (e.g., constructed offline in an incremental manner), based on which it is easy to extract the top k list in O ( kn ), thus making it possible for PageRank algorithm to deal with super large-scale datasets in real time.