The PageRank Citation Ranking: Bringing Order to the Web¶
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank Citation Ranking: Bringing Order to the Web: Bringing Order to the Web.
Cited by¶
5 citations across 5 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Eigenvalue And Eigenvector
- In network science, eigenvector centrality and PageRank read a node's importance from the dominant eigenvector of a link matrix, and spectral clustering uses subordinate eigenvectors to find communities.
This sourcePageRank is the dominant eigenvector (eigenvalue 1) of the link operator; power-iteration convergence is governed by the spectral gap, set via the damping factor.
- In network science, eigenvector centrality and PageRank read a node's importance from the dominant eigenvector of a link matrix, and spectral clustering uses subordinate eigenvectors to find communities.
- Network
- … / instructions → edges: BGP peering / network links / RPC calls / data-flow edges → directed edge: one-way channel / dataflow direction → weighted edge: bandwidth / latency / cost → degree: fan-in + fan-out / connection count → path: route / call chain → cluster: subnet / service mesh → centrality: hub / chokepoint
This sourceSeminal application of eigenvector centrality to web-graph ranking and hub identification.
- … / instructions → edges: BGP peering / network links / RPC calls / data-flow edges → directed edge: one-way channel / dataflow direction → weighted edge: bandwidth / latency / cost → degree: fan-in + fan-out / connection count → path: route / call chain → cluster: subnet / service mesh → centrality: hub / chokepoint
- Random Walk
- In computer science, randomized algorithms walk random paths through state spaces: Markov-chain Monte Carlo samples a target distribution by running a random walk whose stationary distribution is the target; PageRank ranks web pages by the long-run visiting frequency of a random surfer walking the hyperlink graph; random walks on graphs underlie clustering, sampling, and the analysis of randomized search.
This sourceRanks pages by the long-run visiting frequency of a random surfer walking the hyperlink graph — a random walk on a graph.
- In computer science, randomized algorithms walk random paths through state spaces: Markov-chain Monte Carlo samples a target distribution by running a random walk whose stationary distribution is the target; PageRank ranks web pages by the long-run visiting frequency of a random surfer walking the hyperlink graph; random walks on graphs underlie clustering, sampling, and the analysis of randomized search.
- Reputation
- Computer science & distributed systems: Reputation scores aggregate strangers' prior experiences so that parties with no shared history can transact — eBay feedback, web-of-trust key endorsement, and PageRank-style link authority all compute a standing from distributed observations, with PageRank treating an inbound hyperlink as a transferable endorsement of a page's authority, as Page, Brin, Motwani, and Winograd (1999) formalized.
This sourceStanford InfoLab. Formalizes an inbound hyperlink as a transferable endorsement of a page's authority, computing standing as a propagated stock from distributed link behavior.
- Computer science & distributed systems: Reputation scores aggregate strangers' prior experiences so that parties with no shared history can transact — eBay feedback, web-of-trust key endorsement, and PageRank-style link authority all compute a standing from distributed observations, with PageRank treating an inbound hyperlink as a transferable endorsement of a page's authority, as Page, Brin, Motwani, and Winograd (1999) formalized.
Domain-specific¶
- Matrix
- The importance of every page is then the dominant eigenvector of a damped version of this matrix: mixing \(M\) with a small chance of jumping to a page at random gives the Google matrix \(G = dM + \frac{1-d}{N}\mathbf{1}\mathbf{1}^\top\), and the ranking is the vector \(\pi\) satisfying \(G\pi=\pi\), the stationary distribution of that damped walk
This sourceThe report that gives PageRank its eigenvector and random-surfer formulation — 'we want the dominant eigenvector of A... computed by repeatedly applying A', with the ranking read as 'the limiting probability that the random walk will be at that node' — and that damps the recursion to escape rank sinks; it damps with a rank-source term, R' = c(AR' + E), rather than with the closed Google-matrix form, which belongs to the later literature.
- The importance of every page is then the dominant eigenvector of a damped version of this matrix: mixing \(M\) with a small chance of jumping to a page at random gives the Google matrix \(G = dM + \frac{1-d}{N}\mathbf{1}\mathbf{1}^\top\), and the ranking is the vector \(\pi\) satisfying \(G\pi=\pi\), the stationary distribution of that damped walk
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:f62c2fe70662 · see in the full table