The broad generality of complex networks allows for a diverse range of applications in sociological, biological, and technological settings. This thesis describes several new tools and methodologies to study network properties and also introduces new network models of various societal phenomena. Following a detailed introduction to the subject, we present new ways to discover Communities, densely interconnected groups inside networks. A new network representation or ''''portrait'' is developed, providing a canonical picture of the network, even if it is too large for traditional visualization. These portraits are also shown to have broad applications to diverse problems, including Graph Isomorphism. Finally, network models of collective social dynamics are developed to understand information spreading, opinion formation and other phenomena intrinsic to human populations.