[1] A Clauset, CR Shalizi, and MEJ Newman. Power-law distributions in empirical data. SIAM review, 51(4):661-703, 2009. [ bib ]
[2] JM Carlson and J Doyle. Highly optimized tolerance: A mechanism for power laws in designed systems. Physical Review E, 60(2):1412-1427, 1999. [ bib ]
[3] Mej Newman. Power laws, pareto distributions and zipf's law. Contemporary Physics, 46(5):323-351, 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:21-87, 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 Erdos-Renyi models

[6] M Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2):226-251, 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 1-17, 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 Web-like 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 peer-to-peer 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 peer-to-peer 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 flooding-based ...

[10] Q Chen, H Chang, R Govindan, and S Jamin. The origin of power laws in internet topologies revisited. INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2:608-617, 2002. [ bib ]
[11] EF Keller. Revisiting “scale-free” networks. Bioessays, 27(10):1060-1068, 2005. [ bib ]
[12] D Alderson, J Doyle, and W Willinger. Towards a theory of scale-free 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):525-534, 2005. [ bib ]
[14] Saurabh Tewari and Leonard Kleinrock. Analysis of search and replication in unstructured peer-to-peer 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 peer-to-peer networks. We observe that for a search network with a random graph topology where file replicas are uniformly distributed, the hop distance ...

Keywords: peer-to-peer, 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):425-440, Dec 1955. [ bib | http ]
[17] O Riordan and B Bollobas. Robustness and vulnerability of scale-free 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 "infinite-inventory" 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 limited-inventory ...

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):1-28, 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 3-sat via differential equations. Theoretical Computer Science, 265(1-2):159-185, 2001. [ bib ]
[22] A Lakhina, J Byers, M Crovella, and P Xie. Sampling biases in ip topology measurements. INFOCOM 2003. Twenty-Second 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. Router-level topologies collected via traceroute-like methods have led some to conclude that the router graph of the Internet is well modeled as a power-law random graph. In such a graph, the degree distribution of nodes follows a distribution with a power-law tail. We argue that the evidence to date for this conclusion is at best insufficient We show that when graphs are sampled using traceroute-like methods, the resulting degree distribution can differ sharply from that of the underlying graph. For example, given a sparse Erdos-Renyi 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 power-law. 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 well-known 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 486-502, 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. Albert-László Barabási, of Scaling in Random Networks This copy is for your personal, non-commercial 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):525-539, 1998. [ bib ]
[27] Edith Cohen and Scott Shenker. Replication strategies in unstructured peer-to-peer networks. SIGCOMM '02: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, Aug 2002. [ bib | http ]
The Peer-to-Peer (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: peer-to-peer, random search, replication
[28] O Riordan and Bela Bollobas. The diameter of a scale-free 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 power-law relationships of the internet topology. Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, pages 251-262, 1999. [ bib ]
[30] Alex Fabrikant, Elias Koutsoupias, and Christos Papadimitriou. Heuristically optimized trade-offs: 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 peer-to-peer 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 peer-to-peer systems where users form an unstructured peer-to-peer 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: peer-to-peer, scalability

This file was generated by bibtex2html 1.91.