Vast amounts of data are generated each day from applications such as social networks, biological pathways, email graphs, and the word-wide web. This data represents an amazing opportunity for the discovery of interesting, useful, and possibly even life saving new knowledge. Additionally, since the node and edge structures of graph representations can naturally capture the organization and interactions present in many types of data, they are commonly used to represent a wide variety of complex datasets. The analysis, mining, and modeling of these graph datasets have inspired numerous highly active areas of research. This has led to many important applications, including the discovery of new gene and protein functions, anomaly detection in computer networks, and the extraction of significant and influential social groups. However, while there has been much focus on the mining and modeling of graphs in recent years, the vast majority of previous research has dealt with simple, static graph representations. Despite this focus on simple, static graphs, most real world graphs are large-scale, dynamic, and heterogeneous. Their nodes and edges can grow from the thousands to the billions, as well as change across time and have additional information (such as labels, text, weights, images, etc.) associated with them. By disregarding these real-world graph properties, a valuable source of important knowledge and applications is ignored.

In this dissertation, I focus on the mining and modeling of these large-scale, heterogeneous, and time evolving graphs. I introduce several new techniques capable of mining clusters from graphs with greater precision and speed, as well as multiple new dynamic graph modeling algorithms capable of predicting future graph structure and properties such as user communication and sentiment across time.