Communications networks and the traffic they carry can be modeled as graphs. For example, each customer is a vertex, and a transaction (e.g., a telephone call) between two customers is an edge. The resulting graphs are quite large: the AT&T voice network carries two to three hundred million calls on a typical business day; over time, the number of customers seen is also two to three hundred million. The induced graphs contain a wealth of information, but standard graph algorithms assume that graphs fit in main memory and do not scale to process such massive graphs efficiently.

I will review one standard model of algorithmic complexity and show how it breaks down for out-of-core data. I will then introduce a newer model that stresses data transfer over computation and demonstrate how it leads to some effective graph algorithms. Finally, I will show some of the data we have been able to analyze as a result.