  Dense subgraph discovery is a fundamental primitive in graph and hypergraph
analysis which among other applications has been used for real-time story
detection on social media and improving access to data stores of social
networking systems. We present several contributions for localized densest
subgraph discovery, which seeks dense subgraphs located nearby given seed sets
of nodes. We first introduce a generalization of a recent $\textit{anchored
densest subgraph}$ problem, extending this previous objective to hypergraphs
and also adding a tunable locality parameter that controls the extent to which
the output set overlaps with seed nodes. Our primary technical contribution is
to prove when it is possible to obtain a strongly-local algorithm for solving
this problem, meaning that the runtime depends only on the size of the input
set. We provide a strongly-local algorithm that applies whenever the locality
parameter is not too small, and show via counterexample why strongly-local
algorithms are impossible below a certain threshold. Along the way to proving
our results for localized densest subgraph discovery, we also provide several
advances in solving global dense subgraph discovery objectives. This includes
the first strongly polynomial time algorithm for the densest supermodular set
problem and a flow-based exact algorithm for a heavy and dense subgraph
discovery problem in graphs with arbitrary node weights. We demonstrate our
algorithms on several web-based data analysis tasks.
