**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Hypergraphs and Link Prediction: Statistical Analysis of Network Data

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.

Login to watch the video

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

In course

Related concepts (114)

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications.

Related lectures (102)

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 .

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).

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.

Bipartite graph

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets and may be thought of as a coloring of the graph with two colors: if one colors all nodes in blue, and all nodes in red, each edge has endpoints of differing colors, as is required in the graph coloring problem.

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.

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

Introduces network data structures, models, and analysis techniques, emphasizing permutation invariance and Erdős-Rényi networks.

Graph Algorithms: Modeling and Traversal

Covers graph algorithms, modeling relationships between objects, and traversal techniques like BFS and DFS.

Graphical Models: Representing Probabilistic Distributions

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

Graph Algorithms II: Traversal and Paths

Explores graph traversal methods, spanning trees, and shortest paths using BFS and DFS.