Networks with complex structures and functions are pervasive in the modern world, spanning social, biological and technological systems. One feature common to many such networks is a broad variation in the number of edges incident to each node, and growth by preferential attachment, whereby the rich get richer, has been assumed as an explanatory axiom. I will show that an underlying local optimization mechanism can in fact give rise to preferential attachment. Another complex feature of evolving networks is that exhibit phase transitions, such as the sudden emergence of large-scale connectivity. I show that a variant of the classic Erdos-Renyi model of network formation (using the power of two choices) can alter the location and also the nature of the phase transition, making for an explosive onset of connectivity. Finally, in the past ten years a general theory of networks has been developing, but it applies only to isolated networks. In reality, individual networks are increasingly interdependent (e.g., the Internet and the power grid, globalization of financial markets and of social networks). I show that interactions between different types of networks can actually lower the critical threshold, allowing large-scale connectivity to be achieved with fewer overall connections, with implications for the spread of disease across geographic regions and the design of simple communications networks.