graphicHomeAdvance ProgramAward Anniversary EventCall for PapersConference CommitteeLocal InformationPaper SubmissionProgram committeeRegistrationStudent Travel AwardsTutorialgraphic Sigcomm logoSigcomm'99

On Power-Law Relationships of the Internet Topology

Michalis Faloutsos
U.C. Riverside Dept. of Comp. Science

Petros Faloutsos
U. of Toronto Dept. of Comp. Science

Christos Faloutsos
Carnegie Mellon Univ. Dept. of Comp. Science

Despite the apparent randomness of the Internet, we discover some surprisingly simple power-laws of the Internet topology. 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.

Papers are provided as a service to all by the members of ACM SIGCOMM. Please check this box if you are a SIGCOMM member so we can get an idea of how the service is used.

This paper is available in and .

For information about joining SIGCOMM, follow this link

bar

The referenced paper appears in Computer Communication Review, a publication of ACM SIGCOMM, volume 29, number 4, October 1999.

ACM Copyright Notice: Copyright (c) 1999 by Association for Computing Machinery, Inc. (ACM) Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage and that the copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permission to publish from: Publications Dept. ACM, Inc. Fax +1 212 869 0481 or email at mailto:permission@acm.org