  We consider the problem of estimating the edge density of densest $K$-node
subgraphs of an Erd\"os-R\'{e}nyi graph $\mathbb{G}(n,1/2)$. The problem is
well-understood in the regime $K=\Theta(\log n)$ and in the regime
$K=\Theta(n)$. In the former case it can be reduced to the problem of
estimating the size of largest cliques, and its extensions. In the latter case
the full answer is known up to the order $n^{3\over 2}$ using sophisticated
methods from the theory of spin glasses. The intermediate case $K=n^\alpha,
\alpha\in (0,1)$ however is not well studied and this is our focus. We
establish that that in this regime the density (that is the maximum number of
edges supported by any $K$-node subgraph) is ${1\over 4}K^2+{1+o(1)\over
2}K^{3\over 2}\sqrt{\log (n/K)}$, w.h.p. as $n\to\infty$, and provide more
refined asymptotics under the $o(\cdot)$, for various ranges of $\alpha$. This
extends earlier similar results where this asymptotics was confirmed only when
$\alpha$ is a small constant.
  We extend our results to the case of ''weighted'' graphs, when the weights
have either Gaussian or arbitrary sub-Gaussian distributions. The proofs are
based on the second moment method combined with concentration bounds, the
Borell-TIS inequality for the Gaussian case and the Talagrand's inequality for
the case of distributions with bounded support (including the
$\mathbb{G}(n,1/2)$ case). The case of general distribution is treated using a
novel symmetrized version of the Lindeberg argument, which reduces the general
case to the Gaussian case. Finally, using the results above we conduct the
landscape analysis of the related Hidden Clique Problem, and establish that it
exhibits an overlap gap property when the size of the clique is $O(n^{2\over
3})$, confirming a hypothesis stated in a previous related work.
