COMPUTING SCIENCE

# Graph Theory in Practice: Part I

What is the diameter of the World Wide Web? The answer is *not* 7,927 miles, even though the Web truly is World Wide. According to Albert-László Barabási, Reka Albert and Hawoong Jeong of Notre Dame University, the diameter of the Web is 19.

The diameter in question is not a geometric distance; the concept comes from the branch of mathematics called graph theory. On the Web, you get from place to place by clicking on hypertext links, and so it makes sense to define distance by counting your steps through such links. The question is: If you select two Web pages at random, how many links will separate them, on average? Among the 800 million pages on the Web, there's room to wander down some very long paths, but Barabási *et al.* find that if you know where you're going, you can get just about anywhere in 19 clicks of the mouse.

Barabási's calculation reflects an interesting shift in the style and the technology of graph theory. Just a few years ago it would have been unusual to apply graph-theoretical methods to such an enormous structure as the World Wide Web. Of course just a few years ago the Web didn't exist. Now, very large netlike objects seem to be everywhere, and many of them invite graph-theoretical analysis. Perhaps it is time to speak not only of graph theory but also of graph practice, or even graph engineering.

**IN THIS SECTION**

EMAIL TO A FRIEND :

**Of Possible Interest**

**Technologue**: The Quest for Randomness

**Feature Article**: Twisted Math and Beautiful Geometry

**Feature Article**: Simulating Star Formation on a Galactic Scale