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

What you will do: Introduce three simple random graph models and the information each preserves or assumes. Compare the network properties they produce, then explain how such models can serve as reference points for interpreting an empirical network.

Suggested literature:

• M. E. J. Newman (2003), The Structure and Function of Complex Networks, SIAM Review 45(2), 167–256.
• B. K. Fosdick et al. (2018), Configuring Random Graph Models with Fixed Degree Sequences, SIAM Review 60(2), 315–355.

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.

What you will do: Define spectral density and power spectrum signatures, explain how each is computed or approximated, and discuss what graph information the resulting descriptors capture. Use examples from the literature to assess their computational cost and possible use as features in machine learning.

Suggested literature:

• K. Dong et al. (2019), Network Density of States, Proceedings of KDD 2019.
• K. Y. Djima & K. M. Yim (2025), Power Spectrum Signatures of Graphs, arXiv:2503.09660.

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.

What you will do: Introduce the basic coarsening operation and survey methods that preserve different graph properties. Compare a spectral approach with a neural-network-based approach, and discuss their computational benefits, limitations, and example applications.

Suggested literature:

• Y. Jin et al. (2020), Graph Coarsening with Preserved Spectral Properties, Proceedings of AISTATS 2020, 4452–4462.
• C. Cai et al. (2021), Graph Coarsening with Neural Networks, Proceedings of ICLR 2021.

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.

What you will do: Explain which graph properties different sparsification methods aim to preserve, with particular attention to spectral similarity. Compare representative methods and discuss the trade-off between reducing the number of edges and retaining performance on a chosen downstream task.

Suggested literature:

• D. A. Spielman & S.-H. Teng (2011), Spectral Sparsification of Graphs, SIAM Journal on Computing 40(4), 981–1025.
• Y. Chen et al. (2023), Demystifying Graph Sparsification Algorithms in Graph Properties Preservation, Proceedings of the VLDB Endowment 17(3), 427–440.

Optimal transport (OT) is a mathematical framework for comparing probability distributions by computing a transport plan that matches their mass at minimal cost. For distributions supported on a metric space, such as point clouds, the cost of moving mass between two points can be chosen as their distance. Comparing two graphs with OT corresponds to matching their nodes, but no distance is defined between nodes of two different graphs. The Gromov–Wasserstein (GW) distance addresses this by using the pairwise distances within each graph, such as shortest-path distances, and matching nodes so that matched pairs have similar distances in both graphs. The Fused Gromov–Wasserstein (FGW) distance extends this to graphs with node features by combining a Wasserstein term on the features with a GW term on the structure.

What you will do: Introduce OT and the Wasserstein distance for point clouds, and explain how the Gromov–Wasserstein distance compares graphs using only distances within each graph. Then show how FGW combines node features and graph structure, discuss how it is computed in practice, and illustrate its use in down-stream tasks such as graph classification or clustering using reported results or a small example.

Suggested literature:

• T. Vayer et al. (2019), Optimal Transport for Structured Data with Application on Graphs, Proceedings of ICML 2019.
• G. Peyré & M. Cuturi (2019), Computational Optimal Transport, Foundations and Trends in Machine Learning 11(5–6), 355–607.

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.

What you will do: Derive spectral clustering from a relaxation of graph-cut minimisation. Explain how different cut objectives lead to different Laplacians, and show how the two-way partitioning idea extends to 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.

What you will do: Introduce random walks and community structure, then explain how walk behavior can define a useful partition. Compare at least two random-walk-based community detection approaches and discuss where they have been applied.

Suggested literature:

• J.-C. Delvenne et al. (2010), Stability of Graph Communities Across Time Scales, Proceedings of the National Academy of Sciences 107(29), 12755–12760.
• M. Rosvall & C. T. Bergstrom (2008), Maps of Random Walks on Complex Networks Reveal Community Structure, Proceedings of the National Academy of Sciences 105(4), 1118–1123.

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.

What you will do: Define a connectivity objective for node removal and survey heuristic ways to choose a small set of critical nodes. Compare representative approaches, such as centrality-based selection and a search heuristic, using the objective and computational cost to judge their strengths and limitations.

Suggested literature:

• M. Lalou et al. (2018), The Critical Node Detection Problem in Networks: A Survey, Computer Science Review 28, 92–117.
• Y. Zhou & J.-K. Hao (2017), A Fast Heuristic Algorithm for the Critical Node Problem, Proceedings of the GECCO 2017 Companion.

Networks are often not immutable: percolation theory studies how the addition or removal of edges or nodes 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.

What you will do Learn how these ideas are given a precise mathematical definition as either bond or node percolation. Define the concepts of a percolation threshold and giant component, and and use that to explore the connectivity transition in a real-world application.

Starting references

• Cohen, R. & Havlin, S. Percolation in Complex Networks. Complex Media and Percolation Theory 419–431 (2021). doi:10.1007/978-1-0716-1457-0_383.
• Newman, M. E. J. Networks, Chapter 15: Percolation and network resilience, 2nd ed., 569–606 (Oxford University Press, 2018).
• Sahimi, M. Applications of Percolation Theory, 2nd ed. (Springer, Cham, 2023).
• [Animation] Bond-percolation animation showing the emergence of a giant component.
• [Video] Percolation: A Mathematical Phase Transition. (2022). https://www.youtube.com/watch?v=a-767WnbaCQ

In graph-level tasks, graph neural networks (GNNs) aim to predict predict graph properties based on the graph’s connectivity structure and some additional input features. One prominent example for this is the prediction of chemical properties for individual molecules. Most GNNs designed for this purpose follow the message passing paradigm, where the GNN functions by exchanging messages between neighboring nodes.

What you will do: Explain what the message-passing paradigm for GNNs is, how it follows intuitively from the color-refinement algorithm, and how this characterizes the expressivity of the GNN. Then you will survey the strength and weaknesses of this paradigm, and may end with a survey of what message passing GNNs are able to achieve in applications.

Suggested literature:

• Martin Grohe et al. (2017), Color Refinement and its Applications.
• Justin Gilmer et al. (2017), Neural message passing for quantum chemistry, International conference on machine learning, Pmlr.

In many applications, such as sensoring, data can be modeled as a graph together with a signal that lives on the nodes of this graph. Graph signal processing (GSP) is the field that, as the name suggests, studies what the best way of processing these graph signals is. One prominent tool for this are spectral filters. Graph neural networks (GNNs) build upon the insights from spectral filtering in GSP and combine them with the benefits of machine learning (ML). While GNN research is dominated by the ML paradigm, it is useful to look at GNNs from the GSP perspective to understand how they function.

What you will do: Introduce spectral filters from the perspective of GSP, and explain how they can be used to promote or supress aspects of a graph signal. Then you will make the step towards GNNs, explain how spectral filters are built into these models, and understand what benefits GNNs bring of standard GSP tools.

Suggested literature:

• Elvin Isufi et al. (2024), Graph filters for signal processing and machine learning on graphs, IEEE Transactions on Signal Processing 72, 4745-4781.
• T. N. Kipf & M. Welling (2017), Semi-Supervised Classification with Graph Convolutional Networks, Proceedings of ICLR 2017.

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.

What you will do: Introduce a representative GNN and explain how gradient descent trains its parameters. Review a convergence result for a tractable GNN model, state the assumptions under which it holds, and discuss what the analysis suggests about graph structure or architecture during training.

Suggested literature:

• T. N. Kipf & M. Welling (2017), Semi-Supervised Classification with Graph Convolutional Networks, Proceedings of ICLR 2017.
• D. Patel et al. (2025), Convergence of Gradient Based Training for Linear Graph Neural Networks, arXiv:2501.14440.

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.

What you will do: Explain how an image can be represented as a graph and how graph-based smoothing uses that representation. Review two graph-based filtering approaches and compare their treatment of noise and image edges with a conventional image filter, drawing on reported results or a small example.

Suggested literature:

• D. I. Shuman et al. (2013), The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains, IEEE Signal Processing Magazine 30(3), 83–98.
• A. Ortega et al. (2018), Graph Signal Processing: Overview, Challenges, and Applications, Proceedings of the IEEE 106(5), 808–828.

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.

What you will do: Explain graph signals and the conditions under which observations at selected nodes permit reconstruction. Compare two or three sampling and reconstruction methods using their assumptions, recovery guarantees, and reported or reproduced results on real graph data.

Suggested literature:

• Y. Tanaka et al. (2020), Sampling Signals on Graphs: From Theory to Applications, IEEE Signal Processing Magazine 37(6), 14–30.
• A. Gadde et al. (2014), Active Semi-Supervised Learning Using Sampling Theory for Graph Signals, Proceedings of KDD 2014.

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.

What you will do: Introduce graph signals and explain how choosing a subset of observed nodes affects recovery. Compare exact or designed sampling with random sampling, focusing on the assumptions for unique reconstruction and the effect of noise.

Suggested literature:

• S. Chen et al. (2015), Discrete Signal Processing on Graphs: Sampling Theory, IEEE Transactions on Signal Processing 63(24), 6510–6523.
• G. Puy et al. (2018), Random Sampling of Bandlimited Signals on Graphs, Applied and Computational Harmonic Analysis 44(2), 446–475.

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.

What you will do: Review a threshold model of collective action and explain how participation decisions can depend on the actions or communication of others. Then examine a network-based coordination model and discuss how its assumptions about social ties affect possible outcomes.

Suggested literature:

• M. Granovetter (1978), Threshold Models of Collective Behavior, American Journal of Sociology 83(6), 1420–1443.
• M. S.-Y. Chwe (2000), Communication and Coordination in Social Networks, The Review of Economic Studies 67(1), 1–16.

Boolean networks consist of nodes that have either active (1, “ON”) or inactive (0, “OFF”) states, and whose dynamics are determined by their interaction through logical update functions. Networks are a natural representation of biological systems, but modeling the dynamics of biological networks is typically challenging due to the high number and wide variety of relevant interactions. Continuous modeling is often thwarted by insufficient experimental knowledge about the necessary parameters or by sheer computational intractability. Boolean networks constitute a modeling alternative which, despite its intrinsic simplicity, exhibits good predictive power and considerable dynamical richness, managing to capture emergent behaviors of real world biological systems. Applications include systems at several levels of biological organization, from ecological networks (e.g., predator-prey, pollinator-plant) to molecular networks, like the widely explored Gene Regulatory Networks (GRNs).

What you will do: You will learn how to represent and simulate the dynamics of a Boolean Network, as well as the different types of update functions and update schemes. Afterwards, you will choose a Boolean network from a biological system, simulate its dynamics in search of attractor states, which might represent some biological reality (cell type, gene expression profile, ecological state). To that end, you will learn how to explore dynamics through an extensive exploration of the state space, as well as more advanced techniques, such as the parity-expanded hypergraph or the algebraic state space representation of Boolean dynamics.

Suggested literature:

• T. Helikar et al. (2011), Boolean Modeling of Biochemical Networks, The Open Bioinformatics Journal 5, 16–25.
• J. D. Schwab et al. (2020), Concepts in Boolean Network Modeling: What Do They All Mean?, Computational and Structural Biotechnology Journal 18, 571–582.
• S. Bornholdt (2008), Boolean Network Models of Cellular Regulation: Prospects and Limitations, Journal of the Royal Society Interface 5(Suppl. 1), S85–S94.
• J. C. Rozum et al. (2024), Boolean Networks as Predictive Models of Emergent Biological Behaviors, Cambridge University Press.

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.

What you will do: Introduce hypergraphs as a representation of group interactions and select one opinion or consensus model defined on them. Explain its update rule and discuss a behavior that differs from, or cannot be captured by, a comparable pairwise model.

Suggested literature:

• L. Neuhäuser et al. (2021), Consensus Dynamics and Opinion Formation on Hypergraphs, arXiv:2105.01369.
• A. Hickok et al. (2022), A Bounded-Confidence Model of Opinion Dynamics on Hypergraphs, SIAM Journal on Applied Dynamical Systems 21(1), 1–32.

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.

What you will do: Introduce a simple spiking-neuron model, such as the leaky integrate-and-fire model, and explain how its dynamics produce spikes. Review how neurons communicate in an SNN, along with common coding and training ideas, then discuss selected strengths, limitations, and applications.

Suggested literature:

• W. Gerstner et al. (2014), Neuronal Dynamics: From Single Neurons to Networks and Models of Cognition, Cambridge University Press.
• K. Yamazaki et al. (2022), Spiking Neural Networks and Their Applications: A Review, Brain Sciences 12(7), 863.

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 used to describe how certain fireflies synchronize their flashes.

What you will do: Choose a specific example of spontaneous network synchronization and learn the underlying mathematical theory explaining its emergence. From there, depending on your interests, there are multiple options to pursue the topic further:

1. One option is to explore a real-world application (which may range from ad hoc networks to ecology to power grids).
2. If you prefer a more mathematical direction, you may explore the effect of symmetries on synchronization.
3. If you prefer writing code, yet another direction, would be to numerically investigate more esoteric phenomena such as resonance or chaos.

Starting references

• Mirollo, R. E. & Strogatz, S. H. Synchronization of Pulse-Coupled Biological Oscillators. SIAM J. Appl. Math. 50, 1645–1662 (1990).
• Hong, Y.-W., & Scaglione, A. (2005). A scalable synchronization protocol for large scale sensor networks and its applications. IEEE Journal on Selected Areas in Communications, 23(5), 1085–1099.
• Sorrentino et al., Complete Characterization of the Stability of Cluster Synchronization in Complex Dynamical Networks (Science Advances, 2016)
• Rohden, M. et al., Self-Organized Synchronization in Decentralized Power Grids (PRL, 2012)
• Shahal, S. et al., Synchronization of Complex Human Networks (Nature Communications, 2020)
• [Video] Veritasium, The Secret of Synchronization (YouTube, 2021)
• [Audio] Radiolab, Emergence. (14 August 2007)

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.

What you will do: Explain the biological setting and the main steps of a single-cell RNA-sequencing workflow. Show how a cell-neighbourhood graph supports diffusion maps and UMAP, then examine one of the follow-up questions listed above in more detail.

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.

What you will do: Introduce simplicial complexes, Vietoris–Rips filtrations, and the idea of persistent homology. Explain how topological features are tracked across scales, then pursue one direction such as computation, a data-analysis application, or the Mapper construction.

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.