Lecture

Social and Information Networks: Ranking

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.

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.

Instructor

Matthias Grossglauser

Matthias Grossglauser is a Professor of Computer and Communication Sciences at EPFL in Lausanne, Switzerland, where he co-directs the Information and Network Dynamics lab. His current research interests center on machine learning, stochastic networks, and discrete choice models, and on their applications in artificial intelligence, reinforcement learning, network science, computational social sciences, and recommender systems. He is also a member of the Federal Communications Commission (ComCom), the indepe

Official source

Related concepts (32)

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.

Social network

A social network is a social structure made up of a set of social actors (such as individuals or organizations), sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods for analyzing the structure of whole social entities as well as a variety of theories explaining the patterns observed in these structures. The study of these structures uses social network analysis to identify local and global patterns, locate influential entities, and examine network dynamics.

Related lectures (64)

Link-based Ranking: Fundamentals and Algorithms

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

Statistical Analysis of Network Data: Structures and Models

Explores statistical analysis of network data, covering graph structures, models, statistics, and sampling methods.

Handling Network Data

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

Graph Mining: Social Networks Analysis

Explores graph mining in social networks, covering modularity algorithms and community detection.

Handling Networks: Graph Theory