Umea University

Researchers across disciplines rely on clustering to uncover meaningful patterns in noisy similarity data. Standard two-step pipelines reduce noise before clustering, introducing arbitrary parameters that often produce misleading structure. We unite noise reduction and clustering through Bayesian community detection, using information theory to balance model complexity and fit. This one-step approach automatically determines the number of clusters, avoids detecting patterns in random data, and makes full use of limited samples. Testing on synthetic benchmarks and gene expression data shows the approach yields more reliable and interpretable results than widely used alternatives, improving data-driven discovery across scientific disciplines where samples are limited or expensive.

Real-world networks have a complex topology with many interconnected elements often organized into communities. Identifying these communities helps reveal the system’s organizational and functional structure. However, network data can be noisy, with incomplete link observations, making it difficult to detect significant community structures as missing data weakens the evidence for specific solutions. Recent research shows that flow-based community detection methods can highlight spurious communities in sparse networks with incomplete link observations. To address this issue, these methods require regularization. In this talk, I will show how a Bayesian approach can be used to regularize flows in networks, reducing overfitting in the flow-based community detection method known as the map equation.

The positive discrepancy of a graph $G$ is the maximum surplus of edges in an induced subgraph of $G$ compared to its expected size. This quantity is closely related to other well studied parameters, such as the minimum bisection and the spectral gap. I will talk about the extremal behavior of the positive discrepancy among graphs with given number of vertices and average degree, uncovering a surprising pattern. This leads to an almost complete solution of a problem of Alon on the minimum bisection and let's us extend the Alon-Boppana bound on the second eigenvalue to dense graphs.

Joint work with Eero Räty and Benny Sudakov.

This talk has been cancelled.