Lecture

Handling Networks: Graph Theory

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

CS-401: Applied data analysis

This course teaches the basic techniques, methodologies, and practical skills required to draw meaningful insights from a variety of data, with the help of the most acclaimed software tools in the data science world (pandas, scikit-learn, Spark, etc.) ...

Description

This lecture by the instructor covers the fundamentals of handling networks, focusing on graph theory concepts such as nodes, edges, centrality measures, and degree distributions. The lecture delves into types of graphs, including undirected, directed, weighted, and bipartite graphs. It also explores real-world network properties like sparsity, degree distribution, and community structure. Various centrality measures like degree, closeness, betweenness, Katz, and PageRank centrality are explained, highlighting their importance in network analysis.

Instructors (2)

Maria Brbic

Maria Brbic is an assistant professor in computer science at EPFL. Prior to joining EPFL, Maria was a postdoctoral researcher in Computer Science at Stanford University working with Jure Leskovec. She received her PhD degree from University of Zagreb in 2019, while also researching at Stanford University and University of Tokyo. Her research was awarded with the Fulbright Scholarship, L’Oreal UNESCO for Women in Science Scholarship, Branimir Jernej award for outstanding publication in biology and biomedicine, and Josip Loncar Silver Plaque award for the best doctoral dissertation. She has been named a Rising Star in EECS by MIT in 2021. Her research is focused on developing new machine learning methods and applying her methods to advance biomedical research.

Robert West

Robert West is a tenure-track assistant professor of computer science at EPFL, where he heads the Data Science Lab. In his research, he develops and applies techniques in machine learning, computational social science, natural language processing, social network analysis, and data mining. Bob also collaborates closely with the Wikimedia Foundation, in his role as a Wikimedia Research Fellow. Bob’s work has won several awards, including best/outstanding paper awards at ICWSM’21, ICWSM’19, and WWW’13, a best-paper runner-up award at WWW’16, a Google Faculty Research Award, a Facebook Research Award, a Hewlett-Packard Graduate Fellowship, and a Facebook Graduate Fellowship. He is actively involved in the research community, e.g., as an Associate Editor of ICWSM and EPJ Data Science and as a co-founder of the Wiki Workshop (held at WWW and ICWSM) and the Applied Machine Learning Days. Bob received his PhD in Computer Science from Stanford University, his MSc from McGill University, Canada, and his undergraduate degree from Technische Universität München, Germany.[Last updated: 25 Aug 2021]

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

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.

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Related lectures (64)

Handling Networks: Graph Theory

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

Graphical Models: Representing Probabilistic Distributions

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

Handling Network Data

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