Our paper on The Generalized Mean Densest Subgraph Problem. was accepted to KDD 2021. Join work with Austin Benson and Jon Kleinberg.
The paper covers a generalized framework for dense subgraph detection, that unifies previous objectives such as the k-core problem and the densest subgraph problem. We prove polynomial time algorithms for a certain regime of the problem, as well as faster approximation algorithms based on a generalized “peeling” method.