PLEASE CLICK ON COLLOQUIUM TITLE FOR COMPLETE ABSTRACT.  The study of random graphs has been dominated for over fifty years by the Erdos-Renyi (ER) model, wherein edges appear independently and with equal probability. It is by now well-understood that ER random graphs bear very little resemblance to real networks, rendering analytical results for them largely uninformative. After a quick overview of the ER model I will point out its main shortcomings and go over some of the attempts to overcome them. We will see that the main issue is the inherent tension between low-dimensionality, needed for realism, and probabilistic independence, needed for mathematical tractability.   I will then describe recent work aimed at resolving this tension by defining random graphs as maximally random solutions to constrained optimization problems. Along with a strong concentration inequality we establish for the solutions of knapsack-like problems, this allows us to get natural generative models for random graphs which do not assume independence between edges, yet are highly tractable mathematically. As a demonstration of this tractability we prove that “navigability”, in the sense of Kleinberg, is a far more robust property of graphs than previously understood, arising without any coordination between the vertices, almost as soon as sufficient resources are present.