Math in… Web Search
While search engines are increasingly trending toward native advertisements and AI digests, the actual lists of sites they present after the fluff still tend to be roughly what you’re looking for, with the most relevant results often listed first. How do they do it?
When searching the web, we want a search engine that can thoughtfully order sites so we don’t have to spend our time picking through them to find something interesting or useful. What makes a site interesting or useful, though? If we’re looking for a good site on tree octopuses, for example, the words “tree” and “octopus” should probably appear somewhere on the site, but it’s tricky to say what else it needs.
On the other hand, when a friend sends you a link, they’ve already looked at the site and decided that you might find it interesting or useful. If a friend were to send you a link on tree octopuses, you’d probably trust it over a random one.
Here’s a way to think about a good tree octopus site: it’s a site with the words “tree” and “octopus” that someone whose taste you trust would send you to. We can take a question about what is interesting or useful and turn it into a question of who has good taste. Interestingly, in the case of web searches, those tastemakers are other websites!
Imagine a small version of the web with five sites — A, B, C, D, and E:
An arrow means one site links to another. For example, there is an arrow from E to C but not from C to E, so E links to C but C doesn’t link to E. Which sites do you think might be the most interesting or useful? A certainly got the most links, but how important are those links?
The way Google solved this ranking problem was by giving each site a reputation score. Since A is pointed to by B, C, and D, its reputation should somehow be tied to their reputations. If a is A’s score, b is B’s, and so on, then a first pass at creating Google’s PageRank algorithm could be assigning scores as follows:
Each score is the sum of the scores of the sites that link to it, with each referring site’s score first divided by the number of sites it links to. This means that being linked to by a high-reputation site raises your reputation, but sites that link to a bunch of other sites have their influence watered down, since they can only throw a fraction of their reputation to each.
This appears a little circular at first. To compute b we need to know c, but to compute c we need to know b! Fortunately, this is a system of linear equations, the sort of problem routinely solved in linear algebra. Here’s our system as a matrix equation:
In the language of linear algebra, we are looking for an eigenvector with eigenvalue 1, since the net effect of multiplying the vector we want by our matrix is the same as multiplying it by 1. Not every matrix has such an eigenvector, but the fact that our matrix has every column summing to 1 guarantees that it will!
A solution to an eigenvector problem always turns out the be a subspace of infinitely many vectors called an eigenspace. In our example, the eigenspace is one-dimensional:
We can choose any value for t that we like. However, as long as we choose t > 0, we end up with the same ranking for our five-site web:
meaning we should order our search results A, D, C, E, B or D, A, C, E, B. We could normalize the scores so the highest is 1 or something like that, but the important thing is that we end up with a list of numbers that we can use to order the sites.
If the eigenspace ends up having 2 or more dimensions, we no longer get a nice ranking out of it, but there are ways to tweak the matrix so that the eigenspace associated to eigenvalue 1 is always 1-dimensional. To ensure their PageRank algorithm always returned one clear ranking, Google had to make some slight adjustments to our model above.
If you want to read more about the challenges in ranking websites and are comfortable with some linear algebraic jargon, my favorite primer is The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google by Kurt Bryan and Tanya Leise.
In what other ways is web search mathematical?
