Lecture

Hypergraphs and Link Prediction: Statistical Analysis of Network Data

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

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications. ...

Description

This lecture covers hypergraphs, including the theory of incidence matrices, complete hypergraphs, connected hypergraphs, bipartite hypergraphs, and subhypergraphs. It also delves into link prediction in undirected networks, addressing the prediction of missing edges and vertex attributes using various scoring methods.

Instructor

Sofia Charlotta Olhede

I am a professor of Statistics at EPFL. I did my PhD in Mathematics at Imperial College London, and graduated in 2003. I was an assistant professor (lecturer) at Imperial College London 2002-2006, and an associate professor (senior lecturer) 2006-2007. In 2007 I moved to University College London and became a full professor. I moved to EPFL in 2019, and in 2018 I became an Institute of Mathematical Statistics Fellow with citation “For seminal contributions to the theory and application of large and heteroge

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

Hypergraph

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, a directed hypergraph is a pair , where is a set of elements called nodes, vertices, points, or elements and is a set of pairs of subsets of . Each of these pairs is called an edge or hyperedge; the vertex subset is known as its tail or domain, and as its head or codomain. The order of a hypergraph is the number of vertices in .

Bipartite hypergraph

In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph. Property B The weakest definition of bipartiteness is also called 2-colorability. A hypergraph H = (V, E) is called 2-colorable if its vertex set V can be partitioned into two sets, X and Y, such that each hyperedge meets both X and Y. Equivalently, the vertices of H can be 2-colored so that no hyperedge is monochromatic.

Vertex cover in hypergraphs

In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph. An equivalent term is a hitting set: given a collection of sets, a set which intersects all sets in the collection in at least one element is called a hitting set. The equivalence can be seen by mapping the sets in the collection onto hyperedges. Another equivalent term, used more in a combinatorial context, is transversal.

Matching in hypergraphs

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph. Recall that a hypergraph H is a pair (V, E), where V is a set of vertices and E is a set of subsets of V called hyperedges. Each hyperedge may contain one or more vertices. A matching in H is a subset M of E, such that every two hyperedges e_1 and e_2 in M have an empty intersection (have no vertex in common).

Hall-type theorems for hypergraphs

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others. Hall's marriage theorem provides a condition guaranteeing that a bipartite graph (X + Y, E) admits a perfect matching, or - more generally - a matching that saturates all vertices of Y. The condition involves the number of neighbors of subsets of Y.

Related lectures (64)

Statistical Analysis of Network Data: Hypergraphs

Introduces hypergraphs, generalizing graphs by allowing subsets of nodes to form edges and exploring their applications in various fields.

Directed Networks & Hypergraphs

Explores directed networks with asymmetric relationships and hypergraphs that generalize graphs by allowing edges to connect any subset of nodes.

Statistical Analysis of Network Data: Structures and Models

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

Graphical Models: Representing Probabilistic Distributions

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

Statistical analysis of network data