Google's Pagerank and Beyond: The Science of Search Engine Rankings

by Langville, Amy N.; Meyer, Carl D.

• ISBN13: 9781400830329
• ISBN10: 140083032X
• Copyright: 2009-06-22
• Publisher: Princeton Univ Pr

Summary

Why doesn't your home page appear on the first page of search results, even when you query your own name? How do other Web pages always appear at the top? What creates these powerful rankings? And how? The first book ever about the science of Web page rankings,Google's PageRank and Beyondsupplies the answers to these and other questions and more. The book serves two very different audiences: the curious science reader and the technical computational reader. The chapters build in mathematical sophistication, so that the first five are accessible to the general academic reader. While other chapters are much more mathematical in nature, each one contains something for both audiences. For example, the authors include entertaining asides such as how search engines make money and how the Great Firewall of China influences research. The book includes an extensive background chapter designed to help readers learn more about the mathematics of search engines, and it contains several MATLAB codes and links to sample Web data sets. The philosophy throughout is to encourage readers to experiment with the ideas and algorithms in the text. Any business seriously interested in improving its rankings in the major search engines can benefit from the clear examples, sample code, and list of resources provided. Many illustrative examples and entertaining asides MATLAB code Accessible and informal style Complete and self-contained section for mathematics review

Table of Contents

Preface	p. ix
Introduction to Web Search Engines	p. 1
A Short History of Information Retrieval	p. 1
An Overview of Traditional Information Retrieval	p. 5
Web Information Retrieval	p. 9
Crawling, Indexing, and Query Processing	p. 15
Crawling	p. 15
The Content Index	p. 19
Query Processing	p. 21
Ranking Webpages by Popularity	p. 25
The Scene in 1998	p. 25
Two Theses	p. 26
Query-Independence	p. 30
The Mathematics of Google's PageRank	p. 31
The Original Summation Formula for PageRank	p. 32
Matrix Representation of the Summation Equations	p. 33
Problems with the Iterative Process	p. 34
A Little Markov Chain Theory	p. 36
Early Adjustments to the Basic Model	p. 36
Computation of the PageRank Vector	p. 39
Theorem and Proof for Spectrum of the Google Matrix	p. 45
Parameters in the PageRank Model	p. 47
The ¿ Factor	p. 47
The Hyperlink Matrix H	p. 48
The Teleportation Matrix E	p. 49
The Sensitivity of PageRank	p. 57
Sensitivity with respect to ¿	p. 57
Sensitivity with respect to H	p. 62
Sensitivity with respect to vT	p. 63
Other Analyses of Sensitivity	p. 63
Sensitivity Theorems and Proofs	p. 66
The PageRank Problem as a Linear System	p. 71
Properties of (I -- ¿S)	p. 71
Properties of (I -- ¿H)	p. 72
Proof of the PageRank Sparse Linear System	p. 73
Issues in Large-Scale Implementation of PageRank	p. 75
Storage Issues	p. 75
Convergence Criterion	p. 79
Accuracy	p. 79
Dangling Nodes	p. 80
Back Button Modeling	p. 84
Accelerating the Computation of PageRank	p. 89
An Adaptive Power Method	p. 89
Extrapolation	p. 90
Aggregation	p. 94
Other Numerical Methods	p. 97
Updating the PageRank Vector	p. 99
The Two Updating Problems and their History	p. 100
Restarting the Power Method	p. 101
Approximate Updating Using Approximate Aggregation	p. 102
Exact Aggregation	p. 104
Exact vs. Approximate Aggregation	p. 105
Updating with Iterative Aggregation	p. 107
Determining the Partition	p. 109
Conclusions	p. 111
The HITS Method for Ranking Webpages	p. 115
The HITS Algorithm	p. 115
HITS Implementation	p. 117
HITS Convergence	p. 119
HITS Example	p. 120
Strengths and Weaknesses of HITS	p. 122
HITS's Relationship to Bibliometrics	p. 123
Query-Independent HITS	p. 124
Accelerating HITS	p. 126
HITS Sensitivity	p. 126
Other Link Methods for Ranking Webpages	p. 131
SALSA	p. 131
Hybrid Ranking Methods	p. 135
Rankings based on Traffic Flow	p. 136
The Future of Web Information Retrieval	p. 139
Spam	p. 139
Personalization	p. 142
Clustering	p. 142
Intelligent Agents	p. 143
Trends and Time-Sensitive Search	p. 144
Privacy and Censorship	p. 146
Library Classification Schemes	p. 147
Data Fusion	p. 148
Resources for Web Information Retrieval	p. 149
Resources for Getting Started	p. 149
Resources for Serious Study	p. 150
The Mathematics Guide	p. 153
Linear Algebra	p. 153
Perron-Frobenius Theory	p. 167
Markov Chains	p. 175
Perron Complementation	p. 186
Stochastic Complementation	p. 192
Censoring	p. 194
Aggregation	p. 195
Disaggregation	p. 198
Glossary	p. 201
Bibliography	p. 207
Index	p. 219
Table of Contents provided by Publisher. All Rights Reserved.