Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Social and Information Networks: Ranking

In course

COM-308: Internet analytics

Internet analytics is the collection, modeling, and analysis of user data in large-scale online services, such as social networking, e-commerce, search, and advertisement. This class explores a number of the key functions of such online services that have ...

Description

This lecture covers the importance of ranking in social and information networks, focusing on algorithms like PageRank and HITS. It explains how network structure, hyperlinks, and endorsements influence the ranking of web pages. The lecture delves into the challenges of dealing with dangling nodes, the concept of the Google Matrix, and the computation of scores using linear systems and the power method. It also discusses computational optimizations for large-scale web graphs, including the HITS algorithm and other centrality measures like betweenness and closeness centrality.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Matthias Grossglauser

Official source

Related concepts (32)

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.

Centrality

In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.

Katz centrality

In graph theory, the Katz centrality or alpha centrality of a node is a measure of centrality in a network. It was introduced by Leo Katz in 1953 and is used to measure the relative degree of influence of an actor (or node) within a social network. Unlike typical centrality measures which consider only the shortest path (the geodesic) between a pair of actors, Katz centrality measures influence by taking into account the total number of walks between a pair of actors. It is similar to Google's PageRank and to the eigenvector centrality.

Betweenness centrality

In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that either the number of edges that the path passes through (for unweighted graphs) or the sum of the weights of the edges (for weighted graphs) is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex.

Eigenvector centrality

In graph theory, eigenvector centrality (also called eigencentrality or prestige score) is a measure of the influence of a node in a network. Relative scores are assigned to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes. A high eigenvector score means that a node is connected to many nodes who themselves have high scores. Google's PageRank and the Katz centrality are variants of the eigenvector centrality.

Related lectures (32)

Handling Network Data

Explores handling network data, including types of graphs, real-world network properties, and node importance measurement.

Handling Networks: Graph Theory

Covers the fundamentals of handling networks and centrality measures in graph theory.

Handling Networks: Graph Theory

Explores graph theory concepts, centrality measures, and real-world network properties, providing insights into handling diverse types of networks.

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.

Centrality and Hubs