tailieunhanh - Zipf’s law and the Internet

The wide adoption of the Internet has fundamentally altered the ways in which we communicate, gather information, conduct businesses and make purchases. As the use of the World Wide Web and email skyrocketed, computer scientists and physicists rushed to characterize this new phenomenon. While initially they were surprised by the tremendous variety the Internet demonstrated in the size of its features, they soon discovered a widespread pattern in their measurements: there are many small elements contained within the Web, but few large ones. A few sites consist of millions of pages, but millions of sites only contain a handful of pages. Few sites contain millions of links,. | Glottometrics 3 2002 143-150 To honor . Zipf Zipf s law and the Internet Lada A. Adamic1 Bernardo A. Huberman Abstract. Zipfs law governs many features of the Internet. Observations of Zipf distributions while interesting in and of themselves have strong implications for the design and function of the Internet. The connectivity of Internet routers influences the robustness of the network while the distribution in the number of email contacts affects the spread of email viruses. Even web caching strategies are formulated to account for a Zipf distribution in the number of requests for webpages. Keywords Zipf s law caching networks Introduction The wide adoption of the Internet has fundamentally altered the ways in which we communicate gather information conduct businesses and make purchases. As the use of the World Wide Web and email skyrocketed computer scientists and physicists rushed to characterize this new phenomenon. While initially they were surprised by the tremendous variety the Internet demonstrated in the size of its features they soon discovered a widespread pattern in their measurements there are many small elements contained within the Web but few large ones. A few sites consist of millions of pages but millions of sites only contain a handful of pages. Few sites contain millions of links but many sites have one or two. Millions of users flock to a few select sites giving little attention to millions of others. This pattern has of course long been familiar to those studying distributions in income Pareto 1896 word frequencies in text Zipf 1932 and city sizes Zipf 1949 . It can be expressed in mathematical fashion as a power law meaning that the probability of attaining a certain size x is proportional to x T where T is greater than or equal to 1. Unlike the more familiar Gaussian distribution a power law distribution has no typical scale and is hence frequently called scale-free . A power law also gives a finite probability to very large elements .