Lecture

Random Walker Model: PageRank

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture introduces the Random Walker Model and its application in the PageRank algorithm. It covers the concept of relevance in web pages, the link matrix, and the computation of PageRank using a random walker. The lecture explains the importance of PageRank in web search and its practical computation, including the iterative computation process. It also delves into the Hyperlink-Induced Topic Search (HITS) algorithm, which focuses on finding hub and authoritative pages in response to a query. The lecture concludes with a discussion on the Louvain Modularity and Girvan-Newman algorithms for community detection in networks.

Official source

Related concepts (32)

Web crawler

A Web crawler, sometimes called a spider or spiderbot and often shortened to crawler, is an Internet bot that systematically browses the World Wide Web and that is typically operated by search engines for the purpose of Web indexing (web spidering). Web search engines and some other websites use Web crawling or spidering software to update their web content or indices of other sites' web content. Web crawlers copy pages for processing by a search engine, which indexes the downloaded pages so that users can search more efficiently.

Search engine

A search engine is a software system that finds web pages that match a web search. They search the World Wide Web in a systematic way for particular information specified in a textual web search query. The search results are generally presented in a line of results, often referred to as search engine results pages (SERPs). The information may be a mix of hyperlinks to web pages, images, videos, infographics, articles, and other types of files. Some search engines also mine data available in databases or open directories.

PageRank

PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. According to Google: PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.

Deep web

The deep web, invisible web, or hidden web are parts of the World Wide Web whose contents are not indexed by standard web search-engine programs. This is in contrast to the "surface web", which is accessible to anyone using the Internet. Computer scientist Michael K. Bergman is credited with inventing the term in 2001 as a search-indexing term. Deep web sites can be accessed by a direct URL or IP address, but may require entering a password or other security information to access actual content.

Yahoo! Search

Yahoo! Search is a Yahoo! internet search provider that uses Microsoft's Bing search engine to power results, since 2009, apart from four years with Google from 2015 until the end of 2018. Originally, "Yahoo! Search" referred to a Yahoo!-provided interface that sent queries to a searchable index of pages supplemented with its directory of websites. The results were presented to the user under the Yahoo! brand. Originally, none of the actual web crawling and data housing was done by Yahoo! itself.

Related lectures (50)

Fixed Points in Graph Theory

Focuses on fixed points in graph theory and their implications in algorithms and analysis.

Link-based Ranking: Fundamentals and Algorithms

Covers the fundamentals and algorithms of link-based ranking, including anchor text indexing, PageRank, HITS, and practical implementations.

Graphical Models: Representing Probabilistic Distributions

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Link-based ranking: PageRank & HITS

Explores link-based ranking through PageRank and HITS algorithms, covering practical examples and challenges in web search and ranking methods.

Connectivity in Graph Theory