Quasirandom geometric networks from low-discrepancy sequences

We define quasirandom geometric networks using low-discrepancy sequences, such as Halton, Sobol, and Niederreiter. The networks are built in $d$ dimensions by considering the $d$-tuples of digits generated by these sequences as the coordinates of the vertices of the networks in a $d$-dimensional $I^d$ unit hypercube. Then, two vertices are connected by an edge if they are at a distance smaller than a connection radius. We investigate computationally 11 network-theoretic properties of two-dimensional quasirandom networks and compare them with analogous random geometric networks. We also study their degree distribution and their spectral density distributions. We conclude from this intensive computational study that in terms of the uniformity of the distribution of the vertices in the unit square, the quasirandom networks look more random than the random geometric networks. We include an analysis of potential strategies for generating higher-dimensional quasirandom networks, where it is know that some of the low-discrepancy sequences are highly correlated. In this respect, we conclude that up to dimension 20, the use of scrambling, skipping and leaping strategies generate quasirandom networks with the desired properties of uniformity. Finally, we consider a diffusive process taking place on the nodes and edges of the quasirandom and random geometric graphs. We show that the diffusion time is shorter in the quasirandom graphs as a consequence of their larger structural homogeneity. In the random geometric graphs the diffusion produces clusters of concentration that make the process more slow. Such clusters are a direct consequence of the heterogeneous and irregular distribution of the nodes in the unit square in which the generation of random geometric graphs is based on.

Figure 1

Illustration of quasirandom geometric networks generated with the low-discrepancy sequences of Halton (a), Sobol (b), and Niederreiter (c). All networks are generated with 500 points and a connection radius $r=0.075$.

Figure 2

Top panels: Change of the probability of the quasirandom network to be connected as a function of the connection radius for quasirandom geometric networks with 500 nodes (a) and 1000 nodes (b) using Halton (red solid line), Sobol (blue dash-dot line), and Niederreiter (green dotted line) sequences. Bottom panels: Results of the simulations for the connectivity of 100 random realizations of the RGGs with the same size and connection radius as the ones in the top panels for 500 nodes (c) and 1000 nodes (d). Notice that there is an almost perfect overlap between the curves produced from the Sobol and Niederreiter sequences.

Figure 3

Coefficients of variations of the 11 network-theoretic parameters studied here as a function of the connection radius for quasirandom geometric networks with 500 nodes (a) and 1000 nodes (b). The coefficient of variations indicates the relative variation in the index across the three methods used to generate the quasirandom networks. The $y$ axis is in logarithmic scale to make a better differentiation and the lines between the points are used to guide the eye. Some points appear disconnected in the plots due to the fact that the rest of points for this parameter are equal to zero. The lines between the points are used to guide the eye. Diam stands for the diameter $D$.

Figure 4

Change of the error for the 11 network-theoretic invariants studied with the connection radius in quasirandom Halton geometric networks relative to the random geometric networks. The results for RGGs were taken as the average of 100 random realizations. The plots in (a) correspond to networks with $n=500$ nodes and those (b) to networks with $n=1000$ nodes. The lines between the points are used to guide the eye. Diam stands for the diameter $D$.

Figure 5

Halton quasirandom network with $n=500$ nodes and connection radius $r=0.1$ (a). The analogous RGG obtained with random numbers generated from Matlab (b). (Bottom) The partition into two clusters obtained from ${\vec{\psi }}_2$ for the Halton network (c) and RGG (d) shown in the top panels.

Figure 6

Probability degree distribution (main panel) and cumulative degree distribution (inset) for the quasirandom geometric networks. (Top panels) Using Halton (solid line), Sobol (dash-dot line), and Niederreiter (dotted line) sequences for $n=1000$ nodes and connection radius of 0.05, 0.15 and 0.5, respectively. (Bottom panels) Results of 100 random realizations for $n=1000$ nodes and connection radius of 0.05, 0.15, and 0.5. Colors like in Fig. 2.

Figure 7

(a–c) Spectral densities of the quasirandom geometric networks using Halton (solid line), Sobol (dash-dot line), and Niederreiter (dotted line) sequences, for $n=1000$ nodes and connection radius 0.1, 0.25, and 0.5, respectively. (d–f) Results of 100 random realizations for $n=1000$ nodes and connection radius of 0.1, 0.25, and 0.5.

Figure 8

Quasirandom networks with $n=500$ nodes and connection radius $r=0.1$ obtained with the Halton sequence for coprimes 11 and 13 (top panels) and coprimes 61 and 67 (bottom panels). The left-hand side panels correspond to Halton sequences without skipping, leaping or scrambling. The right-hand side panels correspond to skipping the first 1000 numbers of the sequence, leaping every 100 numbers and using scramble with reverse-radix operation to all of the possible coefficient values.

Figure 9

Comparison of eight network-theoretical properties of quasirandom networks with $n=1000$ nodes and $r=0.075$ using the Halton sequence with the first 16 pairs of coprimes (see text). The blue circles represent the Halton sequences without skipping, leaping, or scrambling and the red squares represent Halton sequences after skipping the first 1000 numbers of the sequence, leaping every 100 numbers and using scramble with reverse-radix operation to all of the possible coefficient values.

Figure 10

(a) Standard deviation for the first 20 pairs of coprimes of the 11 network-theoretic properties studied in this work for the Halton quasirandom networks with $n=1000$ nodes and $r=0.075$ without (blue circles) and with (red squares) S-L-S. The lines are used just to guide the eye. (bottom) Three-dimensional quasirandom geometric network generated with the Halton sequence and primes 2, 3, and 5 (b) and the analogous RGG (c). Both networks have 500 nodes and connection radius 0.2.

Figure 11

Plot of the diffusion time for 60 RGGs with 500 nodes and connection radius $r=0.09$. For each RGG we produce 100 random initializations. Then, the circles represent the value of the diffusion time for one graph averaged for 100 random initializations, with standard deviation represented as bars. The blue horizontal line represents the mean value for the 60 RGGs and their 100 random realizations, i.e., the average of 6000 values of the diffusion time, and the red bands are the corresponding standard deviations.

Figure 12

Illustration of the diffusion process on a RGG (a–c) and a Halton-RGG (d–f) at different stages: initial time [(a) and (d)], time at which the difference in concentrations is half the stopping criterion [(b) and (e)], and time at which the difference in concentrations is the same as the stopping criterion [(c) and (f)]. The stopping criterion used here is ${10}^{-3}$. The graphs were built with 500 nodes and connection radius $r=0.09$.