Link Graph Encyclopedia

How links become rankings. PageRank, centrality, the structure of the web graph, and the domain metrics built on top of them.

Every link on the web is a small vote. One page or one site points at another. Collect billions of these votes and you get a link graph: a directed graph with a node for each site and an arc for each link. Search engines, crawlers and SEO tools all read importance off that graph, and they disagree in instructive ways. This encyclopedia explains how they do it, from the definitions to the arithmetic of running them over a hundred million domains, and what the resulting numbers do and do not tell you about a domain you might buy.

How to read an entry

Each entry is built in layers, so you can stop when you have what you need:

The idea. What the concept measures, in plain words.
The math. A precise definition, usually with a formula, and a worked example on the running example below.
At scale. How people compute it on the real web graph, and what it costs.
In practice. What the number means when you look at a domain’s metrics, and where it misleads.

Cross-references look like PageRank or harmonic centrality. Every entry lists the entries that link to it at the bottom, so you can walk the encyclopedia’s own link graph in both directions.

The running example

Most worked examples use the same seven sites and ten links. Sites A, B and C link to each other in a loop. D and E feed links into that loop, and nothing links to E. C links out to G, and E links out to F. F and G link nowhere.

The running example. A, B and C form the core; D and E point into it; G hangs off C; F hangs off E. Nobody links to E, and F and G have no outgoing links.

This small graph already shows most of the behaviour that matters at web scale: a strongly connected core, sources with no in-links, sinks with no out-links (dangling nodes), and a hub (E) that links to three sites. The lab below computes any measure in the encyclopedia live on it. Click one node and then another to add or remove a link, and watch the scores move.

Reading paths

If you buy or evaluate domains, start with backlinks, then reading domain metrics, Common Crawl web graph and metric audit. The vendor entries (Domain Authority, Domain Rating, Trust Flow, Authority Score) explain what each proprietary score claims to measure. Link spam and expired domains cover the ways those scores get gamed.

If you build ranking systems, read web graph, adjacency and random walks, then PageRank, power iteration and dangling nodes. WebGraph compression, HyperBall and PageRank at scale show how to run these measures over billions of links on one machine.

If you want the theory, read centrality and axioms for centrality, then compare harmonic centrality, closeness centrality, eigenvector centrality, Katz centrality and PageRank. Perron–Frobenius explains why a unique ranking exists at all, and Kendall’s tau and weighted tau measure how far two rankings disagree.

The data behind the examples

Real-world numbers come from Common Crawl’s domain-level graph cc-main-2026-jun-jul-aug: 119,722,885 domains and 2,450,405,793 links between them, with harmonic centrality and PageRank computed for every domain. The Common Crawl web graph entry describes the files. The metric audit uses one day of GoDaddy’s public auction inventory, 2026-09-23, which lists 1,068,241 domains alongside third-party link metrics.

Foundations

The web graph The directed graph with a node for every page, host or domain and an arc for every hyperlink between them.
Degree In-degree counts the links a node receives and out-degree the links it makes; their distributions shape everything built on a link graph.
Adjacency matrices and lists Two ways to write a graph down. The matrix suits the algebra behind every spectral ranking; compressed lists are how a real web graph fits in memory.
Paths, distance and reachability How many clicks separate two sites, and whether one can reach the other at all. Breadth-first search answers both, and geometric centralities are built on the answer.
Strongly connected components Groups of nodes that can all reach each other along links. They decide where a random surfer gets trapped and which nodes a spectral ranking can see.
The bow-tie structure Seen from its largest strongly connected component, the web looks like a bow tie. Pages that reach the core sit on one side, pages the core reaches sit on the other, and stragglers hang off both.
Degree distributions and power laws Most sites receive almost no links and a few receive millions. That heavy tail explains why link metrics live on logarithmic scales and why averages mislead.
Page, host and domain graphs The same links give three different graphs depending on whether a node is a URL, a host name or a registered domain. Each level answers different questions and hides different problems.
Reversed domain names and public suffixes Why web graphs write google.com as com.google, and how the Public Suffix List decides where a registrable domain begins.
Random walks and Markov chains A walker who follows random links visits some nodes more often than others. The long-run visit frequencies, the stationary distribution, are the mathematical core of PageRank and its relatives.

Centrality

Centrality A centrality measure assigns every node a score of importance computed from the graph's structure alone. Different measures formalise different ideas of importance, and they disagree.
Axioms for centrality Boldi and Vigna's three tests (size, density and score monotonicity) check whether a centrality measure agrees with intuition on graphs simple enough that the right answer is obvious. Only harmonic centrality passes all three.
Degree centrality Score each node by how many nodes link to it. The oldest, cheapest and most transparent centrality, and the one that "referring domains" reports.
Closeness centrality A node is central if it is close, on average, to all other nodes. A classic idea from social network analysis that breaks down on graphs where most pairs cannot reach each other, like the web.
Harmonic centrality Add up one over the distance from every other node. Nodes that the whole graph reaches in few steps score high, unreachable nodes simply count zero, and link farms gain almost nothing.
Betweenness centrality A node is central if many shortest paths between other nodes pass through it. Betweenness finds bridges and brokers, not popular destinations.
Eigenvector centrality A node's score is proportional to the sum of the scores of the nodes linking to it. The cleanest form of "important nodes are those linked by important nodes", and the parent of PageRank.
Katz centrality Count every walk that ends at a node, weighting a walk of length k by β to the power k. Short walks count most, everyone gets a baseline, and one parameter slides the measure from in-degree to eigenvector centrality.
PageRank A node is important if important nodes link to it. PageRank makes that circular idea precise as the long-run behaviour of a random surfer who sometimes gets bored and jumps.
Personalized PageRank PageRank with the random surfer's jumps aimed at chosen nodes instead of anywhere. It measures importance from a point of view, and underlies TrustRank, topic-sensitive search and local graph clustering.
HITS (hubs and authorities) Every node gets two scores. A good authority is linked by good hubs, and a good hub links to good authorities. Kleinberg's algorithm computes both from the links around a query's results.
SALSA A random-walk version of HITS that alternates forward and backward steps. Its authority scores turn out to be in-degree, normalised within each group of co-cited nodes, which makes them immune to topic drift.
TrustRank Pick a small set of sites a human has checked, and let trust flow outward from them along links, fading with each step. Spam sites, which reputable sites rarely link to, end up with little trust however many links they have.
Spam mass The share of a node's PageRank that does not come from known good nodes. A high-PageRank site whose rank comes mostly from outside the reputable web is a link-spam suspect.
CheiRank and 2DRank PageRank computed on the graph with every link reversed. It scores nodes by how well they link out to the rest of the graph, and paired with ordinary PageRank it places every node on a two-dimensional map.

PageRank in depth

The random surfer The story behind PageRank. A surfer clicks random links, never presses Back, and now and then jumps to a random page; the share of time spent on each page is its PageRank.
The damping factor The probability α that PageRank's random surfer follows a link rather than jumping. It trades link structure against uniformity, sets the speed of convergence, and is conventionally 0.85 for no deep reason.
Dangling nodes Nodes with no out-links, where a random surfer has nowhere to go. On a crawled web graph they are the majority, and how a PageRank implementation treats them changes the scores of everyone.
Power iteration Start from any distribution and apply one random-surfer step to all nodes at once, over and over. The error shrinks by a factor of about α per pass, and each pass reads every link exactly once.
The Perron–Frobenius theorem The theorem that guarantees a nonnegative matrix has a dominant eigenvector with positive entries. It is why PageRank exists, why it is unique, and why eigenvector centrality fails on graphs that are not strongly connected.
PageRank as a linear system PageRank is also the solution of a sparse system of linear equations. That view brings faster solvers such as Gauss–Seidel, explains why the problem is well conditioned, and makes PageRank linear in the teleport vector.
Monte Carlo PageRank Estimate PageRank by actually running random surfers and counting their visits. A few walks per node rank the important nodes well, the walks parallelise trivially, and they can be updated as links change.
Push algorithms Compute personalized PageRank by pushing probability outward from the seed, one node at a time, and stopping when the leftovers are small. The work depends on the precision you want, not on the size of the graph.
A short history of PageRank From a Stanford research project to Google's founding idea, a 0–10 number on millions of toolbars, a market in links, and finally a retired public metric that Google says it still uses internally.

Computing at scale

WebGraph compression How the WebGraph framework stores billions of links in a few bits each, using sorted gaps, copying from similar neighbours, runs of consecutive ids and codes tuned to power laws, while still decoding any node's links quickly.
Node orderings Renumbering a graph's nodes changes nothing about its structure and everything about its cost. Good orders shrink compressed graphs, speed up PageRank through cache locality and balance parallel work.
HyperLogLog A counter that estimates how many distinct items it has seen, within a few percent, using a few bytes. Its counters merge by taking maxima, which is what lets HyperBall count reachable nodes for a hundred million nodes at once.
HyperBall Grow a probabilistic counter around every node by one link per pass over the graph. After a few dozen passes you know, for every node, roughly how many nodes lie within each distance, and with it harmonic centrality, closeness and the distance distribution.
Brandes' algorithm Exact betweenness centrality for every node in O(nm) time. One breadth-first search per source counts shortest paths, and one backward sweep hands each node its share.
PageRank at scale The arithmetic of ranking a hundred million nodes and billions of links. What must fit in memory, what each pass costs, why random reads dominate, and why one well-programmed machine often beats a cluster.

Comparing rankings

Ranks and scores A centrality gives each node a value; a ranking gives it a position. Positions are easy to read and easy to misread. How values are distributed, how ties are broken and how precise the values are decide what a position means.
Kendall's tau Compare two rankings by counting pairs of items they order the same way and pairs they order oppositely. The standard measure of agreement between centralities, computable in O(n log n) time.
Spearman's rho The ordinary correlation coefficient computed on positions instead of values. Easy to compute and explain, robust to skewed scores, and like Kendall's tau blind to whether disagreements happen at the top or in the tail.
Weighted tau Kendall's tau with each pair weighted by how high its items rank, so disagreements at the top count more than disagreements in the tail. Designed by Sebastiano Vigna for comparing web-scale rankings with many ties.
Rank-biased overlap Compare two rankings by how much their top lists overlap at every depth, with geometrically decreasing weight on deeper levels. Works on truncated lists and on lists that do not contain the same items.

Network structure

Clustering coefficient How often two neighbours of a node are also neighbours of each other. Real networks form far more triangles than chance predicts, and unnaturally dense triangles are a classic fingerprint of link farms.
Small worlds Real networks combine dense local clusters with surprisingly short paths between any two nodes. That combination explains why "six degrees of separation" holds, why harmonic values crowd together and why links travel far.
The neighbourhood function For each distance t, how many pairs of nodes are within t links of each other. From it come the distance distribution, the average distance and the effective diameter, the robust ways to say how "small" a graph is.
Community detection Finding groups of nodes that link to each other much more than to the rest of the graph. Modularity, Louvain, Leiden, label propagation and Infomap are the standard tools; on the web they find topics, regions and link farms.
k-core decomposition Repeatedly peel off every node with fewer than k links until none is left. The layer at which a node falls off, its core number, measures how deeply it is embedded in a dense part of the graph, in linear time.
Assortativity Whether well-connected nodes link to other well-connected nodes. Social networks tend to be assortative; the web, where hubs collect links from countless small sites, tends to be disassortative.
Reciprocity The share of links that are returned. In Common Crawl's 2026 domain graph about one link in eight has a link back, hundreds of thousands of times more than chance, from sites under common ownership, communities that cite each other and link exchanges.
Random graph models Recipes for generating graphs at random, from uniform random links to preferential attachment and copying. They explain where web structure comes from, serve as null models for measurements, and provide test graphs for algorithms.

Links in practice

Backlinks and referring domains A backlink is a link from someone else's page to yours; referring domains count the distinct sites those links come from. Both are in-degree at different granularities, and both depend entirely on whose crawl counted them.
Link attributes (nofollow, sponsored, ugc) The rel values that let a publisher say a link is not an endorsement. Introduced in 2005 against comment spam, extended in 2019, and since then treated by Google as hints rather than commands.
Anchor text The clickable words of a link. Search engines have used them since 1998 to learn what the target is about, which made them a prime target for manipulation and makes them the quickest way to read a domain's past.
Redirects and canonicalisation How 301s, 302s and canonical tags move link signals from one URL to another. They decide where a moved site's links end up, and they are the main mechanism by which an expired domain's links are put to new use.
Link spam Links created to manipulate rankings rather than to help readers. Link farms, bought links, private blog networks and parasite pages, what each does to PageRank and harmonic centrality, and the traces they leave in a link graph.
Link penalties and the disavow tool How Google acts on manipulative links, from the 2012 Penguin update and manual actions to today's practice of silently ignoring spam links, and what the disavow tool does.
Expired domains Domains whose owners let the registration lapse, sold at auction or re-registered by someone else. Their links often outlive their sites, which is why buyers value them and why search engines watch how they are reused.

Domain metrics

The Common Crawl web graph Common Crawl publishes free host- and domain-level link graphs every few months, with harmonic centrality and PageRank for every node. What the files contain, how they are built, and how to read them.
Reading a domain's link metrics A practical guide for buyers. Which numbers to look at, what thresholds mean on real data, how to tell real link standing from noise, and two worked examples from the 2026-09-23 auction inventory.
Domain Authority (Moz) Moz's 1–100 score that predicts how likely a domain is to rank in search results, computed by a machine-learning model over Moz's own link index. A comparative, logarithmic-feeling number, not a Google metric.
Domain Rating (Ahrefs) Ahrefs' 0–100 score for the strength of a domain's backlink profile. By Ahrefs' own description it is a PageRank-like computation on a domain graph of followed links, mapped to a logarithmic scale.
Trust Flow and Citation Flow (Majestic) Majestic's two 0–100 scores. Citation Flow measures link volume and power; Trust Flow measures closeness in the link graph to manually reviewed trusted sites, a TrustRank-style idea. Their ratio is a popular spam heuristic.
Authority Score (Semrush) Semrush's compound 100-point score combining link power, estimated organic traffic and spam signals. Designed to resist manipulation, and in the 2026-09-23 auction data almost constant.
Auditing vendor metrics Checking Semrush and Majestic numbers from one day of GoDaddy's auction inventory against Common Crawl's open graph. A referring-domain floor made of the same few domains, a Majestic feed that is mostly empty, and a nearly constant Authority Score.

Most central entries

PageRank (α = 0.85) over this site's own cross-references, recomputed on every build: an entry ranks high when central entries link to it.