  Preferential attachment --- by which new nodes attach to existing nodes with
probability proportional to the existing nodes' degree --- has become the
standard growth model for scale-free networks, where the asymptotic probability
of a node having degree $k$ is proportional to $k^{-\gamma}$. However, the
motivation for this model is entirely ad hoc. We use exact likelihood arguments
and show that the optimal way to build a scale-free network is to attach most
new links to nodes of low degree. Curiously, this leads to a scale-free
networks with a single dominant hub: a star-like structure we call a super-star
network. Asymptotically, the optimal strategy is to attach each new node to one
of the nodes of degree $k$ with probability proportional to
$\frac{1}{N+\zeta(\gamma)(k+1)^\gamma}$ (in a $N$ node network) --- a stronger
bias toward high degree nodes than exhibited by standard preferential
attachment. Our algorithm generates optimally scale-free networks (the
super-star networks) as well as randomly sampling the space of all scale-free
networks with a given degree exponent $\gamma$. We generate viable realisation
with finite $N$ for $1\ll \gamma<2$ as well as $\gamma>2$. We observe an
apparently discontinuous transition at $\gamma\approx 2$ between so-called
super-star networks and more tree-like realisations. Gradually increasing
$\gamma$ further leads to re-emergence of a super-star hub. To quantify these
structural features we derive a new analytic expression for the expected degree
exponent of a pure preferential attachment process, and introduce alternative
measures of network entropy. Our approach is generic and may also be applied to
an arbitrary degree distribution.
