Fixed-parameter tractability of the mixed-sign k-part minimum edge cut problem on sparse graphs
When applying community detection methods such as modularity, one encounters an optimization problem of the general form “I have a collection of objects that I need to divide into bags, and for each pair there is a cost or benefit associated to putting them in the same bag”. In general, this problem is very hard to solve, but for some particular instances, it is known to be easy when dividing into two bags.
May 1, 2025
Universal lower bound for community structure of sparse graphs
When applying community detection in practice, one of the most commonly used methods is to try to find a partition that achieves a high modularity. Unfortunately, this is not a statistically justified method, and so it is in general unclear how to determine if the partition one finds is actually significant, or just the product of random noise.
Jul 14, 2023