Umea University

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.