Critical field-exponents for secure message-passing in modular networks

As our world becomes more interconnected, the need to pass messages securely has gained increasing importance [1]. The recently developed applications of statistical physics of networks to anonymous browsing networks [2] and secure message-passing [3] promises an interesting new direction of security based on network topology. One application is internet routers, which form a physical communication network with nodes belonging to specific countries that can eavesdrop on information passing through their routers [4]. If two nodes wish to communicate securely and are not directly connected, they could split their messages into separate parts and send each part along a different path such that no single adversary is present on every path. In this way, no adversary would be able to decode the full message. Most likely, many nodes will not be able to communicate in such a manner. For example, a node with only one link must inherently have all its information pass through that link. Whether information can be transferred through such a communication network securely and effectively is strongly dependent on the frequency and structural network properties of vulnerabilities e.g. nodes belonging to a malicious country in the aforementioned example. In this paper we define the giant secure component (GSC) as the fraction of nodes which are capable of communicating securely with one another using the above described method of multiple paths. We note that any node in the GSC can securely communicate with any other node in the GSC. To find the GSC we generalize the framework of 'color-avoiding percolation' (CAP) [3, 5] to study a more realistic case of secure message-passing in a communication network with a given community structure and different classes of adversaries (vulnerabilities).

In CAP each node in the network is assigned a specific color. A path between two nodes is considered to avoid a particular color (i.e., is secure from that color) if no nodes of that color exist along the path (not counting its endpoints). We find the set of nodes that can avoid a particular color by removing all nodes of that color, determining the largest component of the remaining nodes, and then adding back those nodes of the removed color that have a direct link to the largest component (see the example in the supplementary material available online at stacks.iop.org/NJP/20/053001/mmedia). If between two given nodes there is for each color at least one path avoiding that color, the two nodes are considered securely connected. Equivalently, only nodes that can communicate such that no single color exists on every path between them are considered secure.

Here we consider CAP on networks with given community structure, a realistic case for many networks [6–14]. Continuing the above example of internet routers, in each country most of the routers presumably belong to that country with a smaller number of routers belonging to other countries [3, 15, 16]. To study the community structure we use the stochastic block model [17, 18], where each community is recognized as a 'block' in an adjacency matrix, and assign a certain color to dominate each module. This imposes correlations on the distribution of colors in the network, naturally modeled as a modular network.

For simplicity, we demonstrate our model and results on a network with two communities having an internal average degree k_I and an external average degree¹⁰ k_E. We begin by assuming (for simplicity but without loss of generalization) that there are two colors with a single dominant color (C_d = 1) occupying a fraction q nodes of each module and the remaining fraction 1 − q being of the other color (see figure 1(a))¹¹ . This same framework can be used to describe networks where the links are correlated by color (see SM). To identify the GSC, we find the standard giant component under the removal of nodes of a single color, and then add back nodes of the removed color which have a direct link to the largest component (reflecting the assumption that the endpoints of every path are secure) [3]. This is done for each color and then the intersection of all these components is the GSC.

Zoom In Zoom Out Reset image size

To solve our model analytically, we adopt the generating function framework defining ${g}_{0}(z)={\sum }_{k}{p}_{k}{z}^{k}$ as the generating function of the variable k with p_k being the probability of a node having k links [19, 20]. For our model we have generating functions for the internal and external connections defined by ${g}_{{0}_{{k}_{I}}}(z)$ and ${g}_{{0}_{{k}_{E}}}(z)$ respectively. For the case of 2 colors, we must find: u_1,0, the likelihood that a link fails to avoid the color dominant in its module; u_0,1, the likelihood that the link fails to avoid the color dominant in the other module; and u_1,1, the likelihood that the link does not avoid either of the two colors. We then assume that the sender and receiver nodes are secure, by taking ${g}_{{0}_{{k}_{I}}}({u}_{i,j}){g}_{{0}_{{k}_{E}}}({u}_{j,i})$, which adds back nodes with a direct link to the giant component in both the internal and external modules. Naively one might think that to find the size of the GSC, S_c, one could merely take $1-{g}_{{0}_{{k}_{I}}}({u}_{\mathrm{1,0}}){g}_{{0}_{{k}_{E}}}({u}_{\mathrm{0,1}})-{g}_{{0}_{{k}_{I}}}({u}_{\mathrm{0,1}}){g}_{{0}_{{k}_{E}}}({u}_{\mathrm{1,0}})$ i.e., take the conjugate of the probability that a randomly chosen node fails to avoid both colors. However, this neglects the fact that some nodes fail to avoid either color. To deal with this overcounting we must add back ${g}_{{0}_{{k}_{I}+{k}_{E}}}({u}_{\mathrm{1,1}})$ in accordance with the inclusion–exclusion principle [21]. The k_I + k_E subscript in this case means that we are now counting over the total number of links of the given node, such that ${g}_{{0}_{{k}_{I}+{k}_{E}}}({u}_{\mathrm{1,1}})={\sum }_{k={k}_{I}+{k}_{E}}{p}_{k}{u}_{1,1}^{k}$, where p_k is now the likelihood of the node having a total of k = k_I + k_E links, independent of whether they are external or internal. For an Erdős–Rényi degree distribution this would be ${g}_{{0}_{{k}_{I}+{k}_{E}}}({u}_{\mathrm{1,1}})={{\rm{e}}}^{-({k}_{I}+{k}_{E})(1-{u}_{\mathrm{1,1}})}$. Using this, we obtain

$$\begin{eqnarray}&&{S}_{c}=1-{g}_{{0}_{{k}_{I}}}({u}_{\mathrm{1,0}}){g}_{{0}_{{k}_{E}}}({u}_{\mathrm{0,1}})-{g}_{{0}_{{k}_{I}}}({u}_{\mathrm{0,1}}){g}_{{0}_{{k}_{E}}}({u}_{\mathrm{1,0}})+{g}_{{0}_{{k}_{E}+{k}_{I}}}({u}_{\mathrm{1,1}}).\end{eqnarray} \tag{ 1 }$$

To solve equation (1) we need to calculate the probabilities u_i,j which, for Erdős–Rényi topologies of internal and external connections, are obtained by solving self-consistently the system

$$\begin{eqnarray}{u}_{\mathrm{1,0}} & = & q+(1-q){{\rm{e}}}^{-{k}_{I}(1-{u}_{\mathrm{1,0}})-{k}_{E}(1-{u}_{\mathrm{0,1}})}\\ {u}_{\mathrm{0,1}} & = & (1-q)+{{q}{\rm{e}}}^{-{k}_{I}(1-{u}_{\mathrm{0,1}})-{k}_{E}(1-{u}_{\mathrm{1,0}})}\\ {u}_{\mathrm{1,1}} & = & {{q}{\rm{e}}}^{-{k}_{I}(1-{u}_{\mathrm{0,1}})-{k}_{E}(1-{u}_{\mathrm{1,0}})}+(1-q){{\rm{e}}}^{-{k}_{I}(1-{u}_{\mathrm{1,0}})-{k}_{E}(1-{u}_{\mathrm{0,1}})}.\end{eqnarray} \tag{ 2 }$$

For more details on the derivation and solving of equations (1) and (2) see supplementary material. Results comparing the above theory to simulations are shown in figure 2.

Zoom In Zoom Out Reset image size

We find from figure 2 that only in the case where k_E = 0 does the system undergo a phase transition at the critical point ${q}_{c}=1-1/{k}_{I}$ [5], while for any k_E > 0 there is always some fraction of nodes in the secure component. This is because even if one of the two modules disintegrates when the dominant color is removed from it, there always exists a finite fraction of its nodes which can communicate securely through external links to the other module. Thus k_E > 0 removes the transition by making the disconnected phase unreachable [22], just as an external magnetic field of magnitude H does with respect to the disordered phase in the Ising model [23]. In what follows we further support, both analytically and by extensive simulations, this intriguing analogy between spin models and secure message-passing on modular networks.

To this aim, we investigate the scaling relations of our model with S_c, q, and k_E as the CAP analogues of total magnetization, temperature, and the external field respectively. Let us first stress that for the case C_d = 1, that is a single dominant color in each module, the scaling exponent β defined by ${S}_{c}{({q}_{c})\sim (q-{q}_{c})}^{\beta }$ was found to be β = 1 [3]. To extract information about the universality class of the model, we will now measure the scaling exponents δ and γ which relate to the properties of the field. We choose these exponents since they are directly related to the field and are easiest to measure. Note that for CAP, exponents relating the distribution of component sizes are computationally challenging to calculate since we must calculate the overlaps of many small components of the various colors. In addition, once any two of the exponents are known, the rest are fixed due to known scaling relations between the various critical exponents [24]. We thus begin with δ, which defines the variation of the order parameter with the external field at criticality. According to our analogy, this is given by

$$\begin{eqnarray}&&{S}_{c}\sim {k}_{E}^{1/\delta }.\end{eqnarray} \tag{ 3 }$$

For C_d = 1, we find from simulations that δ = 2 (figure 3(a)), setting the critical properties of this model within the mean-field percolation universality class. On a practical side, these exponents suggest that, in the case of one dominant color, increasing external connectivity between the modules is more beneficial near the critical point since $1=\beta \gt 1/\delta =\tfrac{1}{2}$.

Based on the above results, we introduce hereafter the CAP-analogue of the magnetic susceptibility, which we define by means of the scaling relation

$$\begin{eqnarray}&&{\left(\displaystyle \frac{\partial {S}_{c}}{\partial {k}_{E}}\right)}_{{k}_{E}\to 0}\sim {| q-{q}_{c}| }^{-\gamma }.\end{eqnarray} \tag{ 4 }$$

Using equations (1) and (2), we find (figure 3(b)) γ = 1 for C_d = 1 which, together with the other exponents obtained (δ = 2 and β = 1), is indeed consistent with Widom's identity δ − 1 = γ/β [24, 25].

The numerical results above can also be found analytically by expanding for k_I near its critical value, ${k}_{I}=\tfrac{1}{1-{q}_{c}}$. By defining ${x}_{\mathrm{1,0}}\equiv 1-{u}_{\mathrm{1,0}}$ and ${x}_{\mathrm{0,1}}\equiv 1-{u}_{\mathrm{0,1}}$ and expanding equation (2) to leading orders in x_1,0 and k_E, we obtain

$$\begin{eqnarray}&&{x}_{\mathrm{1,0}}={q}_{c}-q+\sqrt{{({q}_{c}-q)}^{2}+\displaystyle \frac{2{k}_{E}{x}_{\mathrm{0,1}}}{{k}_{I}^{2}}}.\end{eqnarray} \tag{ 5 }$$

It follows that δ = 2, as x_1,0 scales with the square root of k_E, and γ = 1 as can be found by taking the derivative of equation (5) with respect to k_E.

Having discussed the case of a single dominant color, we now study the case of multiple colors (C_d > 1) sharing dominance in a single community as depicted in figure 1(b). Each of these dominant colors will occupy a fraction q/C_d of the module. Following logic similar to that used for C_d = 1, the GSC in this case can be found by

$$\begin{eqnarray}&&{S}_{c}=\displaystyle \sum _{i=0}^{{C}_{d}}\displaystyle \sum _{j=0}^{{C}_{d}}{(-1)}^{(i+j)}\left(\displaystyle \genfrac{}{}{0em}{}{{C}_{d}}{i}\right)\left(\displaystyle \genfrac{}{}{0em}{}{{C}_{d}}{j}\right){{\rm{e}}}^{-{k}_{{I}}(1-{u}_{i,j})-{k}_{{E}}(1-{u}_{j,i})}\end{eqnarray} \tag{ 6 }$$

where the probabilities u_{i, j} satisfy the system of self-consistent equations

$$\begin{eqnarray}&&{u}_{i,j}={\rm{i}}\displaystyle \frac{q}{{C}_{d}}{{\rm{e}}}^{-{k}_{{I}}(1-{u}_{i-1,j})-{k}_{{E}}(1-{u}_{j,i-1})}+j\displaystyle \frac{1-q}{{C}_{d}}{{\rm{e}}}^{-{k}_{{I}}(1-{u}_{i,j-1})-{k}_{{E}}(1-{u}_{j-1,i})}+\left(1-{\rm{i}}\displaystyle \frac{q}{{C}_{d}}-j\displaystyle \frac{1-q}{{C}_{d}}\right){{\rm{e}}}^{-{k}_{{I}}(1-{u}_{i,j})-{k}_{{E}}(1-{u}_{j,i})}\end{eqnarray} \tag{ 7 }$$

with i ≤ C_d, j ≤ C_d, and ${u}_{\mathrm{0,0}}={u}_{0,-1}={u}_{-\mathrm{1,0}}\equiv 1$. For k_E = 0 we recover the equations obtained by Krause et al in [3, 5].

In contrast with the results for C_d = 1, we find that for every C_d ≥ 2 the critical scaling exponents are given by γ = 0 and δ = 1 (figure 3) which, to the best of our knowledge, define a novel universality class. These results, together with the exponent β = C_d obtained in [5], suggest that for more than one dominant color the system undergoes higher-order phase transitions. In general, for C_d = i we will have an (i + 1)-order transition, i.e. for C_d = 2 we have a third order transition, for C_d = 3 we have a fourth order transition, etc. To verify this claim, we evaluate the higher-order derivatives of S_c with respect to k_E, the first of which is given by

$$\begin{eqnarray}&&{\left(\displaystyle \frac{{\partial }^{2}{S}_{c}}{\partial {k}_{E}^{2}}\right)}_{{k}_{E}\to 0}\sim {| q-{q}_{c}| }^{-G},\end{eqnarray} \tag{ 8 }$$

where G satisfies the generalized scaling relation $G=\beta ({C}_{d}\delta -1)$ [26]. In particular, for C_d = 2 we expect an exponent G = 2, which we confirm with numerical results (see SM). For C_d ≥ 3, equation (8) breaks down and we obtain G = 1. As far as we know, the present study represents the first time that this novel universality class with higher-order transitions is observed in percolation type systems with the higher-order scaling exponents defined and measured.

Zoom In Zoom Out Reset image size

Finally, though our model does not have any spatial embedding, we can gain insights into the upper critical dimension of the CAP process, by invoking the scaling relations and the results above. In fact, we can indirectly evaluate the product $\nu {d}_{c}$, where ν is the scaling exponent related to the singular part of the correlation length at criticality and d_c is the upper critical dimension [27] of the process. We do this by analyzing how the size of the GSC, ${{NS}}_{c}({q}_{c})$, scales at criticality with the number of nodes N in the absence of external connections (i.e., k_E = 0). Specifically, we know that the correlation length, ξ, has power-law scaling $\xi \sim | q-{q}_{c}{| }^{-\nu }$ near criticality, and that in particular it scales with the size of the system, i.e. $\xi \sim {N}^{1/{d}_{c}}$ at the critical threshold [24, 25]. Combining these properties with the critical scaling of the GSC, yields ${{NS}}_{c}({q}_{c})\sim {N}^{1-\beta /\nu {d}_{c}}$ for the GSC's size. Recalling that β = C_d, by measuring ${{NS}}_{c}({q}_{c})$ for varying N, we can find $\nu {{cd}}_{c}$ from simulations. In figure 4 we carry out this simulation for different C_d and obtain in every case that $\nu {d}_{c}=3$, most likely with $\nu =\tfrac{1}{2}$ and d_c = 6 as for classical percolation on Erdős–Rényi networks.

Zoom In Zoom Out Reset image size

This result can be equivalently understood as follows. The scaling of ${{NS}}_{c}({q}_{c})\sim {{NS}}_{1}({q}_{c}){S}_{2}({q}_{c})\,...\,{S}_{{C}_{d}}({q}_{c})\,=\tfrac{N}{{N}^{{C}_{d}}}{{NS}}_{1}({q}_{c})\times {{NS}}_{2}({q}_{c})\,...\,\times {{NS}}_{{C}_{d}}({q}_{c})$, where ${S}_{1}({q}_{c}),\,\ldots ,\,{S}_{{C}_{d}}({q}_{c})$ represent the scaling of the size of the component avoiding color 1, ..., C_d respectively. Each ${{NS}}_{1}({q}_{c}),\,\ldots ,\,{{NS}}_{{C}_{d}}({q}_{c})$ scales like an Erdős–Rényi network [3] with ${{NS}}_{1}({q}_{c}),\,\ldots ,\,{{NS}}_{{C}_{d}}({q}_{c})\sim {N}^{2/3}$. If we rearrange and substitute this into our expression above we obtain ${{NS}}_{c}({q}_{c})\sim \tfrac{N}{{N}^{{C}_{d}}}{N}^{2/3}\times {N}^{2/3}\,...\,\times \,{N}^{2/3}$ and finally

$$\begin{eqnarray}&&{{NS}}_{c}({q}_{c})\sim {N}^{1-{C}_{d}}{N}^{\tfrac{2{C}_{d}}{3}}={N}^{1-{C}_{d}/3}.\end{eqnarray} \tag{ 9 }$$

This can then be set equal to ${N}^{1-\beta /\nu {d}_{c}}$, justifying this way the numerical result $\nu {d}_{c}=3$.

This constant value of $\nu {d}_{c}$ combined with the increasing value of β as the number of colors increases, leads to the apparently surprising behavior of figure 4 where the size of the largest cluster, ${{NS}}_{c}({q}_{c})$, decreases with the system size N, when C_d > 3. We explain this scaling by noting that we assume that nodes in the intersection of the largest component avoiding each color respectively are in the GSC (in the next paragraph we will analyze this assumption). The likelihood of being in the largest component avoiding any single color scales with N^−1/3, such that when two colors must be avoided the scaling is N^−1/3 × N^−1/3, and so on for additional colors. Once more than three colors must be avoided, the decreasing likelihood of being in all of the colors overpowers the linear growth of the system size leading to the observed decrease in the overlap of the largest components for each color. Further, this suggest that at criticality the overlap of the largest components for each color has vanishing or negative fractal dimension for C_d ≥ 3 [28]. These values of the fractal dimension are indeed surprising in the context of percolation on networks. For instance, in classical percolation on scale-free networks, β increases as the degree distribution becomes broader [29, 30], but this increase is counteracted by the simultaneous increase of the upper critical dimension, thus the fractal dimension remains positive.

However, we must note that there is some subtlety in this calculation, especially for C_d > 3. Specifically, we return to the above assumption that the overlap of the largest component avoiding each color gives the GSC. In most cases this will indeed be true, however when this overlap is very small, then overlap between smaller components must be considered in both the simulations and the derivation of equation (9). Specifically in the case where the expected overlap of the largest component for each color is less than a single node, we know that the actual GSC must be at least a single node and thus the assumption does not hold. In any case, we can say that for all C_d ≥ 3 the actual size of the GSC scales as O(1), as opposed to the negative exponent suggested by equation (9). This also implies that the GSC has a vanishing but non-negative fractal dimension since it always includes at least one node.

Finally, our results suggest the breakdown of the scaling relation $\nu {d}_{c}=2\beta +\gamma$ [24, 25] for C_d > 1 since $\nu {d}_{c}=3$ for all C_d > 1 but $2\beta +\gamma =2{C}_{d}$ (for C_d > 1) which increases with C_d. This scaling relation originated from the distribution of small clusters at criticality, n(s), having finite-size scaling $n(s)\sim {N}^{-\tau }$ as long as τ < 3 [24, 25]. Its failure here implies that for CAP with C_d > 1, the critical exponent τ ≥ 3. This can be understood based on previous results on bicomponent-percolation [31], which is less restrictive than CAP [3], where it was shown that there are in general (almost) no small bicomponents in the network, rather only a giant bicomponent can exist. A circumstance is then paved concerning the possibility that also for CAP there are in general almost no small secure components in modular structures.

In summary, our results map the study of secure message-passing between nodes in modular networks to the statistical physics of Ising models with a magnetic field. Previous attempts to introduce the idea of a field into percolation relied on a ghost site [32–34], to which every node connects with some probability H and thus allowing it to remain functional even if it is separated from the 'rest' of the largest cluster. Here we obtain the field-exponents, δ and γ, naturally as a result of the realistic effects of modules rather than from the artificial introduction of a ghost site. Further, we find novel universality classes, the breakdown of a known scaling relation and higher-order phase transitions. This work highlights the potential for incorporating the idea of an external field into complex systems and shows how this idea can be used to shed light on the fundamental physics underlying its collective behaviours.

Acknowledgments