  The $\beta$-model of random graphs is an exponential family model with the
degree sequence as a sufficient statistic. In this paper, we contribute three
key results. First, we characterize conditions that lead to a quadratic time
algorithm to check for the existence of MLE of the $\beta$-model, and show that
the MLE never exists for the degree partition $\beta$-model. Second, motivated
by privacy problems with network data, we derive a differentially private
estimator of the parameters of $\beta$-model, and show it is consistent and
asymptotically normally distributed - it achieves the same rate of convergence
as the nonprivate estimator. We present an efficient algorithm for the private
estimator that can be used to release synthetic graphs. Our techniques can also
be used to release degree distributions and degree partitions accurately and
privately, and to perform inference from noisy degrees arising from contexts
other than privacy. We evaluate the proposed estimator on real graphs and
compare it with a current algorithm for releasing degree distributions and find
that it does significantly better. Finally, our paper addresses shortcomings of
current approaches to a fundamental problem of how to perform valid statistical
inference from data released by privacy mechanisms, and lays a foundational
groundwork on how to achieve optimal and private statistical inference in a
principled manner by modeling the privacy mechanism; these principles should be
applicable to a class of models beyond the $\beta$-model.
