  The structure of large-scale social networks has predominantly been
articulated using generative models, a form of average-case analysis. This
chapter surveys recent proposals of more robust models of such networks. These
models posit deterministic and empirically supported combinatorial structure
rather than a specific probability distribution. We discuss the formal
definitions of these models and how they relate to empirical observations in
social networks, as well as the known structural and algorithmic results for
the corresponding graph classes.
