Percolation under Edge-Reversal: Creation and Destruction of Strong Connectivity in Directed Networks

We study how the connectivity of a directed network changes when each edge is independently reversed with probability $p$, 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 \emph{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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.20717
Primary Topic
Complex Network Analysis Techniques
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Percolation under Edge-Reversal: Creation and Destruction of Strong Connectivity in Directed Networks

Marián Boguñá, M. Ángeles Serrano
arXiv (Cornell University)
Complex Network Analysis Techniques
preprint

Percolation under Edge-Reversal: Creation and Destruction of Strong Connectivity in Directed Networks

Marián Boguñá, M. Ángeles Serrano
preprint en

Abstract

We study how the connectivity of a directed network changes when each edge is independently reversed with probability $p$, 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 \emph{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.

arXiv (Cornell University)
Complex Network Analysis Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon