Isolating Subgraph Algorithm An approach to Personalized Search Engines

The technology of web search engines has both practical and academic importance. As more and more information becomes available on the web, the need for good search engines increases. In this thesis we will mostly discuss Google, the dominant search engine today, mainly because there is more information available on their algorithms than other web search engines. We look briey at the main components of the Google search engine and then continue to look at the PageRank algorithm. The algorithm considers the web modeled as a graph, each node is a web page and each directed edges is a hyperlink between two web pages. A random surfer is then modelled as mak-ing a random walk over the set of nodes in the graph. This markovian random walk will give us a stationary distribution on the set of nodes which is the PageRank of each page. We will use the PageRank vector to nd ows in the graph. The PageRank of each page is then the sum of all ows to that page and equals PageRank. This Network Flow approach will help us later when we try to construct a personalized search engine. Next we look at ways to collect data from a user, a set of preferred nodes, in order to nd a new PageRank that better ts this specic user. Our goal is to nd a teleport vector so that the ows in the graph better models the user. We formulate an opti