Central loops in random planar graphs

Random planar graphs appear in a variety of contexts and it is important for many different applications to be able to characterize their structure. Local quantities fail to give interesting information and it seems that path-related measures are able to convey relevant information about the organization of these structures. In particular, nodes with a large betweenness centrality (BC) display nontrivial patterns, such as central loops. We first discuss empirical results for different random planar graphs and we then propose a toy model which allows us to discuss the condition for the emergence of nontrivial patterns such as central loops. This toy model is made of a star network with $N_b$ branches of size $n$ and links of weight 1, superimposed to a loop at distance $\ell$ from the center and with links of weight $w$. We estimate for this model the BC at the center and on the loop and we show that the loop can be more central than the origin if $w<w_c$ where the threshold of this transition scales as $w_c\sim n/N_b$. In this regime, there is an optimal position of the loop that scales as ${\ell }_{\mathrm{opt}}\sim N_{b}w/4$. This simple model sheds some light on the organization of these random structures and allows us to discuss the effect of randomness on the centrality of loops. In particular, it suggests that the number and the spatial extension of radial branches are the crucial ingredients that control the existence of central loops.

Figure 1

Betweenness centrality for a one-dimensional lattice. Left: When there is no disorder, the barycenter is the most central nodes. Right: In the case of a disordered network, the degree becomes relevant and the most central nodes have large degrees.

Figure 2

Links belonging to the giant component obtained for percolation with $f=0.15$ and with normalized BC larger than $g^{*}=0.05g_{\max }$. We observe that the links with a very large BC form a nontrivial pattern and are not necessarily close to the center. The largest loop is here highlighted with a double line.

Figure 3

Distribution of the distance to the center (normalized by the maximum distance on the lattice) for nodes with a ratio $\eta >1$. These results were obtained for $p=0.8$ on a $100\times 100$ lattice and averaged over 30 configurations.

Figure 4

We show for real-world networks the links $e$ with a BC larger than a certain threshold $g\left(e\right)>g^{*}$ and we highlight the largest loop. (a) Dresden, Germany ($g^{*}=0.11$). (b) Paris, France ($g^{*}=0.315$). (c) Los Angeles, USA ($g^{*}=0.05$). (d) Shanghai ($g^{*}=0.07$).

Figure 5

Perimeter $P\left(g^{*}\right)$ of the main loop (normalized by perimeter of the loop at $g^{*}=0$) for the road network of Dresden, Los Angeles, and Paris.

Figure 6

(a) Normalized area $A\left(g^{*}\right)$ defined by the largest loop for different boundary conditions on the Paris road network. The lowest curve corresponds to the largest size and for decreasing size the curves are shifted to larger values of the area. (b) Different boundaries corresponding to the curves of (a).

Figure 7

Representation of the toy model discussed here. The number of branches is here $N_b=5$, the number of nodes on each branch is $n=11$, and the loop is located at a distance $\ell =6$ from the center 0. The node $C$ is at the intersection of a branch and the loop and $T$ is the terminal node of a branch.

Figure 8

Schematic representation of the approximation used to compute the centrality $g_0\left(w\right)$ at the center 0.

Figure 9

Comparison between the exact result and the approximation for $g_0\left(w\right)$ (a) and $g_C\left(w\right)$ (b) (the BC are here normalized). The parameter values are here $N_b=21, n=60$, and $\ell =30$. (c) Relative error between the exact value and approximation for $g_0$ and $g_C$ for $N_b=21, n=60, w=30, \ell =30$.

Figure 10

$\delta g\left(\ell \right)$ vs $\ell$ (for $N_b=15$ and $n=60$ here) and for different values of $w$ in the range $[0,12.5]$. For values less than a threshold ($w_c\approx 4$ shown here by a dotted line) there is a minimum that is negative.

Figure 11

Comparison between the theoretical prediction [Eq. (18)] and numerical results for ${\ell }_{\mathrm{opt}}$ (for $w<w_c$). For large value of $N_b$ the prediction is excellent. We note that ${\ell }_{\mathrm{opt}}$ exists for $w<w_c$ and $w_c$ decreases with $N_b$ which implies that the range over which we can see a linear behavior is decreasing as $1/N_b$ (here $n=40$).

Figure 12

Value of $w_c{N}_b$ vs $n$. The collapse is reasonably good and is in agreement with our theoretical result, Eq. (20). We observe plateaus that are due to the discrete values of $\ell$ and $n$. The straight line is a linear fit which gives ${\kappa }_{\mathrm{emp}}\approx 0.66$ ($r^2=0.96$).