Loci

Introduction

Do you have a fond memory of playing Monopoly and gaining sole ownership of the board's real estate market as your pile of funny money increases? Let's play a different game called Google-opoly which led to billions of dollars, in cold, hard cash! The fundamental ideas in this game were part of what Google's founders, Larry Page and Sergey Brin, developed that led to their successful company. Page and Brin's version of Google-opoly is played on the entire World Wide Web. We'll play on much smaller game boards that involve only a few web pages.

In this article, we will play a game that motivates ideas of the PageRank algorithm introduced by Page and Brin and serves as a cornerstone of their search engine. PageRank is part of what leads to the ordered list of web pages when a query is entered into a search engine. If two pages are equally relevant to the text on which you are searching, why is one page listed above another? PageRank is a measure of the quality of a page and higher ranked pages appear earlier than pages of equal relevance but lower quality. How do we measure such quality? We will learn step by step on small networks and develop the algorithm through playing Google-opoly.

Larry PageSergey Brin
Larry Page (left) and Sergey Brin (right)
Images from http://www.google.com/corporate/execs.html
Contents:

Introduction
Your first game
Your second game
Teleporting
More games
Markov's strategy
Google's game

Authors
Acknowledgements

See Video