  Degree distribution models are incredibly important tools for analyzing and
understanding the structure and formation of social networks, and can help
guide the design of efficient graph algorithms. In particular, the Power-law
degree distribution has long been used to model the structure of online social
networks, and is the basis for algorithms and heuristics in graph applications
such as influence maximization and social search. Along with recent measurement
results, our interest in this topic was sparked by our own experimental results
on social graphs that deviated significantly from those predicted by a
Power-law model. In this work, we seek a deeper understanding of these
deviations, and propose an alternative model with significant implications on
graph algorithms and applications. We start by quantifying this artifact using
a variety of real social graphs, and show that their structures cannot be
accurately modeled using elementary distributions including the Power-law.
Instead, we propose the Pareto-Lognormal (PLN) model, verify its
goodness-of-fit using graphical and statistical methods, and present an
analytical study of its asymptotical differences with the Power-law. To
demonstrate the quantitative benefits of the PLN model, we compare the results
of three wide-ranging graph applications on real social graphs against those on
synthetic graphs generated using the PLN and Power-law models. We show that
synthetic graphs generated using PLN are much better predictors of degree
distributions in real graphs, and produce experimental results with errors that
are orders-of-magnitude smaller than those produced by the Power-law model.
