(Advanced) Topics in Network Science

Relational data are ubiquitous in nature and are often modeled as graphs. From these graphs, we can calculate properties of interest, such as connectedness or clustering. However, to interpret the results, we need to compare them with something; otherwise, it is impossible to tell whether, for example, a clustering coefficient of 0.3 is high or low. For this reason, graph models have been developed that generate graphs in a maximally random way, given some minimal information. Comparing the properties of these graph models with those of real-world graphs allows for meaningful interpretation. In this seminar topic, you will discuss three simple graph models, explain their underlying assumptions, and explore how they can be used in applications.

While full spectral information from graph operators is highly descriptive, computing it is often prohibitively expensive for large networks. Power spectra, also known as densities of states, offer functional descriptors that can be approximated quickly through functional decompositions. This topic aims to examine how these statistics are formalized and computed, and how they can be used to generate topological features for machine-learning algorithms.

Graph coarsening condenses large networks by merging similar adjacent nodes into supernodes, effectively reducing dimensionality. This approach allows key information to be extracted while maintaining essential properties, such as spectral information or graph convolutional network layer outputs. This topic aims to explore various coarsening algorithms, their computational gains, and examples of practical applications.

Graph sparsification reduces the complexity of large, dense networks by creating a sparser representation while preserving key structural properties. This technique is essential for improving the scalability of graph algorithms and graph neural networks. In this topic, you will investigate various sparsification approaches, with a particular focus on spectral sparsification, and their impact on downstream applications and performance.

Many real-world networks contain groups of nodes that are more strongly connected to each other than to the rest of the network. Community detection aims to uncover such modular structure without knowing the groups in advance.

In this topic, you will study how the eigenvalues and eigenvectors of matrices associated with a graph can be used to find communities. Starting from the problem of partitioning a graph while cutting as few—or as little weighted—edges as possible, you will see how difficult discrete optimisation problems can be relaxed into tractable spectral problems. You will compare different notions of graph cuts and understand why they lead to different versions of the graph Laplacian and different spectral clustering algorithms. Finally, you will investigate how the basic idea extends from splitting a network into two groups to finding several communities.

Suggested literature:

• U. von Luxburg (2007), A Tutorial on Spectral Clustering, Statistics and Computing 17, 395–416.
• J. Shi & J. Malik (2000), Normalized Cuts and Image Segmentation, IEEE TPAMI 22(8), 888–905.

Relational data are ubiquitous in nature and are often modeled as graphs. Examples include social networks and biological networks such as protein–protein interaction networks. Understanding this kind of data is difficult because graphs are irregular and can have arbitrary topologies. One may therefore be interested in clustering nodes into different partitions to help uncover the organization of a network. One way to do this is by using random walks, where a random walker explores the graph by repeatedly moving from its current node to one of its neighbors. This can be used for clustering because nodes that are densely connected in the graph appear together frequently in the random walk. In your seminar paper, you will make this intuition explicit and survey the literature on applications of clustering with random walks.

The Critical Node Problem (CNP) seeks to identify a small set of nodes whose removal maximally disconnects a network, according to some chosen criterion. Because finding an optimal solution is NP-hard for most formulations, heuristic and approximation methods are frequently used for real-world applications such as network robustness studies or epidemic control. This topic aims to evaluate different heuristic approaches, starting from methods such as centrality measures and genetic algorithms, alongside appropriate target connectivity metrics.

Networks are often not immutable: percolation theory studies how the addition or removal of edges from a network affects its overall connectivity. In particular, it describes the emergence of a sharp percolation threshold at which the network abruptly transitions from a disconnected to a connected state. This is relevant to a number of applications, from disease transmission, where we want to remain below the threshold, to communication networks, where we want to remain above it. In this topic, you will learn how the concept of a percolation threshold is given a precise mathematical definition and explore how it may be used in a real-world application of your choice.

Illustration: Bond-percolation animation showing the emergence of a giant component.

Graph neural networks (GNNs) have emerged as a powerful framework for learning from graph-structured data, with applications in social networks, recommendation systems, biological networks, and scientific computing. This topic focuses on the theoretical foundations of GNN training, with particular emphasis on understanding the convergence behavior of gradient descent algorithms. Topics of interest include optimization dynamics, convergence guarantees, and the influence of network architecture on training efficiency and performance.

Signal processing on images supports a variety of tasks, notably including the removal of noise from an image. However, classical filters such as Gaussian filters can blur edges, smoothing the image by reducing fidelity around boundaries. Graph signal processing can help address this problem by defining edge weights and filtering with the graph Laplacian, preserving global structure while removing noise with strong local variations.

This seminar topic introduces the fundamentals of graph signal sampling and reconstruction as an extension of classical signal processing to graph-structured data. The main objective is to compare two or three graph signal sampling and reconstruction methods, both from a theoretical perspective and through their application to real-world graph datasets. You will analyze the strengths, limitations, and practical performance of the selected methods to identify the trade-offs between different approaches.

Graph signal processing (GSP) provides a powerful mathematical framework for analyzing and processing signals defined on irregular graph domains, such as social networks, biological systems, and traffic networks. In this topic, you will investigate sampling strategies for graph signals, where signal observations are collected from a subset of nodes with the goal of accurately reconstructing the original graph signal. The focus is on analyzing different sampling schemes that guarantee unique, stable, and robust signal recovery under various graph structures and signal models.

Collective action refers to situations where many people need to coordinate their individual actions to achieve a public good. These situations are often modeled as games with a large number of players, allowing the analysis of equilibria and stability. Further complexities arise when we account for the structure of the social network, allowing us to draw conclusions about game outcomes from the structure of the network.

Complex systems and relational data can be abstracted as dynamical processes on networks. A dynamical embedding is a node-embedding technique that maps nodes closer together if they induce similar dynamical behavior in the network. This technique makes it possible to construct timescale-resolved node-similarity metrics that can be used for dimensionality reduction and for uncovering functional modules in potentially disassortative communities, in which nodes connect mostly to nodes from a different community. Applications of this technique include social networks, diffusive dynamics, and neural networks.

Common models of opinion dynamics assume that interactions between people are exclusively pairwise. If we account for group interactions, we can model more complex behavior, but at the cost of some analytical tools available in the pairwise case.

Spiking neural networks (SNNs) are a class of artificial neural networks that more closely mimic the behavior of biological neurons. Unlike traditional artificial neural networks, which use continuous activation functions, SNNs are governed by neuronal dynamics that generate and process discrete events called spikes. These spikes allow SNNs to capture temporal dynamics and process information in a more biologically plausible manner, helping to model and understand the underlying mechanisms of brain function. SNNs are also particularly well suited to tasks involving temporal sequences, such as speech recognition, event-based vision, and robotics, and play a central role in the development of neuromorphic computing systems and more energy-efficient AI models.

Imagine a network of interacting agents, each performing an action with some frequency. If we choose the interaction rules between those agents correctly, they will synchronize spontaneously—without any kind of central authority. This surprising behavior was first illustrated in a model by Mirollo and Strogatz (1990), who sought to explain how some species of fireflies synchronize their flashes. Your task will be to choose a specific example of spontaneous network synchronization and learn the underlying mathematical theory explaining its emergence. From there, depending on your interests, you may explore a real-world application, such as hardware synchronization, or numerically investigate more esoteric phenomena such as resonance or chaos.

Illustration: Fireflies synchronizing their flashes.

Modern single-cell technologies can measure the expression of thousands of genes in large numbers of individual cells. This makes it possible to investigate heterogeneous cell populations and continuous biological processes such as differentiation and development. At the same time, single-cell data are high-dimensional, noisy, and affected by numerous technical effects, making their analysis a substantial computational challenge.

In this topic, you will first learn the basic biology and standard computational workflow of single-cell RNA-sequencing analysis, including preprocessing, normalisation, dimensionality reduction, and the construction of neighbourhood graphs. You will then study how these graphs are used by methods such as diffusion maps and UMAP to uncover low-dimensional structure and visualise relationships between cells.

Finally, you will investigate one aspect in more depth: for example, how choices in neighbourhood-graph construction affect the result, how pseudotime can be used to reconstruct developmental trajectories, how UMAP, t-SNE, and diffusion maps differ, or how methods such as Harmony account for batch effects.

Suggested literature:

• M. D. Luecken & F. J. Theis (2019), Current Best Practices in Single-Cell RNA-seq Analysis: A Tutorial, Molecular Systems Biology 15, e8746.
• L. Heumos et al. (2023), Best Practices for Single-Cell Analysis Across Modalities, Nature Reviews Genetics 24, 550–572.

How can we describe the shape of a data set when all we are given is a cloud of points in a high-dimensional space? Topological data analysis provides tools for extracting qualitative geometric information—such as connected components, loops, and higher-dimensional holes—from data.

The basic idea is to replace the point cloud with a combinatorial object that records which points are close to each other. Instead of using only a graph, we can also fill in triangles, tetrahedra, and their higher-dimensional analogues. Such an object is called a simplicial complex. By gradually increasing the distance at which points are connected, we obtain a sequence of simplicial complexes describing the data at different scales.

Using persistent homology, you will learn how to track topological features as the scale changes and distinguish structures that persist over many scales from short-lived features. You will encounter Vietoris–Rips filtrations and the basic linear algebra behind homology, and can then explore efficient computation, applications of persistence in downstream data-analysis tasks, or related constructions such as the Mapper algorithm.

Note: This is one of the more mathematically abstract seminar topics. No prior knowledge of topology is required, but you should be comfortable with linear algebra and willing to work with abstract mathematical definitions.

Suggested literature:

• G. Carlsson (2009), Topology and Data, Bulletin of the AMS 46(2), 255–308.
• N. Otter et al. (2017), A Roadmap for the Computation of Persistent Homology, EPJ Data Science 6, 17.