Synchronous and asynchronous recursive random scale-free nets

We investigate the differences between scale-free recursive nets constructed by a synchronous, deterministic updating rule (e.g., Apollonian nets), versus an asynchronous, random sequential updating rule (e.g., random Apollonian nets). We show that the dramatic discrepancies observed recently for the degree exponent in these two cases result from a biased choice of the units to be updated sequentially in the asynchronous version.

Figure 1

Synchronous recursive scale-free tree and methods of construction. (a) Generations $n=0,1,2,3$ of the tree. (b) First method of construction: to each of the endpoints of every link in generation $n$ we connect a node of degree one. (c) Second method: to each node of degree $k$ in generation $n$ we add $k$ new nodes of degree one. (d) Third method: to obtain generation $n+1$, we join three copies of generation $n$ at the hubs (the nodes of highest degree).

Figure 2

(Color online) Random sequential trees constructed by selecting links at random (×), or by picking the link between a randomly selected node and a neighbor (엯). The trees consist of ${10}^7$ nodes. The straight lines of slopes 3 and 5 are shown for comparison.

Figure 3

(Color online) Degree-degree correlations in deterministic and random trees. Shown is $M(4,m)∕{\sum }_{k}M(4,k)$ as a function of $m$ for deterministic trees of generation $n=8$ (●), compared to random trees of equal size (엯). The random results were obtained as an average over 1000 realizations. Error bars are smaller than the size of the symbols.