Millions of interactions between people take place on the Web everyday. In this work, we utilize data obtained by tracking these interactions on social media sites to study two important aspects of social networks: the way in which connections between people form and evolve over time, and the dynamics of information diffusion on the network. We introduce novel methodologies, algorithms, and mathematical models to analyze observations from rich datasets. Our results validate known sociological theories of link formation and information diffusion at large scale and suggest new ones. We study the formation of links in the network of interactions among people in social media sites from the premise that these networks are inherently different from offline social networks. Online interaction networks are not purely social, but a combination of social and information networks. We introduce mechanisms of link formation that are motivated from sociological theories of social network formation, and are generalized to social-information networks. Furthermore, we study how the communication patterns of connected users of social media sites change as a response to new connections arriving to the network and compare our results to the predictions that various sociological theories would suggest. There is an intuitive sense in which the network of interactions among people is related to how information spreads on the network. In this work, we show that this relationship is present in both directions. That is, the structure of the network can determine whether information spreads through the network, and the kind of information users are exposed to can determine the connections among the users. Furthermore, we show that the dynamics of information diffusion can change significantly depending on the topic, which suggests the mechanisms that control information diffusion are context dependent.