Experience versus talent shapes the structure of the Web.

We use sequential large-scale crawl data to empirically investigate and validate the dynamics that underlie the evolution of the structure of the web. We find that the overall structure of the web is defined by an intricate interplay between experience or entitlement of the pages (as measured by the number of inbound hyperlinks a page already has), inherent talent or fitness of the pages (as measured by the likelihood that someone visiting the page would give a hyperlink to it), and the continual high rates of birth and death of pages on the web. We find that the web is conservative in judging talent and the overall fitness distribution is exponential, showing low variability. The small variance in talent, however, is enough to lead to experience distributions with high variance: The preferential attachment mechanism amplifies these small biases and leads to heavy-tailed power-law (PL) inbound degree distributions over all pages, as well as over pages that are of the same age. The balancing act between experience and talent on the web allows newly introduced pages with novel and interesting content to grow quickly and surpass older pages. In this regard, it is much like what we observe in high-mobility and meritocratic societies: People with entitlement continue to have access to the best resources, but there is just enough screening for fitness that allows for talented winners to emerge and join the ranks of the leaders. Finally, we show that the fitness estimates have potential practical applications in ranking query results.

On rate-distortion models for natural images and wavelet coding performance.

Operational rate-distortion (RD) functions of most natural images, when compressed with state-of-the-art wavelet coders, exhibit a power-law behavior D alpha R(-gamma) at moderately high rates, with gamma being a constant depending on the input image, deviating from the well-known exponential form of the RD function D alpha 2(-xiR) for bandlimited stationary processes. This paper explains this intriguing observation by investigating theoretical and operational RD behavior of natural images. We take as our source model the fractional Brownian motion (fBm), which is often used to model nonstationary behaviors in natural images. We first establish that the theoretical RD function of the fBm process (both in 1-D and 2-D) indeed follows a power law. Then we derive operational RD function of the fBm process when wavelet encoded based on water-filling principle. Interestingly, both the operational and theoretical RD functions behave as D alpha R(-gamma). For natural images, the values of gamma are found to be distributed around 1. These results lend an information theoretical support to the merit of multiresolution wavelet compression of self-similar processes and, in particular, natural images that can be modelled by such processes. They may also prove useful in predicting performance of RD optimized image coders.

Multiple power-law structures in heterogeneous complex networks.

This paper develops a framework for analyzing and designing dynamic networks comprising different classes of nodes that coexist and interact in one shared environment. We consider ad hoc (i.e., nodes can leave the network unannounced, and no node has any global knowledge about the class identities of other nodes) preferentially grown networks, where different classes of nodes are characterized by different sets of local parameters used in the stochastic dynamics that all nodes in the network execute. We show that multiple scale-free structures, one within each class of nodes, and with tunable power-law exponents (as determined by the sets of parameters characterizing each class), emerge naturally in our model. Moreover, the coexistence of the scale-free structures of the different classes of nodes can be captured by succinct phase diagrams, which show a rich set of structures, including stable regions where different classes coexist in heavy-tailed (i.e., the exponent is between 2 and 3) and light-tailed (i.e., the exponent is greater than 3) states, and sharp phase transitions. The topology of the emergent networks is also shown to display a complex structure, akin to the distribution of different components of an alloyed material; e.g., nodes with a light-tailed scale-free structure get embedded to the outside of the network, and have most of their edges connected to nodes belonging to the class with a heavy-tailed distribution. Finally, we show how the dynamics formulated in this paper will serve as an essential part of ad hoc networking protocols, which can lead to the formation of robust and efficiently searchable networks [including, the well-known peer-to-peer networks] even under very dynamic conditions.

Scale-free and stable structures in complex ad hoc networks.

Unlike the well-studied models of growing networks, where the dominant dynamics consist of insertions of new nodes and connections and rewiring of existing links, we study ad hoc networks, where one also has to contend with rapid and random deletions of existing nodes (and, hence, the associated links). We first show that dynamics based only on the well-known preferential attachments of new nodes do not lead to a sufficiently heavy-tailed degree distribution in ad hoc networks. In particular, the magnitude of the power-law exponent increases rapidly (from 3) with the deletion rate, becoming infinity in the limit of equal insertion and deletion rates. We then introduce a local and universal compensatory rewiring dynamic, and show that even in the limit of equal insertion and deletion rates true scale-free structures emerge, where the degree distributions obey a power law with a tunable exponent, which can be made arbitrarily close to 2. The dynamics reported in this paper can be used to craft protocols for designing highly dynamic peer-to-peer networks and also to account for the power-law exponents observed in existing popular services.