Another centrality measure
centrality measure for nodes in directed networksprestige, or Web pagesSource: DOI:10.1017/97811086539471


PageRank was designed to fix the flaws of Eigencentrality in directed graphs (specifically “sinks” where influence gets trapped).
Recursive Logic: A node is important if it is linked to by other important nodes.
The Random Surfer: Models a user clicking links.
Clicking: With probability \(d\), the user follows a random link on the current page.
Teleporting: With probability \(1-d\), the user gets bored and jumps to a completely random page in the network.
Key Innovation: Unlike standard Eigencentrality, PageRank dilutes influence. If a page has many outgoing links, it passes less “authority” to each one.
The score for node \(i\) is defined as:
\[PR(i) = \frac{1-d}{N} + d \sum_{j \in In(i)} \frac{PR(j)}{L(j)}\]
Definitions of Quantities:
Note that structurally the equation is similar to Katz centrality.
| Katz | PageRank | |
|---|---|---|
| Baseline term | Constant \(\beta\) added to every node | Teleport \(\tfrac{1-d}{N}\) to a random node |
| How score passes along an edge | Full score sent down every out-link | Score divided by out-degree \(L(j)\) |
| Tuning knob | Attenuation \(\alpha\), must stay below \(1/\lambda_{max}\) | Damping \(d\), fixed near \(0.85\), always valid |
| Interpretation | Discounted count of incoming walks | Long-run share of a random surfer’s time |
| Convergence | Needs \(\alpha < 1/\lambda_{max}\) | Guaranteed for any \(d < 1\) |
The one difference that matters: out-degree normalization. In Katz, a node passes its full score along every outgoing edge, so a page that links to a thousand others is a thousand times as influential as one that links to a single page. PageRank divides by \(L(j)\) first, so each node has a fixed budget of influence to share, and a link from a selective page counts for more than a link from a spammy link-farm.
Why PageRank is easier to run. Dividing by out-degree turns the link matrix into a stochastic (column-sums-to-one) matrix, whose largest eigenvalue is exactly \(1\). That is why the damping factor can be any \(d < 1\) and always converges, while Katz must keep \(\alpha\) below the graph-dependent threshold \(1/\lambda_{max}\).
Bottom line: Katz is the natural choice when raw incoming volume should count; PageRank is the choice when influence should be a shared, conserved quantity, which is exactly what made it robust to web spam.
To solve for the entire network vector \(\mathbf{r}\), we define the Google Matrix:
\[\mathbf{r} = \left( \frac{1-d}{N} \mathbf{E} + d \mathbf{M} \right) \mathbf{r}\]
Since web-scale matrices are too large for direct inversion (\(O(N^3)\)), we use an iterative approach (\(O(m \cdot i)\)).
Algorithm: Power Iteration for PageRank
Input: Adjacency Matrix A, damping factor d, tolerance epsilon
Output: PageRank Vector r
1. Initialize r = [1/N, 1/N, ..., 1/N]
2. while (change > epsilon):
3. r_new = [(1-d) / N] * ones_vector
4. for each node j:
5. if L(j) > 0:
6. for each neighbor i that j points to:
7. r_new[i] += d * (r[j] / L(j))
8. else: // Handle sinks (nodes with no out-links)
9. r_new += d * (r[j] / N)
10. change = ||r_new - r||
11. r = r_new
12. return rGraph Structure:
Initial Parameters:
Iteration 1 Calculation:
Observation: \(C\) becomes the most important because it pools the influence of \(B\) and half of \(A\). The scores will converge after a few more iterations.
Source: DOI:10.1017/97811086539471

Source: DOI:10.1017/97811086539471

How Google Search Works?
Imagine a tiny web of just three pages, each linking to a couple of others. Here is the whole search engine, stripped to its bones:
1. Crawl (go find the pages). Start at one page, follow its links to the next, and keep going until you have visited them all. Now you have a copy of every page.
2. Index (make a word list). For each page, jot down which words it contains, then flip it around into a lookup table: "cat" -> [page 1, page 3], "dog" -> [page 2]. This is the part that lets you find pages instantly instead of re-reading the web every time.
3. Rank (decide who is important). Count the links pointing at each page, and let important pages pass on their importance, the PageRank idea in one line. A page that many good pages link to floats to the top.
4. Search (answer the query). A user types “cat.” Look up “cat” in the word list to get pages 1 and 3, then order them by their importance score and show the better one first.
That is Google in miniature: find the pages, list their words, score their importance, and at query time match the words and sort by score. Everything real Google adds (freshness, spam-fighting, language understanding, personalization) is refinement layered on top of these four moves.
PageRank is still used but is not the sole factor in search rankings.
PageRank remains a component but within a sophisticated, multifaceted ranking system.
Evolution of PageRank:
Other Ranking Factors:
Algorithm Updates: