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.