The accelerated evolution of online social interactions and information systems has brought a marked growth in their complexity. The dynamics of these systems are not entirely regulated or engineered, but are instead governed by hidden structures that form as a result of organic growth, but are neither directly observable nor predictable by design. Understanding these structures is crucial for harnessing the benefits of social and information networks while supporting their health and growth. Leveraging the vast amounts of data generated by the Web and the sciences, Network Science has achieved remarkable progress at identifying and modeling certain hidden structures. However, as datasets become larger, they come with higher levels of noise and represent increasingly complex, multifaceted, and multidimensional structures. Therefore, approaching these problems in a rigorous way is crucial to enable further discoveries. This thesis advances the field by providing insights gained from applying novel, principled approaches to three existing modeling and learning tasks: community detection, network inference, and Internet modeling. It concludes with an illustration of the application of sociological theories to guide the empirical analysis of online social network data, revealing hidden social structures that enable a deeper understanding of our own behavior.