Two-hop walks indicate PageRank order. (November 2019)
- Record Type:
- Journal Article
- Title:
- Two-hop walks indicate PageRank order. (November 2019)
- Main Title:
- Two-hop walks indicate PageRank order
- Authors:
- Tang, Ying
- 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 forHighlights: 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. … (more)
- Is Part Of:
- Pattern recognition. Volume 95(2019:Nov.)
- Journal:
- Pattern recognition
- Issue:
- Volume 95(2019:Nov.)
- Issue Display:
- Volume 95 (2019)
- Year:
- 2019
- Volume:
- 95
- Issue Sort Value:
- 2019-0095-0000-0000
- 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 - Journal URLs:
- http://www.sciencedirect.com/science/journal/00313203 ↗
http://www.sciencedirect.com/ ↗ - DOI:
- 10.1016/j.patcog.2019.06.010 ↗
- Languages:
- English
- ISSNs:
- 0031-3203
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 11157.xml