SDI Seminar

Speaker: Christos Faloutsos, Carnegie Mellon University

Date: September 16, 1999
Time: Noon
Place: Wean Hall 8220

On Power-Law Relationships of the Internet Topology


Despite the apparent randomness of the Internet, we discover some surprisingly simple power-laws of the Internet topology. %we show that these power-laws These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period. We show that our power-laws fit the real data very well resulting in correlation coefficients of 96% or higher.

Our observations provide a novel perspective of the structure of the Internet. The power-laws describe concisely skewed distributions of graph properties such as the node outdegree. In addition, these power-laws can be used to estimate important parameters such as the average neighborhood size, and facilitate the design and the performance analysis of protocols. Furthermore, we can use them to generate and select realistic topologies for simulation purposes.


Christos Faloutsos received the B.Sc. degree in Electrical Engineering (1981) from the National Technical University of Athens, Greece and the M.Sc. and Ph.D. degrees in Computer Science from the University of Toronto, Canada. Prof. Faloutsos is currently a faculty member at Carnegie Mellon University. Prior to joining CMU he was on the faculty of the department of Computer Science at University of Maryland, College Park. He has spent sabbaticals at IBM- Almaden and AT&T Bell Labs. He has worked as a consultant to several companies, including AT&T Research, Lucent, SUN.

He has received the Presidential Young Investigator Award by the National Science Foundation (1989), two ``best paper'' awards (SIGMOD 94, VLDB 97), and four teaching awards. He has published over 70 refereed articles, one monograph, and has filed for four patents. His research interests include physical data base design, searching methods for text, geographic information systems indexing methods for multimedia databases and data mining.