PageRank-Type Algorithm From the 1940s Discovered 108
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."
Just more proof... (Score:3, Interesting)
linearity (Score:4, Interesting)
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:Good advice for all developers (Score:1, Interesting)
You must be the one who hasn't. While they can't be compared to what we have today, they were useful. I particularly liked Infoseek. Oh and GOOGLE SUCKED at first, I remember this VERY WELL, i tried it when it started and it wasn't any good. I guess it took a while to gather enough data to really show their algorithms' potential, now i always use google of course...
Re:Good advice for all developers (Score:4, Interesting)
"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.
Vistas in Information Handling, Spartan Press 1962 (Score:2, Interesting)
The most amazing computer book ever. It has Doug Englebart's first description of “augmenting the human intellect” using computers. It describes what we know now as windows (generic) with pointing devices. It has an early linear document retrieval system using page ranks based on word co-occurrences and it has an early language translation system (Russian to English with examples of translating Soviet missile papers). What a preview of things to come.
It is worth a read just to get into the heads of some of the computing pioneers.
Another required reading book for all aspiring CS students should be John Von Neumann’s the “Computer and the Brain.” Dated, but again this is what they were thinking.
We have a lot to be humble about given the hardware and compilers they had to work with. Not to mention primitive development environments, a.k.a. the card punch.
Re:Good advice for all developers (Score:3, Interesting)
> As for ranking pages by links to other important pages, that's rather flawed?
I hinted that it was OK to innovate or even re-invent. You have to know what you are doing although.
Actually, I totally agree with you on the quoted phrase but I am still looking for a solution (Holy Grail?) to supplant Google implementation. ;-))
Seriously, I really spent some time thinking about this...
Re:Good advice for all developers (Score:3, Interesting)
There is a second rule of advice that goes with this, but that unfortunately usually is forgotten:
Don’t imitate. Innovate!
Yes, it is a good idea to not reinvent the wheel. But it’s even better to invent an airplane! (You know: Thinking outside the box. “Inside the box” would be a square wheel. ;)
Re:Good advice for all developers (Score:1, Interesting)
I'm beginning to suspect I'm being targeted. Nearly every one of my posts has been demodded -1 point (which drops me down to (0) score).
And there's nothing "offtopic" about agreeing with the previous poster's statement: "Don't reinvent the wheel. Look around, search for what's been done before and adapt it to suit your needs." That really is what I do in my day-to-day routine as an engineer.
link to the actual paper (Score:2, Interesting)
The summaries were intriguing but lame. Here's the real thing (preprint):
http://arxiv.org/abs/1002.2858 [arxiv.org]
Author's page is here:
http://users.dimi.uniud.it/~massimo.franceschet/ [uniud.it]
Interesting stuff.