Graph Theory in Practice: Part II

Part I of this article, in the January--February issue, discussed some very large structures that can usefully be looked upon as mathematical graphs. In this context a graph is a set of vertices (which are usually represented as dots) and a set of edges (lines between the dots). One large object that can be described in this way is the World Wide Web; its 800 million pages are the vertices of a graph, and links from one page to another are the edges. A second example comes out of Hollywood: The vertices are 225,000 actors, and an edge connects any two actors who have appeared in a feature film together. Although graph theory has a history of two centuries and more, only in recent years has it been applied routinely to structures like these, with many thousands or millions of vertices and edges. Studying such enormous graphs is by no means easy. The Hollywood collaboration graph just barely fits in the memory of a large computer. The Web, a few orders of magnitude larger, requires all the resources of the Internet to keep track of its tentacles. Certain other graphs are even bigger. The human acquaintanceship graph, with a vertex for every person on earth and edges linking all those who know each other, may never be recorded beyond a few small, sampled regions. Even when the vertices and edges of a large graph can be catalogued in full detail, gaining a deeper understanding of the graphs structure still calls for something more. Whats needed is a mathematical theory or model. Typically this takes the form of an algorithm for generating new graphs that share certain properties of the graph under examination: You understand the original graph by building structures that resemble it. Part II of this article looks at a few such models.