Interface 2003

Worm Propagation on Graphs with Heavy-tailed Degree Distribution
Stephan Bohacek, (University of Delaware),


Email worms spread over graphs defined by email address books. In order to study the propagation of email worms, it is necessary to understand the graph over which they spread. The email address book graph and other graphs such as the World Wide Web and Internet routers have received much attention recently. There has been extensive work suggesting that for these graphs, the degree of each node is distributed according to a heavy-tailed distribution. Other work has shown that the World Wide Web and Internet router graph can be decomposed into two basic parts: a highly connected core and lightly connected tendrils. This structure provides insight into worm propagation. This paper will explore these graphs and show how heavy-tailed degree distribution typically leads to a highly connected core. However, we will also see how graphs such as the Internet router graph are not typical. For example, the core is not nearly as connected as the theory leads one to expect. Furthermore, the growth function (the number of nodes visited as a function of the number of “hops” from starting node) is significantly different from that of the typical graph with heavy-tailed degree distribution. Notwithstanding the Internet router graph’s peculiarity, to a worm, the Internet graph appears similar to the typical heavy-tailed degree distribution. A slightly different notion of connectivity leads to an explanation for this behavior.

Take me back to the main conference page.