Graph representations underlie many modern computer applications, capturing the structure of such diverse networks as the Internet, personal associations, roads, sensors, and metabolic pathways. While the static structure of graphs is a well-explored field, a new emphasis is being placed on understanding and representing the way these networks change over time. Current research is delving into graph evolution rate and mechanisms, the impact of specific events on network evolution, and spatial and spatiotemporal patterns. However, systematic support for scalable querying and analytics over evolving graphs still lacks. In this dissertation, we combine the theoretical and practical advances in graph databases and temporal relational databases to formulate an evolving graph model, including a representation and an algebra. With this model we aim to enable systematic support for the evolving graph analysis, heretofore lacking in generality. Our goal is to give users an ability to concisely express a wide range of common analysis tasks. We provide several use cases to motivate our work, and demonstrate how they are supported in our model. We show that our algebra is strictly more expressive than the currently published state of the art and provides additional operations not available to the users today. We also provide a prototype implementation of our model in a distributed system called Portal and conduct an extensive experimental evaluation with real datasets. The results of our experiments show that Portal scales to large evolving graph datasets even on a modest size cluster and outperforms a published baseline, while providing additional functionality not available elsewhere. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com.bibliotheek.ehb.be/en-US/products/dissertations/individuals.shtml.]