[1]  A Clauset, CR Shalizi, and MEJ Newman. Powerlaw distributions in empirical data. SIAM review, 51(4):661703, 2009. [ bib ] 
[2]  JM Carlson and J Doyle. Highly optimized tolerance: A mechanism for power laws in designed systems. Physical Review E, 60(2):14121427, 1999. [ bib ] 
[3]  Mej Newman. Power laws, pareto distributions and zipf's law. Contemporary Physics, 46(5):323351, Sep 2005. [ bib  DOI ] 
[4]  G Yule. A mathematical theory of evolution, based on the conclusions of dr. j. c. willis, f.r.s. Philosophical Transactions of the Royal Society of London. Series BContaining Papers of a Biological Character, 213:2187, Jan 1925. [ bib  http ] 
[5] 
R Kumar, P Raghavan, S Rajagopalan, D Sivakumar, A Tomkins, and E Upfal.
Stochastic models for the web graph.
Foundations of Computer Science, 2000. Proceedings. 41st Annual
Symposium on, pages 57  65, 2000.
[ bib 
DOI 
http ]
The Web may be viewed as a directed graph each of whose vertices is a static HTML Web page, and each of whose edges corresponds to a hyperlink from one Web page to another. We propose and analyze random graph models inspired by a series of empirical observations on the Web. Our graph models differ from the traditional Gn,p models in two ways: 1. Independently chosen edges do not result in the statistics (degree distributions, clique multitudes) observed on the Web. Thus, edges in our model are statistically dependent on each other. 2. Our model introduces new vertices in the graph as time evolves. This captures the fact that the Web is changing with time. Our results are two fold: we show that graphs generated using our model exhibit the statistics observed on the Web graph, and additionally, that natural graph models proposed earlier do not exhibit them. This remains true even when these earlier models are generalized to account for the arrival of vertices over time. In particular, the sparse random graphs in our models exhibit properties that do not arise in far denser random graphs generated by ErdosRenyi models

[6]  M Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2):226251, 2004. [ bib ] 
[7]  JM Kleinberg, R Kumar, P Raghavan, S Rajagopalan, and AS Tomkins. The web as a graph: Measurements, models, and methods. Proceedings of the 5th annual international conference on Computing and combinatorics, pages 117, 1999. [ bib  http ] 
[8] 
E Drinea and M Enachescu....
Variations on random graph models for the web.
Preprint, Jan 2001.
[ bib 
.pdf ]
In this paper, we introduce variations on random graph models for Weblike graphs. As a basis, we recall a model first presented in [5]. We add vertices to the graph, one per unit time, with each vertex having one outedge. With probability a this outedge loops back to ...

[9] 
Qin Lv, Pei Cao, Edith Cohen, Kai Li, and Scott Shenker.
Search and replication in unstructured peertopeer networks.
SIGMETRICS '02: Proceedings of the 2002 ACM SIGMETRICS
international conference on Measurement and modeling of computer systems,
Jun 2002.
[ bib 
http ]
Decentralized and unstructured peertopeer networks such as Gnutella are attractive for certain applications because they require no centralized directories and no precise control over network topology or data placement. However, the floodingbased ...

[10]  Q Chen, H Chang, R Govindan, and S Jamin. The origin of power laws in internet topologies revisited. INFOCOM 2002. TwentyFirst Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2:608617, 2002. [ bib ] 
[11]  EF Keller. Revisiting “scalefree” networks. Bioessays, 27(10):10601068, 2005. [ bib ] 
[12] 
D Alderson, J Doyle, and W Willinger.
Towards a theory of scalefree graphs: Definition, properties, and
implications.
Internet Mathematics, Dec 2005.
[ bib 
.pdf ]
Abstract. There is a large, popular, and growing literature on “  ” networks with the Internet along with metabolic networks representing perhaps the canonical examples. While this has in many ways reinvigorated , there is unfortu nately no consistent, precise

[13]  M Mitzenmacher. Editorial: The future of power law research. Internet Mathematics, 2(4):525534, 2005. [ bib ] 
[14] 
Saurabh Tewari and Leonard Kleinrock.
Analysis of search and replication in unstructured peertopeer
networks.
SIGMETRICS '05: Proceedings of the 2005 ACM SIGMETRICS
international conference on Measurement and modeling of computer systems,
Jun 2005.
[ bib 
http ]
This paper investigates the effect of the number of file replicas on search performance in unstructured peertopeer networks. We observe that for a search network with a random graph topology where file replicas are uniformly distributed, the hop distance ... Keywords: peertopeer, unstructured networks, flooding, optimal file replication, search performance, replication, random graphs 
[15] 
Riley Crane, Frank Schweitzer, and Didier Sornette.
Power law signature of media exposure in human response waiting time
distributions.
Physical Review E, 81(5):056101, May 2010.
[ bib 
DOI ]

[16]  Herbert Simon. On a class of skew distribution functions. Biometrika, 42(3/4):425440, Dec 1955. [ bib  http ] 
[17] 
O Riordan and B Bollobas.
Robustness and vulnerability of scalefree random graphs.
Internet Mathematics, Jan 2004.
[ bib 
.pdf ]
... Free Random Graphs Béla Bollobás and Oliver Riordan Abstract. ... See [Aiello et al. 01, Cooper and Frieze 02, Bollobás et al. 01, Buckley and Osthus to appear, Cooper and Frieze 01] and [Cooper and Frieze 02] for some examples, or the survey [Bollobás and Riordan 02]. ...

[18] 
Sharad Goel, Andrei Broder, Evgeniy Gabrilovich, and Bo Pang.
Anatomy of the long tail: ordinary people with extraordinary tastes.
WSDM '10: Proceedings of the third ACM international conference
on Web search and data mining, Feb 2010.
[ bib 
http ]
The success of "infiniteinventory" retailers such as Amazon.com and Netflix has been ascribed to a "long tail" phenomenon. To wit, while the majority of their inventory is not in high demand, in aggregate these "worst sellers," unavailable at limitedinventory ... Keywords: infinite inventory, long tail 
[19]  Dimitris Achlioptas, Aaron Clauset, David Kempe, and Cristopher Moore. On the bias of traceroute sampling. J. ACM, 56(4):128, Jun 2009. [ bib  DOI ] 
[20] 
Xiaoyun Zhu, Jie Yu, and J Doyle.
Heavy tails, generalized coding, and optimal web layout.
INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE
Computer and Communications Societies. Proceedings. IEEE, 3:1617  1626
vol.3, 2001.
[ bib 
DOI 
http ]
This paper considers Web layout design in the spirit of source coding for data compression and rate distortion theory, with the aim of minimizing the average size of files downloaded during Web browsing sessions. The novel aspect here is that the object of design is layout rather than codeword selection, and is subject to navigability constraints. This produces statistics for file transfers that are heavy tailed, completely unlike standard Shannon theory, and provides a natural and plausible explanation for the origin of observed power laws in Web traffic. We introduce a series of theoretical and simulation models for optimal Web layout design with varying levels of analytic tractability and realism with respect to modeling of structure, hyperlinks, and user behavior. All models produce power laws which are striking both for their consistency with each other and with observed data, and their robustness to modeling assumptions. These results suggest that heavy tails are a permanent and ubiquitous feature of Internet traffic, and not an artifice of current applications or user behavior. They also suggest new ways of thinking about protocol design that combines insights from information and control theory with traditional networking

[21]  D Achlioptas. Lower bounds for random 3sat via differential equations. Theoretical Computer Science, 265(12):159185, 2001. [ bib ] 
[22] 
A Lakhina, J Byers, M Crovella, and P Xie.
Sampling biases in ip topology measurements.
INFOCOM 2003. TwentySecond Annual Joint Conference of the IEEE
Computer and Communications. IEEE Societies, 1:332  341 vol.1, 2003.
[ bib 
DOI 
http ]
Considerable attention has been focused on the properties of graphs derived from Internet measurements. Routerlevel topologies collected via traceroutelike methods have led some to conclude that the router graph of the Internet is well modeled as a powerlaw random graph. In such a graph, the degree distribution of nodes follows a distribution with a powerlaw tail. We argue that the evidence to date for this conclusion is at best insufficient We show that when graphs are sampled using traceroutelike methods, the resulting degree distribution can differ sharply from that of the underlying graph. For example, given a sparse ErdosRenyi random graph, the subgraph formed by a collection of shortest paths from a small set of random sources to a larger set of random destinations can exhibit a degree distribution remarkably like a powerlaw. We explore the reasons for how this effect arises, and show that in such a setting, edges are sampled in a highly biased manner. This insight allows us to formulate tests for determining when sampling bias is present. When we apply these tests to a number of wellknown datasets, we find strong evidence for sampling bias.

[23] 
G Miller.
Some effects of intermittent silence.
The American Journal of Psychology, Jan 1957.
[ bib 
http ]
Imagine that a monkey hits the keys of a typewriter at random, subject only to these constraints: (1) he must hit the space bar with a probability of p(*) and all the other keys with a probability of p(L) = 1  P(*), and (2) he must never hit the space bar twice in a row. I wish ...

[24]  Benoit Mandelbrot. An informational theory of the statistical structure of language. Communication Theory, pages 486502, Aug 1953. [ bib ] 
[25] 
A Barabási and R Albert.
Emergence of scaling in random networks.
Science, Dec 1999.
[ bib 
http ]
Page 1. DOI: 10.1126/science.286.5439.509 , 509 (1999); 286 Science et al. AlbertLászló Barabási, of Scaling in Random Networks This copy is for your personal, noncommercial use only. . 1 July 1999; accepted 2 September 1999 of Scaling in

[26]  J Laherrere and D Sornette. Stretched exponential distributions in nature and economy:" fat tails" with characteristic scales. The European Physical Journal B, 2(4):525539, 1998. [ bib ] 
[27] 
Edith Cohen and Scott Shenker.
Replication strategies in unstructured peertopeer networks.
SIGCOMM '02: Proceedings of the 2002 conference on Applications,
technologies, architectures, and protocols for computer communications, Aug
2002.
[ bib 
http ]
The PeertoPeer (P2P) architectures that are most prevalent in today's Internet are decentralized and unstructured. Search is blind in that it is independent of the query and is thus not more effective than probing randomly chosen peers. One technique ... Keywords: peertopeer, random search, replication 
[28] 
O Riordan and Bela Bollobas.
The diameter of a scalefree random graph.
Combinatorica, Jan 2004.
[ bib 
.pdf ]
... Page 2. 6 BÉLA BOLLOBÁS, OLIVER RIORDAN graphs are often not well approximated by these models, as shown by their degree sequences, for example. ... 8 BÉLA BOLLOBÁS, OLIVER RIORDAN the process (Gt m)tâ‰¥0 by running the process (Gt 1) on a sequence v1,v2,...; ...

[29]  M Faloutsos, P Faloutsos, and C Faloutsos. On powerlaw relationships of the internet topology. Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, pages 251262, 1999. [ bib ] 
[30]  Alex Fabrikant, Elias Koutsoupias, and Christos Papadimitriou. Heuristically optimized tradeoffs: A new paradigm for power laws in the internet. ICALP '02: Proceedings of the 29th International Colloquium on Automata, Languages and Programming, Jul 2002. [ bib  http ] 
[31] 
A Clauset and C Moore.
Accuracy and scaling phenomena in internet mapping.
Physical review letters, Jan 2005.
[ bib 
http ]
It was recently argued that sampling a network by traversing it with paths from a small number of sources, as with traceroutes on the Internet, creates a fundamental bias in observed topological features like the degree distribution. We examine this bias analytically and ...

[32] 
Stratis Ioannidis and Peter Marbach.
On the design of hybrid peertopeer systems.
SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS
international conference on Measurement and modeling of computer systems,
Jun 2008.
[ bib 
http ]
In this paper, we consider hybrid peertopeer systems where users form an unstructured peertopeer network with the purpose of assisting a server in the distribution of data. We present a mathematical model that we use to analyze the scalability of ... Keywords: peertopeer, scalability 
This file was generated by bibtex2html 1.91.