The Second Eigenvalue of the Google Matrix

Want an analytical peek at some of the core components of Google's famous PageRank algorithm? These two papers from Stanford offer some heavy-duty insights into Google's operation.

The abstract of the first paper, "The Second Eigenvalue of the Google Matrix," is likely sufficient for most people. Authors Taher Haveliwala and Sepandar Kamvar state:

"We determine analytically the modulus of the second eigenvalue for the web hyperlink matrix used by Google for computing PageRank. Specifically, we prove the following statement: 'For any matrix $A=[cP + (1- c)E”^T$, where $P$ is an $n \times n$ row-stochastic matrix, $E$ is a strictly positive $n \times n$ rank- one row-stochastic matrix, and $0 \leq c \leq 1$, the second eigenvalue of $A$ has modulus $|\lambda_2| \leq c$. Furthermore, if $P$ has at least two irreducible closed subsets, the second eigenvalue $\lambda_2 = c$.'"

Got that? Wait! There's more!

"This statement has implications for the convergence rate of the standard PageRank algorithm as the web scales, for the stability of PageRank to perturbations to the link structure of the web, for the detection of Google spammers, and for the design of algorithms to speed up PageRank."

Another paper looks at ways to speed up the calculation of PageRank values by looking more closely at the link structure of local hosts -- and may have implications for all of you webmasters who obsess over your site's PageRank values. From the abstract of "Exploiting the Block Structure of the Web for Computing PageRank," by Sepandar Kamvar, Taher Haveliwala, Christopher Manning and Gene Golub::

"The web link graph has a nested block structure: the vast majority of hyperlinks link pages on a host to other pages on the same host, and many of those that do not link pages within the same domain. We show how to exploit this structure to speed up the computation of PageRank by a 3-stage algorithm/.

"Empirically, this algorithm speeds up the computation of PageRank by a factor of 2 in realistic scenarios. Further, we develop a variant of this algorithm that efficiently computes many different 'personalized' PageRanks, and a variant that efficiently recomputes PageRank after node updates."

Heavy reading, but fascinating for the insights they offer into one of the web's most popular search engines.

The Second Eigenvalue of the Google Matrix
A Stanford University Technical Report, authored by Taher Haveliwala and Sepandar Kamvar.

Exploiting the Block Structure of the Web for Computing PageRank
A Stanford University Technical Report, authored by Sepandar Kamvar, Taher Haveliwala, Christopher Manning and Gene Golub.

Search Engine Forums Spotlight

Google phonebook!
Webmaster World Forums
"Reverse lookup is a service that many companies provide, and have provided longer than Google. Google does allow you to opt out if you don't want that information in the search engine."

Overture and Gator
ihelpyou Forums
"This Overture client, small fry though I may be, would definitely pull all advertising on Overture if the relationship were made complete."

Google referrals
ihelpyou Forums
"My new hobby is to think like my customers. I really go out of my way to get into their minds. And the better I understand them the more highly targeted keywords I find that I should have optimized for."

CitySearch to start new search engine
Webmaster World Forums
"If there is an advantage to CitySearch, it is that the user types in his/her ZIP code prior to doing the search, so the results can be naturally localized. If I go to CitySearch and type 'Plumber', I'll get one in my local area. That's what's missing on the regular [search enginess”."

Search Engine Strategies Boston
Webmaster World Forums
"This was a very different kind of SEM/SEO conference. It was the largest conference the SEM/SEO industry has ever put together. From corporate marketing crowd to the mom & pop seo's, there was a diversification present we have not seen before."

Overview of what makes a site SE friendly
ihelpyou Forums
"I need to write a brief summary of what makes a site SE friendly. I understand that there are no exact rules, so i need something general."

Search Engine Forums Spotlight courtesy Search Engine Guide.

Search Headlines

NOTE: Article links often change. In case of a bad link, use the publication's search facility, which most have, and search for the headline.

Online portals news
Yahoo rumoured to be targeting Espotting for purchase/. Mar 17 2003 12:31PM GMT
Internet features
Should You Spam?: Advice for Uncertain Businesses/.
WebTalkGuys Radio Mar 17 2003 10:28AM GMT
Online portals news
Comcast Learned From Excite@Home Experience/.
New York Times Mar 17 2003 7:52AM GMT
Yahoo's Paid Video to Supply Sports, Finance and 'Survivor'/.
New York Times Mar 17 2003 7:52AM GMT
Online search engines news
Search Engines Are Picking Up Steam/.
Business Week Mar 17 2003 2:07AM GMT
new article examining Google's content targeting/.
Traffick Mar 16 2003 6:26AM GMT
'Google Stalkers' Troll for Lost Acquaintances/.
Yahoo Mar 15 2003 12:22PM GMT
Search Engine Optimization Campaign Results and Expectations/.
Search Engine Guide Mar 15 2003 11:39AM GMT
Online portals news
What if Netscape had won?/.
CNET Mar 14 2003 12:16PM GMT
Online search engines news
Keywords in Hyperlinks Improve Search Engine Ranking/.
Search Engine Guide Mar 14 2003 11:46AM GMT
Online portals news
Yahoo Launches Personals Ad Blitz/. Mar 14 2003 11:31AM GMT
XML and metadata news
Reporter Takes His Weblog to War/.
Wired News Mar 14 2003 10:43AM GMT
Online marketing news
The explainer: internet advertising/.
Guardian Unlimited Mar 14 2003 9:45AM GMT
Cut Online Ad Costs by 90% & Raise Sales - 5 Tips for Search Marketing/. Mar 14 2003 9:03AM GMT
powered by

About the author

Chris Sherman is a frequent contributor to several information industry journals. He's written several books, including The McGraw-Hill CD ROM Handbook and The Invisible Web: Uncovering Information Sources Search Engines Can't See, co-authored with Gary Price. Chris has written about search and search engines since 1994, when he developed online searching tutorials for several clients. From 1998 to 2001, he was's Web Search Guide.