PageRank-Type Algorithm From the 1940s Discovered

KentuckyFC writes "The PageRank algorithm (pdf) behind Google's success was developed by Sergey Brin and Larry Page in 1998. It famously judges a page to be important if it is linked to by other important pages. This circular definition is the basis of an iterative mechanism for ranking pages. Now a paper tracing the history of iterative ranking algorithms describes a number of earlier examples. It discusses the famous HITS algorithm for ranking web pages as hubs and authorities developed by Jon Kleinberg a few years before PageRank. It also discusses various approaches from the 1960s and 70s for ranking individuals and journals based on the importance of those that endorse them. But the real surprise is the discovery of a PageRank-type algorithm for ranking sectors of an economy based on the importance of the sectors that supply them, a technique that was developed by the Harvard economist Wassily Leontief in 1941."

Comments

Good advice for all developers

[ls671]

Well, this is actually pretty good advice for any developer; Don't reinvent the wheel. Look around, search for what's been done before and adapt it to suit your needs. Of course, as a last resort, one can design something new once he has done his homework and made sure nothing that has been done before may be re-used.

Through my life, I have seen a amazing high level of work that has been done in vain because it yielded poor results and that something doing the same better already existed anyway.

Don't get me wrong here, once you have made sure that nothing already existing suits your needs or can be reused, it is fine to innovate and create real new stuff. Just don't get caught trying to reinvent the wheel unless you reinvent it better ;-)

Also, an exception to that principle could be allowed for trivial tasks that are really quick to implement and where searching for an existing solution might cost more than implementing it yourself but be really careful applying that exception rule, it is an open door that leads to trying to reinvent the wheel sometimes ;-))

Re:Good advice for all developers

[cyphercell]

It would have been a pretty exhaustive search without google.

Re:Good advice for all developers

[commodore64_love]

They could have used one of the other search engines in existence in 1997-98, like Altavista or Lycos or Magellan or WebCrawler or Yahoo or Excite or Hotbot.

Re:Good advice for all developers

[pipatron]

I can see that you must be young enough never to have used the search engines you list, if you suggest that you would have been able to find anything useful.

Re:Good advice for all developers

[Weirsbaski]

Well, this is actually pretty good advice for any developer; Don't reinvent the wheel. Look around, search for what's been done before and adapt it to suit your needs, and patent it.

Re:Good advice for all developers

[Junior J. Junior III]

"don't reinvent the wheel" is kindof dumb advice when you think about it.

If I didn't already have a wheel, it would take me a really long time to traverse the world in search of a wheel to see if it had been invented yet. If it has, and it's got sufficient penetration into the market that I know about them already, then, sure, it's a no brainer not to reinvent it. On the other hand, if no one in my immediate vicinity has ever heard of the wheel, then inventing one -- quickly -- is a lot smarter than traversing the known world until I run into a culture that already has wheels. Especially if they might exploit their superior technology to subjugate and enslave my people. Better to have a home-brewed shitty wheel to start off with, and upgrade quickly if I discover that there are other friendly cultures that have better wheels already, and have at least something if I don't discover anyone else, or discover hostiles who already have them.

As long as the cart is loosely integrated with the wheels I have, upgrading to better wheels when they are found to be available should be easy. And I might just learn something about wheels while studying them that applies to other problems, or could even possibly improve the existing state of the art with respect to wheels.

Re:Good advice for all developers

[twosat]

Reminds me of the invention of Turbo Codes in the early Nineties for forward error correction for communication networks. It was later discovered that in the early Sixties, low density parity check (LDPC) coding was developed that performed a similar function but was not used because of the lack of computer power and memory back then. The LDCP patents had expired by then, so now there are two technologies doing the same thing in a different way but one is patent-free. In a similar vein, I read some years ago of a company in the UK who search through expired and current patents looking for inventions that meet their customers' needs. They would often find solutions in a totally different field to the area being researched and a lot of it was stuff that was ahead of its time and its technology had been abandoned.

Re:Patent?

[Jorl17]

If you hate Google: Yes. If you don't: No. If you want Bananas: Get them.

Re:Patent?

[Meshach]

So it could be used as previous art to invalidate Google's patent?

From my read of the linked article it seems that Sergey and Larry cited the previous art in their publications. So it looks like there was no plagiarism, just building a new idea using the tools provided by an earlier idea.

Re:Patent?

[nedlohs]

No, since the one from 1941 didn't say "on the internet" or "with a computer".

linearity

[bcrowell]

What really shocked me when someone first described page rank to me was that it was linear. I felt that this just had to be wrong, because it didn't seem right for a *million* inbound links to have a *million* times the effect compared to a single inbound link. Maybe this is just the elitist snob in me, but I don't feel that the latest American Idol singer is really a thousand times better than Billie Holliday, just because a thousand times more people listen to him than to her. If it was me, I'd have used some kind of logarithmic scaling. I think people do usually describe page ranks in terms of their logarithms, but that's taking the log on the final outcome. I'm talking about taking logs at each step before going on to the next iteration.

To me, this has an intuitive connection to the idea that the internet used to be more interesting and quirky, and it was more about individuals expressing themselves, whereas now it's more like another form of TV.

Of course that's not to say that I want to go back to the days before page rank. God, search engine results were just horrible in those days.

From an elitist snob point of view, one good thing about page rank is that it doesn't let you just vote in a passive way, as Nielsen ratings do for TV. In order to have a vote, you have to do something active, like making a web page that links to the page you want to vote for.

Re:linearity

[Ibiwan]

From a naive, off-the-cuff armchair analysis, it seems to me that PageRank only serves as a way to provide ordering of search results. Funny thing... sorting on positive values will always yield the same ordering as a sort on those values' logs.

Re:linearity

[martin-boundary]

What really shocked me when someone first described page rank to me was that it was linear. I felt that this just had to be wrong, because it didn't seem right for a *million* inbound links to have a *million* times the effect compared to a single inbound link. Maybe this is just the elitist snob in me,

The algorithm is not at all linear in the effect of inbound links. Two inbound links don't have the same effect, instead their effects are first weighted by the PageRank of each node of origin.

Now the distribution of PageRank among nodes is approximately power-law distributed on the web. Intuitively, this means that among all inbound links of a particular node, when that number is high, then 99% have practically no effect on the rank of that node, exactly as you probably thought in the first place. More precisely, you can expect a pareto (or similar) distribution for the influence of incoming nodes, which is not unexpected since these sorts of distributions occur a lot in social sciences.

That said, the PageRank algo is actually linear, but only in the sense of being a linear operator on weight distributions. If you normalize the weights after each iteration, the algo is actually affine (on normalized distributions) rather than linear.

Re:linearity

[Shaterri]

The reason why PageRank 'has to be' linear is essentially mathematical; treating importance as a linear function of the importance of inbound links means that the core equations that need to be solved to determine importance are linear and the answer can be found with (essentially) one huge matrix inversion. If you make importance nonlinear then the equations being solved become computationally infeasible.

What's interesting to me is how close the connections are between PageRank and the classic light transfer/heat transfer equations that come up in computer graphics' radiosity (see James Kajiya's Rendering equation); I wonder if there's a reasonable equivalent of 'path tracing' (link tracing?) for computing page ranks that avoids the massive matrix inversions of the basic PageRank algorithm.

Re:linearity

[Jerry Talton]

*sigh*

You understand neither how the parent post is using the word "linear" nor the PageRank algorithm itself. You can rewrite the eigenproblem at the heart of PageRank as the solution to a linear system, but very few people do. Moreover, this is not the correct intuition to employ to understand what's going on: there are no "massive matrix inversions" here, just a simple iterative algorithm for extracting the dominant eigenvector of a matrix.

Furthermore, you've got it exactly backwards regarding the "connection" between PageRank and light transfer. Since the Markov process used to model a web surfer in the PageRank paper is operating on a discrete domain with an easily-calculable transition function, the stationary distribution (or ranking) can be determined exactly. In rendering, you have a continuous problem for which Markov chain Monte Carlo techniques provide one of the most efficient ways to approximate the solution...but you have to actually simulate a Markov chain to get it (see, for instance, Veach's seminal paper on Metropolis Light Transport). Computing PageRank is an "easy" problem, by comparison.

Or there's the number ...

[PPH]

... of times one Pharaoh's cartouche was chiseled into the obelisks beloning to other Pharaohs.

additional ranking algorithm in the 1940s paper

[commodoresloat]

allowed pages to be ranked and categorized according to whether it was "insightful," "interesting," "informative," "funny," "flamebait," or "troll."

Re:Patent?

[mirix]

I'd better get a rush on a patent for "using pagerank on the internet" then. Take that google.