The patent was actually assigned to Stanford University, and Google then licensed it (this is also how most pharmaceutical discovery is patented and licensed). A fundamental problem is that these patents all rely on federal funds from US taxpayers to one extent or the other, and while it may make sense for Stanford to hold the patent, there's a strong argument that any US entity should be able to license it (not just one exclusive license in other words).
Prior to Bayh-Dole legislation in the 1980s, this was the case for university-held patents: they could be not be exclusively licensed. Repealing that legislation would be a good idea to avoid the rise of monopolisitic behemoths like Google/Alphabet.
The patent approval process isn't perfect. Had you violated the patent, and had Google sued you, you could always argue prior art. What would your evidence be?
The patent office could have just missed the prior art, or more likely is that the claims are more narrow than and represent an improvement upon said prior art.
The patent doesn't cover just ranking documents based on their citations; it also covers various ways to extract "citations" from a webpage, weighting the pages to determine their importance, and doing all of this efficiently enough that you can process millions of queries per second.
I was thinking of the Pinski-Narin method, but there are other earlier uses of eigenvector calculations over very similar data: https://arxiv.org/pdf/1002.2858.pdf
Prior to Bayh-Dole legislation in the 1980s, this was the case for university-held patents: they could be not be exclusively licensed. Repealing that legislation would be a good idea to avoid the rise of monopolisitic behemoths like Google/Alphabet.