Computing PageRank on your PC?

An anonymous reader writes "A group of CS researchers of the University of Milan has found a way to compress web graphs at 3 bits per link, and to access them in compressed form. They provide data sets representing real snapshots of portions of the web with one hundred million nodes and 1 billion links. You just need some bandwidth to download a few hundred megabytes of data, and you can compute PageRank with your PC. All the code involved is GPL'd, and the data are public: everybody can grok PageRank now!"

Comments

The major thing missing from Mozilla

[Anonymous Coward]

Is a way to look at Google's pagerank. That's the only real thing the IE Google toolbar has over the Mozilla alternative.

Re:The major thing missing from Mozilla

[FroMan]

Heck, at only 12 megs for a download of mozilla, maybe we should incorporate this "feature" into mozilla. Whats a couple hundred more meg right? :-)

</sillyness>

This was posted by mozilla, don't worry about modding me down for teasing the browser.

Re:The major thing missing from Mozilla

[Anonymous Coward]

Is a way to look at Google's pagerank. That's the only real thing the IE Google toolbar has over the Mozilla alternative.

The Google toolbar for IE has to ask google.com for the PageRank of each page you view, via XML-RPC. One of the fields in the XML-RPC request is a checksum. Without that checksum, google.com rejects the request. So it's just a matter of finding out how the toolbar calculates the checksum based on your URL. Then you could write a standalone (or Mozilla-based) tool for fetching PageRanks.

Re:The major thing missing from Mozilla

[Anonymous Coward]

http://googlebar.mozdev.org

Re:The major thing missing from Mozilla

[FroMan]

sic

Check the second definition supplied. Is this making more sense to you?

Re:The major thing missing from Mozilla

[wherley]

Tried it...but it provides no pagerank. They say:
"We currently have no plans to implement pagerank"

Still - a cool addition to mozilla.

Re:The major thing missing from Mozilla

[Badge 17]

Hey, as long as we're being fussy and using [sic], shouldn't that be "it's," rather than "its"?

"it's" := "it is"

Re:The major thing missing from Mozilla

[JamesDotCom]

The problem is, is that the google toolbars checksum changes constantly. So if you were to find out how the google toolbar works exactely regarding pagerank, all it takes if for googles official toolbar to change it and it wont work anymore. The catch is however, that if you send a wrong checksum to google, they don't send back an error message of any sort instead they send back a fake pagerank. So you wouldn't really know if it was still working or not.

Re:The major thing missing from Mozilla

[FroMan]

Yep. Good call. :-) Thanks.

This sounds cool..

[xchino]

Now if I can just think of a reason why I would need this..

Re:This sounds cool..

[Daniel_Staal]

Now if I can just think of a reason why I would need this..

And you call yourself a geek. *Sigh*.

It doesn't matter why you need it. It's technical, GPLed, and has to do with Google. That's all the reason you need.

Re:This sounds cool..

[imAck]

This is really cool, not just for page rank. Finding pre-compiled data sources like this can be a great catalyst in scientific research. Just my two cents.

Re:This sounds cool..

[(trb001)]

It's technical, GPLed, and has to do with Google

It's a geek hattrick!

Re:This sounds cool..

[inerte]

1) Soccer/BasketBall/Any Ball game: Put a sensor on everyone's shoes (or hands) and one at the ball. Consider each player as a webpage and each pass as a link. The ball is the vertex. Then you can find what player (from what position) makes a good pass, and to who; Optimize your strategy :)

2) P2P: Store and analyze peer positions (both geographically or between network connections/routes) to find the best combination. Consider the download as link, and each peer is a vertex. For example, "cluster" peers with the same content (if you make the file hash as the link initiator), or from the same country.

3) User Interface: Streaming and saving inumerous screenshots from people using their computer, you can correlate what are the most common tasks performed on an application, or how "difficult" is to use it. For example, how many pixels the mouse pointer usually travel, either when you pass where you wanted to click, or from buttom to buttom. If you plot a web graphic showing that users usually go from buttom "A" to "B", and they are 20 pixels away, you could reduce the distance.

4) Compression (I guess?): Find on your hard drive common byte sequences between files, and create "webpages" for them. When you open a file, it will look for its bytes on a vertex (the "link" from the webgraph). The more files you have, the better they are compressed.

Also good for defrag: Keep the most accessed vertexes on the start of the hard drive, or its files "around";

5) Surveys: If each answer and the profile of who's answering is a webpage, you can create vertexes of interests

6) Spam: Consider each word from the spam as a vertex. Parse the email and connect each word with a vertex. Store this information (how many links a vertex have). When an email comes, check if it is spam by watching to how many vertexes its words connect to (and how "big" the vertexes are, ie: previous connections).

Dumb Question:

[Xesdeeni]

What's Page Rank? Does this indicate how often my page is visited?

Xesdeeni

Re:Dumb Question:

[Chris_Stankowitz]

Do you mods ever stop to wonder if this guy could have been asking a legit question? Its possible he doesn't know. Also possible that others don't. I know...I know..., this is /. how could he not know right. It is still very possible. I'm not saying he should have been modded up, but by modding him down someone may miss the chance to read his post and reply to it with an intelligent answer. All of that being said. I would answer his question. But now that I think about, I'm not sure what it is. I 'think' I know. But, I think he and I are in the same boat. I also thought about posting this as an AC, but I won't. Then surley someone will just think that it was the original poster posting as an AC. He may be trolling. He may not be. It won't hurt to answer the question.

Re:Dumb Question:

[Andorion]

Well said =)

~Berj

Re:Dumb Question:

[Anonymous Coward]

Jesus, you created a second account just to defend yourself!

Re:Dumb Question:

[kevin_conaway]

I didnt know what it was either. Mod parent and grandparent up

Re:Dumb Question:

[Xesdeeni]

Thanks for the defense, but I was kinda enjoying my first post labelled as a "Troll" :).

So that's how Google ranks its pages. I didn't realize they tracked the number of links. I didn't really think about it long, but I figured they just used how many times the query string appeared, maybe the age of the page, or whatever.

I wonder if this data would be hugely different from the number of visits a page receives, considering easily typed-in page addresses (fewer links needed), or the possibility that a single link is followed many times, while another is almost never followed.

Anyway, thanks to AC for the info.

Xesdeeni

Re:Dumb Question:

[biomass]

Page rank, to a first order of approximation, ranks your page by "popularity". Using a voting system,it counts the number of links to your page.

To a second order of approximation, it weights the votes of the referencing links by their popularity.

To a third order of approximation, it is a Markov chain that measures the long term likelihood of you arriving at a page, if you to randomly traverse the net: taking random links out of a pages and occasionally take (1/20?) random jumps to arbitrary urls.

Re:Dumb Question:

[sig cop]

I didn't know what is it either.

Mod parent and grandparent and great-grandparent up.

Also, mod parents children up.

Also, mod great-great-grandparents great-great-granddaughters up.

Also, say up unto them verily, that the mod of the parent will be cast down the generations to be a mod on the children, and on the children's children, and on the children's children's chilluns.

And also, mod up the nephews of the parents of the sibilings of the grandparent for though they be trolls or flaimbait, they are righteous in the eyes of the moderators.

And thou shalt visit the mods onto the descendents on through the generations, for I, your Mod, have smote upon thee a mod pestilence that shalt not be lifted until the second coming of the JonKats.

Thanks be to Mod, Amen

Re:Dumb Question:

[iphayd]

I'm sure Jesus has better things to do that defending himself on Slashdot.

Or posting on Slashdot, for that matter.

Re:Dumb Question:

[Ravioli]

... while forgetting to login with the third account for all the karma points! ;/
--

Re:Dumb Question:

[The Cydonian]

Think of it as Google-bestowed karma on your website. :-D

Re:Dumb Question:

[Where's my towel]

Some papers:

http://citeseer.nj.nec.com/page98pagerank.html
The original definition of pagerank.

http://www.google.com/technology/
The laymans definition.

http://dbpubs.stanford.edu:8090/pub/1999-31
How to compute it quickly.

http://citeseer.nj.nec.com/haveliwala02topicsens it ive.html
How to make it topic-specific

Re:Dumb Question:

[jonadab]

> I wonder if this data would be hugely different from the
> number of visits a page receives

Dunno. But there's no way for Google to know how many visits
a page receives; whereas, they can calculate how well-linked
it is.

It would be interesting to do a study on the relationship between
pagerank and page loads and number of distinct visitors, but that
would require having log data from all the servers involved; it
would be pretty easy to get log data from a small number of servers,
but getting those data for a decent subset of the internet would be
significantly less easy.

Tee Hee

[teamhasnoi]

I bet the Searchking is steaming right about now...

"Finally, proof!!"

Some webmasters/SEO's are obsessive

[Anonymous Coward]

If Google tweaks one thing, causing result 97 to shift to result 98, they notice. They'd be doing this daily to check on their pages.

does this mean...

[Dreadlord]

I wonder if this goes as it's planned to, is it the end of search engines, and the beginning of peap to pear search?

Re:does this mean...

[IMarvinTPA]

I was going with it as an autamotapea(sp?, and no the spell checker didn't know either). So pick a random chirping bird or better yet, those Easter Marshmellow birds seeking out pears.

IMarv

Re:does this mean...

[critter_hunter]

Was the word you were looking for "onomatopoeia". You weren't even close, but I can hardly blame you

Re:does this mean...

[JamesOfTheDesert]

... pear search

... to find the fruits of your labor?

What a grape idea! Orange you glad you thought of it?

.

.

.

Ok. Groan fest is over.

Re:does this mean...

[nacturation]

... and the beginning of peap to pear search?

Depends on whether it's pear connections use they're bandwidth effectively. What happens when they loose the connection? I have too say that their way to many pear too pear programs out they're too shut them down all ready.

Re:does this mean...

[Davak]

PEAP really isn't used anymore...

PEEP is now the common term.

PEEP - Positive End-Expiratory Pressure

Like anybody gives a flip.

Davak

Which sites are the Root(s)?

[amembleton]

When these Web Graph or Page Rank things are drawn up which sites do they use as the roots?

I mean they've got to start with some site(s) and then go through each link from there.

Re:Which sites are the Root(s)?

[marcs]

The ODP/dmoz would probably be a good place to start.

Re:Which sites are the Root(s)?

[cristofer8]

I would assume they have multiple roots. They have to seed google with some list of sites. In fact, I would guess that every site google sees gets added as a root, as well as any site added by google employees.

Re:Which sites are the Root(s)?

[warkda rrior]

It is a graph, not a tree, so there is no one root. Maybe you are looking for the seed site, i.e. the first site added to the webgraph they construct. You can choose any site you prefer, although something well-connected is better. It seems to me that Yahoo! would be a good starting point.

Re:Which sites are the Root(s)?

[menscher]

Google starts their webcrawl with the Stanford University home page. (Info based on a talk given by Craig SIlverstein, the directory of technology at Google.)

Re:Which sites are the Root(s)?

[jonadab]

Backwards you have it. You start at leaf nodes (pages that don't
link to anything) and work backwards to pages that link to the leaf
nodes, pages that link to those, and so forth.

Initially you have lots of webs -- one for each leaf node. As you
add pages that link to them, these will tend to get joined as you
find that many of them belong to some of the same trees.

Oh, and you reserve known search engines for last.

One Billion Linnks?

[Anonymous Coward]

There is more links than that just at Microsoft's Support page. Although I don't know if you can call them links if they only send you around in a cirlce.

beyond PageRank...

[rfischer]

... I would be interested in how the links change over time. Maybe take a new snapshot every day or week, see the web evolve.

Re:beyond PageRank...

[big_gibbon]

That would be amazingly cool.The only problem (and it's not really a problem) would be that generally people never, or rarely, remove links. If you limited this to links only (say) a month old or younger, you could see the paths of memes round the web . . . for example right now, you'd probably see a lot of BitTorrent hotspots, whereas a couple of years ago there'd be lots focussed on "all your base" . . .

Anyone got a lot of procesing power and some spare time? ;)

P

Re:beyond PageRank...

[Niet3sche]

That'd be COO... wait, no, it's called
www.archive.org
And they have the "wayback machine" or some such.
It's been done already.

PageRank is part of Google's algo

[Anonymous Coward]

It's basically how well linked to your page is, and how well linked to the pages linking to you are, and so on. It's an advanced form of link popularity. The idea is that the more people that link to something, the more influential/important it is. Some sites have high PageRanks of 10 (like Google), while Slashdot is something like an 8. Many pages are in the 4-6 range. Every link you create is like a "vote" for another web page.

Re:PageRank is part of Google's algo

[e2d2]

Google's PageRank was actually named after Larry Page, the creator of their system for ranking pages. Pun was obviously intended.

Re:PageRank is part of Google's algo

[kisrael]

Is there a way to see a given site's absolutely PageRank w/o using that toolbar? (as opposed to its relative PageRank of where it shows up on your search results.)

Re:PageRank is part of Google's algo

[Anonymous Coward]

If your site is in the Google Directory (based on DMOZ), it may have a pagerank listed next to it.

Re:PageRank is part of Google's algo

[nacturation]

Riiiight... and hypertext was so-called because someone's kid was always hyper. I suppose next you'll be telling us that Dell Computers was named after... er, wait... never mind.

Re:PageRank is part of Google's algo

[brakk]

Ok, now we know what it is, can someone tell me what is usefull about being able to calculate it on my PC?

Re:PageRank is part of Google's algo

[thumperward]

Informative, it gets! Informative!

- Chris

Re:PageRank is part of Google's algo

[InfoCynic]

PageRank is a one-dimensional recursive weighting for a web page. Intially you assume all pages were created equal. Now for each page, compute an updated PageRank based on indegree (number of pages linking to the site). You usually also introduce a weighting factor which is designed to simulate some random chance that you "jump" to the next page by just typing a URL, not following a link. After that, you typically normalize the scores (sum of squares must equal one is the preferred norm).

Now you have to iterate, but on subsequent iterations, you're no longer consider with purely indegree. You care about the PageRank of pages linking to you. Pages that are "popular" and have high PageRank will boost your score. Typically you iterate until the values converge to within a given threshold. If you know linear algebra, you can also cheat and use eigenvalues, but that's not the point.

There are better algorithms, like Kleinberg's, which gives each page a "hub" and "authority" score, where just linking to a page isn't enough, and you can learn more about that in a Web Algorithms course.

I can see it now...

[AyeRoxor!]

"[...] even on a PC with as little as 256 Mbytes of RAM."

Somewhere in 1980, milk shoots out of Bill Gates' nose for no apparent reason.

Re:I can see it now...

[nacturation]

Damn, that's about the funniest thing I've read all day. Rather Douglas Adams-ish -- well done.

exactly

[Anonymous Coward]

This is what we need to talk about at our little IRC chat session tonight, commander.

web graphs at 3 bits per link, that's a paddling...

compute PageRank with your PC, that's a paddling....

groking PageRank, you better believe that's a paddling...

Google with feedback

[Sanity]

Doesn't Google have a patent on PageRank?

Anyway, forgive the opportunism, but this is reasonably on-topic. Last weekend I set myself the ambitious task of improving on Google. I came up with a Google front-end which allows you to give feedback on the quality of search results, and thus refine your search. I could really use people's help to test it out - you can find it here. Feedback would really be appreciated.

Re:Google with feedback

[YoJ]

The whole point of patents is to encourage inventors to publish their inventions in a safe way. In some respects, PageRank is a good example of how the system is supposed to work. They publish the algorithm, people examine it and experiment further with it, but the inventors still have protection against people ripping off their work.

The problem is that the GPL does not allow distribution of patent-encumbered technology. The authors of the code in question have every right to release their code with whatever license they want (I believe this is a free-speech issue, especially since the purpose of releasing the code is for doing research). People who receive their code may not use the code in a way that violates the patent, and in addition may not redistribute the code at all (since it would violate the GPL).

The other issue is that PageRank is really a mathematical formula, and as such is unpatentable. What they actually patented is an algorithm for computing PageRank. If someone finds another way of computing the same formula, I think the patent holders would have a very hard time showing infringement.

Re:Google with feedback

[sjlutz]

The only problem with getting feedback from anyone is that it would be very easy to reduce a search engines hit on specific things. Example, say I work for Pepsi, I seach to cola, and say "BAD" for every Coca-Cola result. I script it to submit hundreds of "bads" an hour. Now, I search for Cola, and only get Pepsi results.

This is good, but...

[Prince_Ali]

This is good, but I'd rather have the google cache compressed to 3 bits per page.

"I'll be there in a minute! I'm downloading the Internet!"

Re:This is good, but...

[Jerf]

Here ya go:

011

Proper decompression is left an as exercise for the reader.

Now, let us discuss payment schemes...

Re:This is good, but...

[misterhaan]

download the internet

Live XML Version

[amembleton]

data sets representing real snapshots of portions of the web

If these are snapshots then you'll need to keep downloading them for your Page Rank system to be up to date. The web is constantly changing and therefore so is Page Rank. I can't see having a data set on your computer being all that usefull as it'll soon expire.

It would be far better to be able to link to a data set via XML and query it. That way you would have live upto the minute Page Ranks. I know that Google already does a live Page Rank system, but being able to access it and query it would be usefull.

Re:Live XML Version

[sporty]

If these are snapshots then you'll need to keep downloading them for your Page Rank system to be up to date. The web is constantly changing and therefore so is Page Rank. I can't see having a data set on your computer being all that usefull as it'll soon expire.

You are absolutely right. This is Google does on your behalf. They have the computing power, storage-wise as well as processing-wise to do the needed updating. Not that google can do it 24/7, but they do better than I can with my 4 computers. :\

It would be far better to be able to link to a data set via XML and query it. That way you would have live upto the minute Page Ranks. I know that Google already does a live Page Rank system, but being able to access it and query it would be usefull.

And expensive. Remember, queries more complex than "what is related to this" and doing the computation on the data requires resources to move the data from google to you PLUS the additional query. It'd be a bandwidht hog if not compressed significantly. Google's shared API is prolly more sufficient.

Google patents?

[PaulBu]

All the code involved is GPL'd, and the data are public: everybody can grok PageRank now!

GPL'd? Hmm, I thought that Google did patent the PageRank algorithm (correct me if I am wrong), so re-implementing THEIR algorithm even more efficiently would be incompatible with GPL. OTOH, if it is not THEIR algorithm, it can not be called 'PageRank'
Oh, the evils of software patents...
Paul B.

Re:Google patents?

[JoeBuck]

Google hasn't exactly patented the algorithm for all uses, and no court has determined that the code infringes the patent, and software patents aren't valid in most countries, so it's not clear whether or not there is any compatibility.

It would seem that anyone who uses the code to build a search engine would be infringing, but even that is something that lawyers can argue about.

Re:Google patents?

[egomaniac]

OTOH, if it is not THEIR algorithm, it can not be called 'PageRank'.

Unless the term is trademarked (is it?), you can call whatever the hell you want "PageRank" and nobody can do a thing about it.

Doesn't actually calculate PageRank?

[Vultan]

As best as I can tell from the website, the API is only for storing and interacting with a large graph. Nothing there is actually involved with PageRank. You could use this API presumably to write your own PageRank code, but to say "everybody can grok PageRank now!" is misleading at best.

Moreover, IANAL, but isn't the PageRank algorithm patented by Google? Wouldn't this prevent anyone from releasing GPL code that computes PageRank?

Re:Doesn't actually calculate PageRank?

[morzel]

Moreover, IANAL, but isn't the PageRank algorithm patented by Google? Wouldn't this prevent anyone from releasing GPL code that computes PageRank?

It would prevent anyone in the US from releasing that code. Software patents don't apply everywhere (yet)

Isn't that illegal?

[anthony_dipierro]

PageRank is patented, isn't it?

Re:Isn't that illegal?

[Anonymous Coward]

Yes, and it's trademarked, too. Here's a bunch more info on PageRank.

Re:why is rank/rating necessary?

[TopShelf]

You get sort of a self reinforcing cycle of wankage...

For a second there I thought you were just talking like Elmer Fudd! "wating and wanking incwease the welevance of pagewanking..."

Not Page Rank (?)

[SirTwitchALot]

I don't think this is pagerank, reading the link, this looks more like another rating system that is similar to pagerank. It's great for study, but I don't think reading through the source and finding ways to 'trick' this algorithm will necessarily work on Google. Correct me if I'm wrong someone.

has to be said

[madHomer]

It's just not the same without the pigeons...

By the way...

[Sanity]

...it isn't on a fat pipe, so please understand if its slow.

Re:By the way...

[el-spectre]

heh, we need a new mod level, -1, CheapShot

Re:By the way...

[fanpoe]

I'm sure some would prefer it to be +1, CheapShot ;)

Re:By the way...

[el-spectre]

probably everyone except the guy who gets mocked :)

then again, a whole lot of "MS SUCKS" posts might qualify.

Proof of concept only

[Saganaga]

I think this project is really just a proof of concept. As another post pointed out, to make this really useful you'd need to regularly update your local data set, which isn't very practical for most people.

Also, if the downloadable dataset only covers a small portion of the web, how can this system's utility really compare to Google's?

That said, I think computer science proof-of-concept type project are very useful and serve a valuable purpose in getting the ideas out there for others to improve upon.

Re:why is rank/rating necessary?

[Pionar]

It could have receded back into the depths and maintained quality but it put page-ranking first, attempting to attract and contain a particular audience.

I disagree. In case you haven't noticed, the title of the /. front page is "News for Nerds, Stuff that Matters." So, of course /. is attracting a particular audience. That's a Good Thing.

Target audience is one of the most important decisions when designing a web site. "Good info" is a subjective concept. What's good to you is not necessarily good to me. But, chances are if I search for something that I'm looking for, PageRank can provide a sense of the more authoratative pages for that subject.

Also, putting stuff up for popularity's sake is a great reason to put something up. If I didn't want my employer's site to be seen, I wouldn't have put it up there. Attracting eyeballs is the only way to get good info. The more eyeballs, the better the accuracy of information. Why do you think peer review is such a big deal in scientific arenas (and it is, as I know from working for a big-name medical school)? If I was a scientist reviewing another scientist's work, then I would look at the writing aspects of the work. A little bit of style often makes information more credible to others. Don't ask me why, just know that it's human nature.

Explains it all...

[Spokehedz]

It uses Slashdot as a root, of course. ;)

Seriously, I don't know. Here's a page on how Google works though.

http://www.google.com/technology/index.html

Wow! The site is not /.'d!

[tyroneking]

Though after a quick read, I can see why ...

You're an optimist

[niom]

Maybe take a new snapshot every day or week, see the web evolve.

How much time do you think it's needed to take a snapshot of the Web? Most certainly much longer than a day or even a week. My bet would be several months at the very least.

Re:You're an optimist

[jonadab]

> How much time do you think it's needed to take a snapshot of
> the Web? Most certainly much longer than a day or even a week.
> My bet would be several months at the very least.

I strongly suspect some pages get re-evaluated much more often than
others. At least, it _ought_ to be that way. For one thing, pages
with a higher PageRank are more important (to the evaluation of
other pages) and thus should get redone more often. Additionally,
pages that are known to change frequently should be done more often
than pages that are not known to have changed previously. How to
ballance those two considerations is an open question.

What a mess

[Ignorant Aardvark]

Sure, now everybody can grok PageRank, but I, for the life of me, cannot grok grok.

Re:What a mess

[dpbsmith]

Just in case this wasn't an implied rhetorical question... the term, as far as I know, was invented by Robert Heinlein in his novel _Stranger in a Strange Land,_ where it is an expression used by Martians. It literally means "to drink," but the Martians use it to mean an understanding that is both very deep and very complete.

Re:What a mess

[mbourgon]

Yes. Basically, "to share water with", which on Mars meant you were more than brothers. Considering how little water was/is on Mars, it was a great honor.

Re:What a mess

[nonetheless]

Indeed.

OED Online:

grok, v. U.S. slang. Also grock.

[Arbitrary formation by Heinlein (see quot. 1961).]

a. trans. (also with obj. clause) To understand intuitively or by empathy; to establish rapport with. b. intr. To empathize or communicate sympathetically (with); also, to experience enjoyment.

1961 R. HEINLEIN Stranger in Strange Land iii. 18 Smith had been aware of the doctors but had grokked that their intentions were benign. Ibid. xxiv. 250 Now that he knew himself to be self he was free to grok ever closer to his brothers. 1968 T. WOLFE Electric Kool-Aid Acid Test vi. 86 Instead they are all rapping and grokking over the sound it made..as if they had synched into a never-before-heard thing, a unique thing. 1968 Playboy June 80 He met her at an acid-rock ball and she grokked him, this ultracool miss loaded with experience and bereft of emotion. 1969 New Yorker 15 Mar. 35, I was thinking we ought to get together somewhere, Mr. Zzyzbyzynsky, and grok about our problems. 1975 D. LODGE Changing Places iv. 137 Nestling earth couple would like to find water brothers to grock with in peace. 1984 InfoWorld 21 May 32 There isn't any software! Only different internal states of hardware. It's all hardware! It's a shame programmers don't grok that better.

Re:What a mess

[MyHair]

I never knew the source but figured it had to be Emacs. grep, grok, natch?

I feel so much more enlightened now, and now I have less reason to learn Emacs. Viva vi!

bile@netscape.com

[radiumhahn]

It doesn't mean a lot to me when my brother says he is going to double his efforts to find a job. This is especially true if you know my brother.

Google's algorithms have changed quite a bit

[HiKarma]

Since their original papers, according to all posted reports. So I don't think you're really going to get the exact google number from a basic algorithm and this data set.

They also use terms that appear in links as a major key in ranking searches.

(Among other things.)

Not that it is not interesting to see these rankings, and note the most widely linked to sites on the net.

Which, by the way, after the obvious winners like Yahoo, include Adobe and Real networks, which have gotten immense numbers of sites to link to them with "Get acrobat reader" style links.

I've often wondered if the makeashorterlink and tinyurl folks are doing it just for the googlejuice.

In reverse, many sites now use javascript links in order to preserve their googlejuice.

Very much a heisenberg phenomenon here.

I wonder...

[crashnbur]

...how this can be used to discover the percentage of broken links on the web at any given moment in time.

Feedback is local

[Sanity]

Your feedback is local to your search, it doesn't affect other people's searches.

You say Power-Law graph of a billion pages...

[Salamanders]

and I say "Dammit, where are all the pretty pictures."

can anyone explain what a web graph is?

[bongoras]

I get this from the article: "A set of flat codes, called Î codes, which are particularly suitable for storing web graphs (or, in general, integers with power-law distribution in a certain exponent range). The fact that these codes work well can be easily tested empirically, but we also try to provide a detailed mathematical analysis."

Maybe it's my ADD. Maybe it's my inherent dumbassedness... but I can't grok that.

So what is a web graph? How is that related to PageRank? If I download all this data, what the hell do I use it for?

Re:can anyone explain what a web graph is?

[Wesley Felter]

Yeah, I think they should have explained that. Presumably a Web graph is what you get when you treat each URL as a node and each link as an edge in a graph. PageRank is an algorithm used by Google that takes a Web graph as input.

Re:can anyone explain what a web graph is?

[lordbrain]

In a graph is made up of two things, edges and vertices.

In a web graph, vertices are webpages and edges are hyperlinks.

PageRank determines how many incoming edges a vertex has. Given the nature of the web, this is a nontrivial problem because a vertex only knows its outgoing edges.

The assumption for PageRank is that the more incoming edges a vertex has, the more popular it is. So you would use this to figure out how popular a particular vertex is.

Given this you could do like Google and combine it with a search engine to prioritize the results.

Can google sue for reverse engineering pagerank

[asscroft]

even if it was improved upon. Can the idea of ranking based on links popularity be patented? Did google patent it? if not, how much longer before some asshole lawyer in melo park or amazon/ms/aol does and tries to shut down google.

Re:Can google sue for reverse engineering pagerank

[ktorn]

Hold on, if someone can prove that they had that idea first, how can a patent force any shutdown?

Besides - not all browsers show page rank

[kiddailey]

And let's not forget... not all of us even get exposed to page rank regularly.

On my Mac for example, I can't see it at all. On my Wintel I can, thanks to the Google toolbar.

Ask and ye shall receive...

[Theaetetus]

and I say "Dammit, where are all the pretty pictures."

Here (for free)

Here too (for free)

This one too (for free)

This one also (free)

And don't forget this classic ($30 poster)

-T

WebGraph has a PR of NULL

[mcguyver]

If WebGraph can inflate their google PR to 10 then I'm a believer. Until then this looks like one of the many tools available to analyse your PR.

The WebGraph tool may be interesting for college students but the webmasters that are interested in seo techniques are going to find little use out of this tool.

pagerank for the masses

[yoyo81]

I don't know what the big deal is. I've always been able to do pagerank on my computer...

Just use Google

[kc0dxh]

Why reinvent the wheel?

Could I someday use it for my PC - Re:This soun

[leoaugust]

I wonder if I can use pagerank algorithm for the smaller universe of my harddrive itself?

I have over 6,000 files on my PC many of which link to each other, and I am adding more links between them as time goes by. The collection is now so big that I can't even revist my own files and reason out the implications of the links between pages, beacuse of the huge time it would take to even spend a minute on each saved file.

I wonder if something like Pagerank will let the important files that are linked by many others on my PC to rise "up" like the cream to say, and I can avoid having to use keywords and categories to wade through all the clutter on my harddrive ...

Any other ideas of how to study the relationship between my 6,000+ files?

I also have quite a few articles, e.g. news items saved from the web itself. I wonder if the pagerank of google for those saved articles could also help me flush out the important "external" articles on my harddrive itself.

Re:why is rank/rating necessary?

[FearUncertaintyDoubt]

You get sort of a self reinforcing cycle of wankage the more we increase the "relevance", "awareness" or "utility" of pageranking.

That reminds me of Asimov's pyschohistory and the Second Foundation. That the First Foundation had to be unaware of the influence of the Second Foundation for it to work. Maybe that makes Searchking the Mule?

page rank isn't real-time.

[jasonhamilton]

Have you ever developed a website and monitored SE traffic to it? PageRank is not a real time process. If you're running your own version of it, updating it once per month is more than enough.

Re:why is rank/rating necessary?

[Spazmania]

TV without Nielsen ratings would be better too, for similar reason.

We have TV without Nielsen ratings. We call it "PBS."

Is PBS better? Sometimes. Perhaps even often in recent years. Certainly no one has ever referred to PBS' content as mindless drivel, the way we talk about things like Survivor and American Idol.

But let me ask you this: If you could have only one TV station and you had to choose between ABC, CBS, FOX, NBC and PBS would you choose PBS? Didn't think so.

You mean google's spyware

[MushMouth]

Don't think for a moment that google is not tracking and saving this.

Re:You mean google's spyware

[hkmwbz]

Spyware? How can it be "spying" on the user when the installer practically assaults the user with warnings that it will send the URL to Google so it can return the pagerank. How exactly is it supposed to send the pagerank if it can't send the URL to Google anyway?

Ridiculous. You "anti"-spyware freaks are more dangerous than most spyware because you stir up shit and cause hysteria by accusing everything and everyone for spyware. You remove the focus from the actual spyware and sleazeware out there.

You are actually helping spyware companies by causing hysteria and confusion.

Great job, mister spyware posterboy.

Three-bit compression for web pages.

[stripmarkup]

Here's the algorithm:

000: page is spam. Ignore it.
001: page is porn. Porn is all the same, show porn page from disk.
010: page is pop-up ad. Block it.
011: page is a 404.
100: page has javascript. Show random javascript error.
101: page is Slashdot.
110: page is Slashdot.
111: page belongs to the .000001% of uncompressible pages, store it as is (full page follows).

Re:Three-bit compression for web pages.

[teorth]

000: page is spam. Ignore it.
001: page is porn. Porn is all the same, show porn page from disk.
010: page is pop-up ad. Block it.
011: page is a 404.
100: page has javascript. Show random javascript error.
101: page is Slashdot.
110: page is Slashdot.
111: page belongs to the .000001% of uncompressible pages, store it as is (full page follows).

I think your code for 110 is incorrect, it should be: 110: page is Slahdotted.

Terry

Googling your harddisk

[|>>?]

While calculating PageRank seems like a nice idea, I'm much more interested in having a google search available over my harddisk. I recall that AltaVista in the mid-90's had a programme that created an index over your whole disk - it dealt with many filetypes including .doc, .pdf, .mbox and basically gave you an AltaVista search over all your harddisk content.

Anyone know of anything like that?

Re:Googling your harddisk

[MyHair]

I'm much more interested in having a google search available over my harddisk.

I thought I remember Google having a product like this, but I can't find it now.

MS Win2k and WinXP have an indexing service that's supposed to do just what you want. It's not enabled by default in 2k; not sure about XP. I've been afraid to try it for various paranoia and stability reasons.

HTdig was my next thought. It's designed for web pages, but I bet you could restrict it to your hard disk. However, the site says they don't index non-text files yet.

For some reason I felt like searching Freshmeat and came up with SWISH++. It says it can index hard drives and non-text files "such as Microsoft Office documents", although the method they describe they use is not one I'm sure would work since Office docs can be in Unicode.

Both HTdig and SWISH++ are GPL. There were other possibilities on Freshmeat, too.

Re:why is rank/rating necessary?

[baka_boy]

I really shouldn't rise to this bait, but I can't resist: yes, given the choice between those networks, I would choose PBS. Just as I would take a non-profit-driven Internet, public radio over Clear Channel and its ilk, and community mesh wireless networks over 3G mobile phone service.

Google has been, so far at least, a rare exception in the world of privatized communications utilities, by consistently showing a amazing lack of intention to lock people into their service, using either exclusivity agreements of some sort or the simple expedient of proprietary technology (i.e., "increase your PageRank by 10% if you support new encrypted GoogleML tags on your site!"). Nothing is permanent, though, and as we all know, single points of failure are a no-no.

So, to bring all this back somewhere in the general neighborhood of the main story: further distributing the capability to build "mini-Googles", or specialized, community-maintained (but still fairly large-scale in terms of number of pages and links indexed) search tools is very interesting, and a useful body of technology to perpetuate.

Or, even more generally, the technology needed to do large-scale storage, analysis, and manipulation of directed graph structures is a very useful tool. Software analysis often relies heavily on large graphs showing dependencies, caller-callee relationships, variable accesses, etc., as do any number of AI subdomains like knowledge representation and planning systems.

Hattrick

[Daniel_Staal]

Of course it's a hattrick. Two reasons just isn't impressive, and four is starting to get cumbersome (like you are droning on). Now 7-boredom are funny again too (depending on how funny the reasons themselves are), but I wasn't sure I could come up with seven on short notice. Three reasons was the optimum length for that post.

Can someone explain.....

[reality-bytes]

Exactly how my last post was trolling?