WorksPhysics and Astronomy
Percolation under Edge-Reversal: Creation and Destruction of Strong Connectivity in Directed Networks
Abstract
We study how the connectivity of a directed network changes when each edge is independently reversed with probability , while the underlying connections remain fixed. Reversal changes the in- and out-degrees, and we derive the exact transformation of the joint in–out-degree distribution and characterize its evolution under repeated reversal. However, the transformation does not rewire the network, and every edge still connects the same pair of vertices. As a result, the transformed degree distribution alone does not determine whether a giant strongly connected component exists, and a reconstruction based only on the transformed degrees can even place the network on the wrong percolation state. For the directed configuration model, we account for the preserved structure by separately tracking edges that retain or reverse their original direction, leading to a two-type branching process. From this formalism, we obtain explicit analytical criteria for the creation or destruction of a giant strongly connected component and illustrate these contrasting outcomes with empirical examples. Consistent with the predicted creation criterion, randomizing edge directions in a S. cerevisiae transcriptional regulation network dramatically increases the size of the largest strongly connected component. In the San Diego directed road network, the degree moments satisfy the destruction criterion, and the largest strongly connected component decreases to virtually zero, although its decline occurs well below the predicted configuration-model threshold. These results provide a framework for assessing the sensitivity of mutual reachability to changes or uncertainty in edge directions and show that directional disorder can either enable or suppress global connectivity without changing the underlying connections.
Introduction
Directions encode function in many networks. They distinguish upstream from downstream regulation, supply from demand, sender from receiver, predator from prey, and one-way from two-way accessibility. A convenient way to probe how much a network depends on this information is therefore to perturb directions while keeping the underlying set of connections fixed. Here we study the simplest such perturbation: each directed edge is independently reversed with probability on the otherwise quenched network structure, meaning that every edge connects the same two vertices as before and only its direction may change.
The operation itself has clear precedents. Random orientations of a fixed graph have been studied in probabilistic graph theory [7, 8, 9]. Direction randomization has also been used as a null model in network science [10, 13], and partial edge reversals have been used to probe loop structure and global directionality in empirical networks [11, 12]. Independent reversal has been studied directly for the strongly connected component of divisor graphs [19]. Related work has developed percolation theory for random directed networks containing both unidirectional and bidirectional edges [5], while strong-connectivity transitions induced by one-way links have been studied in two-dimensional lattice models [14]. Our goal here is to develop an explicit theory for the effect of edge-reversal noise on degree statistics and, for directed configuration models, on percolation when the original edge pairings are preserved.
Generating functions provide a convenient way to describe how edge reversal changes the joint in–out-degree distribution, building on the standard treatment of arbitrary-degree directed random graphs [1]. Predicting percolation, however, requires more information in our setting because reversal preserves the original edge pairings. Reversing edge directions is therefore not equivalent to rebuilding a random graph from the transformed degree distribution. A current directed edge can arise in two different ways—as an original edge that retained its direction or as an original edge that was reversed. Following these two kinds of edges samples different excess-degree distributions and therefore gives different expected numbers of outgoing edges available for further exploration. We accordingly keep the two cases distinct in a two-type branching process. This construction builds on the standard branching-process description of giant components in sparse directed degree-sequence and configuration models [2, 3], and is closely related to multitype and correlated random-graph formalisms used when edge or stub classes carry information not contained in the degree distribution alone [4, 5, 6].
For a directed configuration model, keeping track of the two possible arrival types—through a retained or a reversed edge—leads to a two-type branching description of percolation. Its largest eigenvalue determines the percolation threshold for a giant strongly connected component to exists. Because reversal changes the relative contribution of the two arrival types to the largest eigenvalue, the resulting threshold can move either upward or downward as reversal noise increases, so the same perturbation can create a giant strongly connected component in an initially subcritical network and destroy it in an initially supercritical one. Importantly, this behavior is not determined by the transformed in–out-degree distribution alone: in sufficiently asymmetric cases, a reconstruction based only on that distribution can even predict the wrong connectivity phase.
The configuration model provides a useful baseline for interpreting empirical directed networks. However, real-world directed networks may also contain hierarchy, reciprocity, clustering, geometry, and other forms of organization not encoded by the joint degree distribution [15, 16, 17]. We illustrate the resulting framework using a S. cerevisiae transcriptional network distributed by SNAP [21, 22] and the San Diego freeway-and-ramp subnetwork extracted from an OpenStreetMap-derived city network [23, 24, 25]. These examples exhibit creation and destruction of strong connectivity, respectively, treating reversal as a topology-preserving stress test of how strongly connectivity depends on the observed edge orientations.
Edge-reversal transformation and degree statistics
Consider a directed graph with joint in–out-degree distribution , where and denote the in- and out-degree of a vertex, and is its total degree. Each edge is independently reversed with probability and retains its original direction with probability . The endpoints of every edge remain fixed, so the perturbation changes only edge directions and leaves the underlying undirected graph unchanged.
Multiple edges and oppositely directed edges between the same pair of vertices, when present, are treated as distinct labelled edges and are reversed independently. Allowing such edges is natural for the directed configuration model and keeps the reversal operation well defined without additional merging or rejection rules. They are not required for the degree-level results derived below. In sparse configuration-model limits, occasional multiple or opposite-direction edges do not affect the leading percolation threshold, although they may be more relevant in finite, strongly heterogeneous, or highly reciprocal networks.
Consider now a vertex with initial in-degree and out-degree . After the perturbation, its incoming edges can have two origins: original incoming edges that were not reversed and original outgoing edges that were reversed. Let and denote the numbers of edges of these two types, respectively. Then, the new in- and out-degrees are
In particular, , and the total degree of every vertex is exactly conserved. Since edges are reversed independently, and are statistically independent and follow binomial distributions with parameters and , respectively. Therefore, after edges are reversed with probability , the new degree distribution can be written as
We now define the generating function of the joint in–out-degree distribution after the perturbation by
and similarly define for the original joint in–out-degree distribution. Using (2), we see that these two generating functions are related by
Equation (4) gives the exact change in the joint in–out-degree distribution under edge-reversal noise. It is a degree-level identity and does not require a configuration-model, tree-like, or other random-graph assumption.
Several invariants follow immediately. Since reversal leaves unchanged at every vertex, the total-degree distribution is unchanged. Its generating function,
is therefore invariant. The numbers of vertices and edges are also unchanged, as are all weakly connected components, because the underlying undirected graph is fixed.
Finally, each directed edge contributes one unit to the total in-degree and one unit to the total out-degree of the network. Their mean values are therefore equal and remain invariant under reversal:
Iteration of the transformation and stationary orientation statistics
The transformation can be iterated. Two independent reversal rounds with probabilities and reverse an edge relative to its initial orientation exactly when one, but not both, reversals occur. This happens with probability . After rounds with the same , the probability to finally reverse an edge is the probability that during the rounds the number of partial reversals is an odd number. This is simply the sum for all odd numbers of a binomial distribution with parameters and , which gives
and the joint degree generating function becomes
The factor in Eq. (7) carries the memory of the initial orientation. After rounds, this directional memory is reduced by the factor . For , we have , so this memory vanishes as and . The limiting joint degree distribution is therefore
Equation (9) has a direct interpretation. Conditional on a vertex having total degree , each of its incident edges is equally likely to point inward or outward in the limiting ensemble. Hence, the limiting network remains directed, but its edge orientations no longer retain information about their initial directions and every vertex has equal expected value for its in- and out-degree, while the actual values fluctuate from vertex to vertex. Thus, repeated reversal converges to the uniform distribution over all possible orientations of that skeleton. At , this distribution is reached in a single round, since every edge is then equally likely to have either orientation.
The endpoints are exceptional. At no edge changes direction, whereas at every edge reverses at every round, producing a deterministic two-cycle between the original network and its global reversal. Finally, global reversal does not change the strongly connected components (SCC). Moreover, reversal with probability is equivalent, up to a global reversal, to reversal with probability . SCC statistics are therefore symmetric under . We consequently restrict attention to , over which increasing corresponds to increasing edge orientation noise.
Exact evolution of second-order degree moments
We next consider how reversal noise changes the second-order degree moments. Define the initial second factorial moments of the in- and out-degree and the mixed factorial moment as
and
Differentiating the generating-function transformation in Eq. (4) gives
Thus, the second-order degree moments after one reversal step are determined exactly by the corresponding moments of the original network.
For the mixed factorial moment, Eq. (14) gives
The sign of the quantity in brackets therefore determines whether reversal noise increases or decreases the mixed in–out degree moment.
After rounds with the same reversal probability , the mixed factorial moment is
where
Since as for , Eq. (16) shows explicitly that converges to . At , the random-orientation limit is reached after a single reversal step.
The relevance of Eq. (15) stems from the fact that, for uncorrelated random networks, the percolation transition takes place when
Therefore, the possibility of increasing or decreasing the mixed in–out degree moment opens up the possibility that percolated networks may be destroyed by noise or that non-percolated ones may percolate. However, as we explain in the next section, the new percolation transition cannot be directly derived from Eq. (15).
Percolation under edge reversal with fixed edge pairings
The results in the section above are exact averages over the edge-reversal process for a fixed initial graph. They describe how the degree statistics change under reversal noise, but they do not by themselves determine the existence or size of giant directed components.
Knowing only the new joint in–out-degree distribution after reversal is not enough to predict the percolation behavior of the actual reversed network. In an ordinary directed configuration model, following a randomly chosen directed edge leads to a vertex with probability proportional to its in-degree. The expected number of outgoing edges available from the vertex reached in this way is therefore
This quantity is the mean branching factor for directed exploration. The percolation threshold occurs when it reaches unity, [1].
One might therefore try to apply Eq. (19) directly to the transformed degree distribution. This would amount to constructing a new directed configuration model from the transformed in- and out-degrees, with the stubs paired uniformly at random, with branching factor
Such a construction preserves the transformed degree statistics, but not the edge pairings of the original graph. It therefore differs from the reversal process studied here, in which the same pairs of vertices remain connected and only the edge directions change.
This distinction matters because the preserved pairings contain information relevant to directed percolation that is not encoded in the transformed degree distribution alone. After reversal, a current outgoing edge can arise in two different ways: it can be an original outgoing edge that retained its direction, or an original incoming edge that was reversed. Following these two types of edges reaches vertices through different original stub types and therefore samples different excess-degree distributions. This motivates a two-type branching description, consistent with hidden-stub and correlated-percolation formalisms [4, 5, 6].
Two-type branching matrix
From this point on, we introduce a directed percolation calculation for the problem of edge reversal with fixed edge pairings studied here. We consider the large limit of sparse directed configuration models with joint degree distribution converging to . The total numbers of incoming and outgoing stubs are equal, the stubs are initially matched uniformly at random, and neighborhoods are locally tree-like, so following directed edges through the network can be approximated by a branching process implying that each newly reached vertex generates a number of outgoing edges that can be followed to new vertices, while repeated visits to previously reached vertices are negligible at this stage. A giant directed component appears when this exploration has a positive probability of continuing indefinitely in the large-network limit. Survival of this branching process then identifies the appearance of extensive directed components, including the Strongly Connected Component (SCC) of nodes that are mutually reachable following directed paths. This is the standard setting used in giant-SCC results for directed degree-sequence models [2, 3].
The only additional information needed after reversal is whether a current edge kept its original direction or was reversed. We therefore distinguish two types of edge in the branching process: retained edges and reversed edges. To see why the two types must be distinguished, consider following a current outgoing edge and arriving at its target vertex. If the edge was retained, then it was originally an incoming edge of the vertex that we reach. A vertex with original degrees is therefore reached with probability proportional to its original in-degree, and so distributed as
Once there, its original outgoing edges remain outgoing with probability , while its remaining original incoming edges become outgoing if they are reversed, with probability .
If instead the edge that we followed was itself reversed, then it was originally an outgoing edge of the vertex that we reach. Vertices are therefore sampled with probability
In this case, one of the original outgoing edges has already been used to reach the vertex, leaving such edges, while all original incoming edges remain available to become outgoing through reversal.
To construct the mean offspring matrix, we average the numbers of available outgoing edges using the degree distribution conditioned on the arrival type. We label retained edges as type 1 and reversed edges as type 2, and define as the mean number of outgoing edges of type available at a vertex reached through an edge of type . Here, outgoing always refers to the direction after the perturbation.
For arrival through a retained edge, the original degrees of the vertex reached are distributed according to Eq. (21). Its original outgoing edges are retained with probability , while each of its remaining original incoming edges becomes outgoing with probability . Therefore,
The subtraction of one in the second expression excludes the original incoming edge through which the vertex was reached.
For arrival through a reversed edge, the corresponding degree distribution is Eq. (22). In this case, the arrival edge was originally outgoing, leaving original outgoing edges that can retain their direction, while all original incoming edges can become outgoing through reversal. Thus,
Combining these four conditional averages gives the mean offspring matrix
The rows specify whether the current vertex was reached through a retained or a reversed edge, respectively, and the columns specify whether the next edge followed is retained or reversed.
The same construction can be carried out backward, by following edges against their direction. This interchanges and , but the resulting matrix has the same eigenvalues. Consequently, forward and backward exploration have the same growth threshold. The largest eigenvalue of is
In the Appendix A, we show that this eigenvalue is the effective branching factor of the two-type process. In the configuration-model regime described above, directed exploration becomes extensive when
The same condition governs the appearance of giant in- and out-components and, when both are present, of a giant strongly connected component. The corresponding component-size equations are derived in Appendix A.
At , no edge is reversed, so the two-type description reduces to the usual directed configuration-model result,
At , each edge direction is randomized with equal probability, and
For comparison, let denote the branching factor obtained by discarding the original edge pairings and constructing a new directed configuration model from the transformed degree distribution alone. At , the difference between this degree-only prediction and the branching factor of the actual reversal process is
Thus, even when the edge directions have been completely randomized, a network obtained by reversing directions while preserving the original edge pairings is generally not equivalent to a new configuration-model network constructed only from the resulting degree distribution.
Creation, destruction, and repeated reversal
On the interval , the quantity increases monotonically from 0 to , while decreases from 1 to 0. It follows from Eq. (24) that the branching factor is itself monotonic:
Because is monotonic on , the possibility of a noise-induced transition can be determined entirely from its values at the two endpoints. Using Eq. (25) and Eq. (26), a noise-induced creation of a giant strongly connected component occurs when
so that the network is subcritical at but becomes supercritical as the directions are randomized. Conversely, a destruction transition occurs when
so that a giant strongly connected component present initially is lost as the reversal probability increases. If both endpoint values are on the same side of one, no percolation transition occurs on .
When the endpoint values lie strictly on opposite sides of one, monotonicity guarantees a unique transition probability . At the transition,
Defining , after some algebra we obtain
The minus sign in the expression for selects the solution in the interval . Finally, requiring and to lie on opposite sides of one ensures that Eq. (31) corresponds to the physical percolation transition.
The same framework also applies to repeated reversal. After rounds with the same reversal probability , an edge has the effective reversal probability given by Eq. (7). Substituting into Eq. (24) gives
For , as , and therefore
If , this limiting value is approached from below; if , it is approached from above. When , the branching factor is unchanged by reversal.
Examples
Creation from sources and sinks in a bipartite directed network
Consider an initially acyclic configuration-model ensemble in which half of the vertices are pure sources, with degrees , and the other half are pure sinks, with degrees . Thus every edge in the original bipartite network points from a source to a sink. A directed path therefore stops as soon as it reaches a sink, so the initial network cannot contain a giant strongly connected component.
The joint degree generating function is
The vanishing mixed moment reflects the complete separation between sources and sinks: no vertex has both incoming and outgoing edges initially. Substituting these moments into Eq. (24) gives
At , , consistent with the absence of sustained directed paths. As edges are reversed, however, some of the original source-to-sink edges become sink-to-source edges. Sinks can then acquire outgoing edges and sources can acquire incoming edges, allowing directed paths to alternate between the two vertex classes and creating return routes that were absent in the original orientation.
A giant strongly connected component appears when crosses one. Solving gives
where the root in the interval has been chosen. Such a transition is possible only for , because at complete direction randomization
which exceeds one only when .
For the simplest case, , . By contrast, a degree-only reconstruction based on the transformed degrees gives , and would place the transition at . The difference arises because the degree-only reconstruction discards the original source–sink edge pairings, whereas the actual reversal process preserves them.
Importantly, the transition is produced without adding or removing any edges. Reversal changes only their directions, but this is sufficient to create directed return paths on the same underlying bipartite network and thereby generate a giant strongly connected component. Figure 1 shows numerical simulations of this toy example confirming our predictions.
Figure 1. Creation of a giant strongly connected component in the bipartite ensemble. The solid curve is the solution of the two-type component equations in Appendix A. Symbols show the mean largest-SCC fraction from synthetic configuration-model simulations. Blue and orange dotted vertical lines mark the two-type and degree-only threshold predictions, respectively. The orange dashed curve is the degree-only prediction. Open circles and filled squares show the smaller and larger simulated sizes, respectively; error bars indicate one standard error over 12 realizations.
Destruction in an initially balanced directed ensemble
Consider an initially balanced directed configuration-model ensemble with joint degree generating function
Thus, a fraction of the vertices have one incoming and one outgoing edge, , while the remaining fraction have two incoming and two outgoing edges, . Every vertex therefore has equal in- and out-degree in the original network.
The corresponding moments are
At , the branching factor is
so the initial network is in the supercritical regime and supports a giant strongly connected component.
Edge reversal has the opposite effect from the previous bipartite example. Although the mean in- and out-degrees remain unchanged, individual vertices need no longer remain balanced. For example, a vertex that initially has one incoming and one outgoing edge can, after reversal, end up with two incoming edges or two outgoing edges. Such local imbalances reduce the ability of directed paths to continue in both directions through the network.
Substituting the moments in Eq. (24) for the effective branching factor of the two types gives
Since , this quantity decreases monotonically as increases from 0 to . At complete randomization of the edge directions,
The network therefore passes from the supercritical to the subcritical regime as the reversal probability increases.
The destruction threshold is obtained from , giving
Thus, once approximately 21% of the edges are independently reversed, the branching process becomes subcritical in the large-network limit.
For comparison, reconstructing a new directed configuration model from the transformed degree distribution alone gives
which crosses one at
The degree-only reconstruction therefore predicts the loss of the giant strongly connected component substantially earlier than the pairing-preserving reversal calculation. The difference arises because the actual reversal process keeps the original edge pairings, whereas the degree-only construction retains only the transformed degree statistics. Figure 2 shows numerical simulations, confirming again our predictions.
Figure 2. Destruction of the giant strongly connected component for Eq. (37). The branching prediction is , rather than the degree-only value . The blue solid and orange dashed curves show the pairing-aware and degree-only predictions; matching dotted vertical lines mark their thresholds. Open circles and filled squares show the smaller and larger simulated sizes, respectively, with one-standard-error bars over 12 realizations. Finite graphs retain small SCCs in the subcritical regime, while the extensive fraction vanishes in the random-graph limit.
Degree-only reconstruction can predict the wrong percolation phase
The previous two examples have . In that symmetric case, the degree-only and pairing-preserving branching criteria become equal at , although they can differ for intermediate reversal probabilities. To show that the distinction can be qualitative rather than merely quantitative, consider the degree distribution with characteristic function
This distribution contains three types of vertices: a fraction have degrees , a fraction have degrees , and a fraction have degrees . The network is therefore strongly asymmetric in its in- and out-degree statistics, even though the mean in- and out-degrees remain equal, as required for a directed network. The corresponding moments are
Two combinations of these moments control two different responses to reversal noise:
The first quantity determines the change of the mixed factorial moment , while the second determines the change of the true branching factor . Their opposite signs therefore imply that these two quantities move in opposite directions as increases. Indeed, the degree-only reconstruction gives
which increases with reversal noise and remains larger than one for the entire interval . If one considered only the transformed degree distribution, one would therefore conclude that the network remains in the supercritical regime. The pairing-preserving branching calculation gives a different result:
Because , decreases monotonically with . Initially,
so the network is supercritical. As the edge directions are randomized, however, the branching factor falls and eventually crosses the percolation threshold. Solving gives
Thus the giant strongly connected component is predicted to disappear once the reversal probability exceeds approximately 0.223. The contrast is especially clear at complete direction randomization, :
The two descriptions therefore predict different connectivity phases: the degree-only reconstruction remains supercritical, whereas the pairing-preserving calculation is subcritical. This example clearly shows why the transformed joint degree distribution alone is not sufficient to determine percolation under edge reversal. The quantity , which would be the branching factor of a newly rewired configuration model with the transformed degrees, actually increases with . Nevertheless, the true branching factor of the edge-reversal process decreases because the original edge pairings are preserved and retained and reversed edges sample those pairings differently. Figure 3 shows simulation results confirming these predictions.
Figure 3. Asymmetric destruction example, Eq. (41). The two-type theory predicts the loss of the extensive SCC at , while the degree-only comparison remains supercritical for all . The blue solid and orange dashed curves show the pairing-aware and degree-only predictions, respectively; the blue dotted line marks the pairing-aware threshold. Open circles and filled squares show the smaller and larger synthetic configuration-model sizes, respectively, with one-standard-error bars over 12 realizations. Sampling near the transition is limited and the figure is intended as a consistency check rather than a finite-size scaling study.
Applications to real directed networks
For an empirical directed network, edge reversal can be used as a sensitivity test of how strongly connectivity depends on the observed edge directions. The network connections are kept fixed, each edge is independently reversed with probability , and the resulting response is measured through
These curves show how mutual reachability changes as the edge orientations are progressively randomized. The empirical response can be compared with two configuration-model baselines. The first is the pairing-aware two-type model developed above, which accounts for the different roles of retained and reversed edges. The second is the degree-only reconstruction, in which a new directed configuration model is built from the transformed degree distribution and the original edge pairings are discarded. Differences between the empirical response and either baseline indicate structural information not contained in that particular random-graph description, such as reciprocity, clustering, geometry, motifs, and degree correlations [15, 16, 17].
The same procedure can also be used when edge directions are uncertain rather than deliberately perturbed. A uniform provides a simple reference test, while edge-specific reversal probabilities can be used when confidence in the inferred directions varies from edge to edge.
Creation of strong connectivity in a S. cerevisiae transcriptional regulation network
We illustrate this procedure using the S. cerevisiae transcriptional regulation network distributed by SNAP of Milo et al. [21, 22]. The network contains 690 vertices and 1,094 directed edges, including 12 self-regulatory loops. Removing those loops leaves , , with no isolated vertices. The analysis uses only directed topology; regulatory signs do not enter the reversal process. The largest weakly connected component contains 664 vertices, whereas the observed largest strongly connected component contains only three:
Thus the observed orientation supports very little mutual reachability, despite an almost network-spanning weakly connected component.
The loop-free network has mean degree and factorial moments
The pairing-aware branching factor consequently satisfies
Unlike a case in which reversal merely enlarges an already-supercritical core, this degree sequence satisfies the creation criterion. Solving gives , corresponding to about 17.8 reversed edges on average. The degree-only reconstruction instead predicts . These are configuration-model thresholds inferred from the empirical degree sequence, rather than sharp transition points of this finite fixed network.
Figure 4 compares the empirical reversal response with the two configuration-model baselines. Each empirical point averages 300 independent reversal realizations. The mean largest-SCC fraction increases to at , to at . Randomizing the directions therefore produces a strongly connected core containing about 31% of the network, starting from less than half a percent.
Figure 4. Creation of strong connectivity in the S. cerevisiae transcriptional network under edge-reversal noise. Symbols show the mean largest-SCC fraction on the fixed empirical network over 300 reversal realizations. The solid and dashed lines connect the reported sampled predictions of the pairing-aware two-type and degree-only configuration-model baselines, respectively; the connecting segments are guides to the eye. Vertical lines mark their predicted thresholds and . The inset resolves the small- region. The error bar at is the reported standard error; uncertainties at the other displayed points were not retained in the available numerical summary.
The pairing-aware baseline predicts and , close to the corresponding empirical values. The degree-only reconstruction gives 0.12571 and 0.24740, respectively. Retaining the distinction between original and reversed arrivals therefore improves the description of both the predicted creation threshold and the upper part of the response curve. Agreement is less close at intermediate noise: at and , the two-type baseline gives 0.04399 and 0.11008, respectively, slightly larger than the empirical values.
Gene-regulatory networks provide a natural setting for this type of directionality test because their interpretation depends strongly on which genes regulate which others, and directed loops can be sensitive to reversal of even a small fraction of edges [11]. Uniform reversal probability remains a deliberately simple perturbation: real uncertainty in regulatory directions may be heterogeneous, correlated, or absent for particular interaction types. Finally, changes in SCC structure should not by themselves be interpreted as evidence for changes in oscillatory behavior, dynamical stability, regulatory strength, or biological function.
Destruction of strong connectivity in the San Diego freeway network
A complementary empirical example is provided by the San Diego freeway-and-ramp subnetwork [23, 24]. We use the simplified directed multigraph from [25]. We retain edges whose highway classifications consist exclusively of motorway and/or motorway_link, together with all their incident vertices. Original edge directions, parallel edges, and reciprocal arcs are retained; self-loops are excluded. No restriction to the largest connected component is made. This construction selects a road class within the supplied city boundary, rather than the complete urban street network.
The resulting graph contains , , and its largest SCC initially contains 668 vertices, giving . Its degree moments are
Substitution into Eq. (24) yields
The empirical degree sequence therefore satisfies the destruction criterion, complementing the creation example above. The pairing-aware configuration-model branching factor crosses one at . This value is the threshold of the configuration-model baseline, not an independently measured critical point of the finite road graph.
For each of 300 independent realizations, we assign independent uniform random variates to the labelled edges and reverse an edge whenever its variate is below . Figure 5 shows the resulting mean largest-SCC fraction. It decreases to 0.17157 at , 0.03975 at , and
Figure 5. Destruction of strong connectivity in the San Diego freeway-and-ramp subnetwork. Mean largest-SCC fraction on the fixed empirical graph over 300 independent reversal realizations; error bars indicate one standard error and connecting segments are guides to the eye.
0.00817 at . At fair random orientation,
where the uncertainty is the standard error across realizations. Thus an initial strongly connected core containing about 42% of the vertices is reduced to a largest SCC containing about nine vertices on average.
The endpoint criterion and the empirical reversal response agree on destruction, but the configuration-model threshold does not accurately locate the observed decline: the empirical largest SCC is already small well below . Spatial organization and correlations beyond the single-vertex degree distribution are not represented by this baseline. The finite-network experiment demonstrates loss of a large strongly connected core, rather than a finite-size scaling verification of a critical point. Reversal here is a topological sensitivity test; it does not model traffic capacities, congestion, travel times, or turn restrictions.
Discussion
Independent edge reversal changes the directions of connections while preserving which vertices they join. We obtain an exact description of how this process changes the incoming and outgoing degrees of each vertex while leaving its total degree unchanged. Repeated reversal gradually erases the initial directional organization, making each edge equally likely to point either way. These local changes alter the directed paths through the network and can therefore reshape its large-scale connectivity. Understanding this global response requires keeping track of how the connections were originally arranged. Networks with the same incoming and outgoing degree distributions can respond differently because reversal preserves the original connections. Our theory captures this information by distinguishing paths that arrive along retained edges from those that arrive along reversed edges. This distinction leads to explicit conditions under which reversal creates or destroys a giant strongly connected component.
The synthetic examples show why this distinction matters. Reversal can create strong connectivity in an initially acyclic source–sink network or destroy it in an initially balanced directed ensemble. In the asymmetric example, the transformed mixed moment increases while the pairing-aware branching factor decreases. A degree-only reconstruction consequently predicts a supercritical network even where the pairing-preserving ensemble is subcritical. The transformed degree statistics therefore need not identify even the correct percolation phase.
The empirical examples illustrate both the usefulness and the limits of the theory. In the S. cerevisiae regulatory network, the degree moments satisfy the creation criterion, and reversal expands the largest SCC from approximately 0.435% to 30.6% of the vertices. The pairing-aware prediction closely describes the response at larger reversal probabilities, whereas the degree-only reconstruction underestimates the resulting core. In the San Diego freeway-and-ramp subnetwork, the moments instead satisfy , and the largest SCC decreases from approximately 41.5% to 0.573% of the vertices. The endpoint criterion agrees with the observed destruction, although the empirical decline occurs substantially earlier than the predicted configuration-model threshold.
The scope of these results depends on the level of description. The degree transformation applies to arbitrary directed networks, whereas the percolation predictions rely on the locally tree-like configuration-model ensemble. Geometry, clustering, reciprocity, and correlations between adjacent vertices can therefore produce departures from the predicted response. A small nonzero largest SCC in a finite graph also remains compatible with the absence of an extensive component in the asymptotic theory. The empirical examples demonstrate creation and destruction of large strongly connected cores, but do not establish the predicted critical points through finite-size scaling.
Directional uncertainty provides a further motivation for this analysis. In regulatory networks inferred from gene-expression data, a statistical association may be easier to establish than which gene regulates the other. In causal networks inferred from observational data, distinct edge orientations can be compatible with the same observed dependencies. Brain networks reconstructed from diffusion MRI present a related limitation: the measurements do not distinguish afferent from efferent pathways and therefore generally yield undirected connections. These settings motivate testing how connectivity conclusions depend on assumed orientations. Independent reversal provides a simple reference perturbation, although realistic uncertainty may be heterogeneous or correlated, and additional constraints, such as acyclicity in causal models, require a different orientation-sampling procedure. Our empirical experiments test directional sensitivity rather than estimate errors in the recorded edge directions.
Edge reversal provides a controlled probe of how strongly mutual reachability depends on direction when the underlying connections remain fixed. The pairing-aware theory supplies an explicit baseline for this experiment: it identifies when orientation changes alone can create or destroy extensive strong connectivity, while departures from its predictions reveal the need to account for network structure beyond the original degree distribution.
More broadly, these results show that the same set of connections can support markedly different patterns of mutual accessibility depending on its orientation. Directional disorder can either enable or suppress large-scale connectivity, so randomizing directions need not simply degrade an existing network. This dual role makes directionality an independent dimension of network organization and motivates studying orientation changes alongside the addition, removal, or rewiring of connections.
Data and code
The empirical network data were obtained from publicly available sources: SNAP for the S. cerevisiae transcriptional network [21, 22], and the OpenStreetMap-derived collection distributed through Netzschleuder for the San Diego network [23, 24, 25]. All data generated for the analyses and the code used for network preprocessing, numerical simulations, analytical verification, and figure generation are available from the authors upon request.
Acknowledgments
The authors acknowledge support from Grant No. PID2022-137505NB-C22 funded by MCIN/AEI/10.13039/501100011033 and by ERDF/EU and Grant No. PID2025-169261NB-C21 funded by MCIU/AEI/10.13039/501100011033.
Giant-component equations
We derive the sizes of the giant directed components using the finite-component generating-function approach of Ref. [5]. We consider the sparse, locally tree-like configuration-model regime described in the main text, with original joint degree distribution . Each labelled edge has a single direction and is independently reversed with probability , while its endpoints remain fixed. There are therefore no undirected or bidirectional edges in the branching description.
The configuration-model assumption applies to the original network. Its incoming and outgoing stubs are matched uniformly at random, so the original transition probabilities are
where denotes the original degrees and . Correlations between the in- and out-degree of the same vertex are allowed. After reversal, we retain the distinction between edges that kept their direction and edges that reversed, since these two types sample different original stub distributions.
Finite-component distributions
Let denote the probability that a vertex with original degrees has a finite out-component containing vertices, including the vertex itself. Similarly, is the probability that its finite in-component contains vertices. We also define as the probability that both components are finite and have sizes and , respectively. Their generating functions are
The corresponding unconditional generating functions , , and are obtained by averaging over . All distributions include the average over the independent edge reversals.
The sums run only over finite component sizes. Their total probability can therefore be smaller than one above the percolation threshold. In particular, is the probability that the out-component is finite, whereas is the probability that both components are finite. Consequently, is generally different from above the threshold. Values of the generating functions at unity are understood as limits from below.
With the convention that GIN and GOUT both include the GSCC, their relative sizes are
A vertex belongs to the GIN when its out-component is extensive, and to the GOUT when its in-component is extensive. Membership in the GSCC requires both conditions. Inclusion–exclusion therefore gives
Branch generating functions
We label retained edges as type 1 and reversed edges as type 2. Let be the probability that following an edge of type in its current direction reaches a finite forward branch containing vertices. The count includes the vertex reached by that edge and excludes the vertex from which the traversal started. We define analogously for backward exploration, in which the edge is traversed against its current direction. Because the original stub matching is uniform, these functions do not depend on the original degrees of the vertex from which the edge is followed. They do depend on the edge type, which determines the original stub through which the next vertex is reached.
These two functions are needed to compute and . Consider, for instance, the outgoing cluster size distribution of nodes with degree , . This can be written as
From (59), we obtain its generating function as
and after averaging over , we obtain
where we have defined the shorthand notation
Following the same argument used to derive Eqs. (A5) and (A6), we can obtain a closed system of equations for and . Arrival through a retained edge reaches an original incoming stub, so the original degrees of the vertex reached are distributed according to . The arrival edge has already been used, leaving original incoming edges and original outgoing edges. Thus,
Here, denotes the derivative of with respect to its first argument whereas the factor takes into account the vertex reached. Arrival through a reversed edge instead reaches an original outgoing stub. Its degree distribution is , and the remaining original degrees are and . Therefore,
where is the derivative with respect to the second argument. For backward exploration, an original incoming edge can be traversed against its current direction if it is retained, whereas an original outgoing edge can be traversed in this way if it is reversed. Repeating the same analysis above in this case leads to
where we define
Finally,
and after averaging over , we obtain
Extinction probabilities and the giant in- and out-components
We now evaluate the branch generating functions at unity and define
These quantities are the probabilities that the corresponding forward or backward branches are finite.
Writing and , the forward equations become
Similarly, with and , the backward equations are
The physical solution is the componentwise smallest fixed point in for each pair of equations. It can be obtained by iteration starting from zero. Substituting the root generating functions into Eq. (57) gives
Following Ref. [5], the branching threshold can also be recovered by linearizing the fixed-point equations around the trivial solution. The Jacobian of the forward equations at is
which coincides with Eq. (23). The backward equations give
The two matrices have the same trace and determinant and therefore the same eigenvalues. This recovers the common forward and backward branching threshold derived in the main text.
Joint generating function and the strongly connected component
To compute the GSCC, we need the joint probability that both explorations are finite. Since every edge is purely directed, an incident edge can initiate only one of the two explorations for any realized orientation. The orientation of that edge nevertheless enters both component-size calculations and must be averaged consistently.
To make this explicit, consider a root with original degrees and use the variables introduced in Eq. (1): is the number of original incoming edges that are retained, and is the number of original outgoing edges that are reversed. They are independent and satisfy
The root then has retained outgoing edges and reversed outgoing edges, together with retained incoming edges and reversed incoming edges.
Conditional on these counts, the forward and backward explorations use disjoint incident edges. Independence of their branches in the locally tree-like limit therefore gives
The factor counts the root once in each component.
Averaging over assigns each original incoming edge the joint generating factor
If that edge is retained, it contributes to the backward exploration; if it is reversed, it contributes to the forward exploration. Similarly, averaging over assigns each original outgoing edge the factor
Taking the product of these factors over the original incident edges and then averaging over yields
Thus, the factorization into forward and backward contributions holds when the retained and reversed incident-edge counts are specified. It generally does not survive the average over those counts at fixed original degrees. The reason is that the same orientation variable determines whether an original edge contributes to the forward or to the backward exploration. This dependence is fully accounted for by the sums in Eqs. (75) and (76).
At , Eq. (77) becomes
Finally, substituting this expression and the two marginal generating functions into Eq. (58) gives
As a consistency check, at only retained edges are present. The relevant extinction probabilities then satisfy
and Eq. (79) reduces to
recovering the result for the original directed configuration model.
References
- [1]M. E. J. Newman, S. H. Strogatz, and D. J. Watts, “Random graphs with arbitrary degree distributions and their applications,” Phys. Rev. E 64, 026118 (2001). doi: 10.1103/PhysRevE.64.026118.DOI
- [2]C. Cooper and A. Frieze, “The size of the largest strongly connected component of a random digraph with a given degree sequence,” Comb. Probab. Comput. 13, 319–337DOI
- [3]S. Donderwinkel and Z. Xie, “Universality for the directed configuration model: Metric space convergence of the strongly connected components at criticality,” Electron. J. Probab. 29, 87 (2024). doi: 10.1214/24-EJP1131.DOI
- [4]B. Söderberg, “Properties of random graphs with hidden color,” Phys. Rev. E 68, 026107 (2003). doi: 10.1103/ PhysRev E 68 026107pubmed.ncbi.nlm.nih.gov/14525049
- [5]M. Boguñá and M. Á. Serrano, “Generalized percolation in random directed networks,” Phys. Rev. E 72, 016106 (2005). doi: 10.1103/PhysRevE.72.016106.DOI
- [6]A. Allard, L. Hébert-Dufresne, J.-G. Young, and L. J. Dubé, “General and exact approach to percolation on random graphs,” Phys. Rev. E 92, 062807 (2015). doi: 10.1103/PhysRevE.92.062807.DOI
- [7]C. McDiarmid, “General percolation and random graphs,” Adv. Appl. Probab. 13, 40–60 (1981). doi: 10.2307/1426466.DOI
- [8]S. Linusson, “A note on correlations in randomly oriented graphs,” arXiv:0905.2881 (2009).arxiv.org/abs/0905.2881
- [9]B. Narayanan, “Connections in randomly oriented graphs,” Comb. Probab. Comput. 27, 667–671 (2018). doi: 10.1017/S0963548316000341.
- [10]S. E. Ahnert and T. M. A. Fink, “Clustering signatures classify directed networks,” Phys. Rev. E 78, 036112 (2008). doi: 10.1103/PhysRevE.78.036112.DOI
- [11]R. Itzhack, L. Tsaban, and Y. Louzoun, “Long loops of information flow in genetic networks highlight an inherent directionality,” Systems Biomedicine 1, 47–54 (2013). doi: 10.4161/sysb.24471.DOI
- [12]Y. Rosen and Y. Louzoun, “Directionality of real world networks as predicted by path length in directed and undirected graphs,” Physica A 401, 118–129 (2014). doi: 10.1016/j.physa.2014.01.005.DOI
- [13]V. Domínguez-García, S. Pigolotti, and M. A. Muñoz, “Inherent directionality explains the lack of feedback loops in empirical networks,” Sci. Rep. 4, 7497 (2014). doi: 10.1038/srep07497.
- [14]V. Verbavatz and M. Barthelemy, “From one-way streets to percolation on random mixed graphs,” Phys. Rev. E 103, 042313 (2021). doi: 10.1103/PhysRevE.103.042313.DOI
- [15]N. Rodgers, P. Tiño, and S. Johnson, “Strong connectivity in real directed networks,” Proc. Natl. Acad. Sci. USA 120, e2215752120 (2023). doi: 10.1073/pnas.2215752120.DOI
- [16]A. Allard, M. Á. Serrano, and M. Boguñá, “Geometric description of clustering in directed networks,” Nat. Phys. 20, 150–156 (2024). doi: 10.1038/s41567-023-02246-6.DOI
- [17]M. Boguñá and M. Á. Serrano, “Statistical Mechanics of Directed Networks,” Entropy 27, 86 (2025). doi: 10.3390/e27010086.DOI
- [19]J. Kim and T. Phillips, “On the largest strongly connected component of randomly oriented divisor graphs,” arXiv:2604.05176v2 (2026), preprint.arxiv.org/abs/2604.05176
- [21]R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “Network motifs: simple building blocks of complex networks,” Science 298, 824–827 (2002). doi: 10.1126/science.298.5594.824.DOI
- [22]Stanford Network Analysis Project, “S. cerevisiae transcriptional regulation network,” https://snap.stanford.edu/data/S-cerevisiae.html.
- [23]G. Boeing, “Street Network Models and Measures for Every U.S. City, County, Urbanized Area, Census Tract, and Zillow-Defined Neighborhood,” Urban Sci. 3, 28 (2019). doi: 10.3390/urbansci3010028.DOI
- [24]G. Boeing, “Street Network Models and Measures for U.S. Cities,” Harvard Dataverse. doi: 10.7910/DVN/CUWWWYJ.
- [25]Netzschleuder network catalogue, OpenStreetMap collection, San Diego city network (06-CA-cities_networks:066000_San_Diego), https://networks.skewed.de/net/openstreetmap.




