# 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
http://dbpubs.stanford.edu:8090/pub/2003-20
A Stanford University Technical Report, authored by Taher Haveliwala and Sepandar Kamvar.

Exploiting the Block Structure of the Web for Computing PageRank
http://dbpubs.stanford.edu:8090/pub/2003-17
A Stanford University Technical Report, authored by Sepandar Kamvar, Taher Haveliwala, Christopher Manning and Gene Golub.

## Search Engine Forums Spotlight

Webmaster World Forums
http://www.webmasterworld.com/forum3/10456.htm
"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
http://www.ihelpyouservices.com/forums/t7613/
"This Overture client, small fry though I may be, would definitely pull all advertising on Overture if the relationship were made complete."

ihelpyou Forums
http://www.ihelpyouservices.com/forums/t7614/
"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
http://www.webmasterworld.com/forum33/1437.htm
"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
http://www.webmasterworld.com/forum5/1991.htm
"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
http://www.ihelpyouservices.com/forums/t7411/
"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.