Back to search
2203.13943

How fragile is your network? More than you think.

Jeremie Fish, Mahesh Banavar, Erik Bollt

incompletemedium confidence
Category
Not specified
Journal tier
Specialist/Solid
Processed
Sep 28, 2025, 12:56 AM

Audit review

The paper defines fragility F_δ(G) via the complete-graph baseline f_comp and claims that complete equitable bipartite graphs (CEB_n) are asymptotically robust (F_δ(CEB_n) → 0) . It asserts an exact formula for r* on CEB graphs by “following the logic” used for complete graphs (its Eq. (20)), but does not supply a rigorous bipartite analogue of the ‘splitting squares’ extremal step or the discrete convexity argument needed to justify the maximization of kept edges under an LCC ≤ c constraint . The subsequent limit analysis for F_δ treats several special cases (e.g., c = n − k, k fixed; and δ = 1/2) and then generalizes with heuristic language rather than a uniform argument for all fixed δ ∈ (0,1) . By contrast, the model’s solution provides the needed combinatorial extremal argument on K_{p,q}, uses the discrete convexity of S(s) = ⌊s^2/4⌋, and constructs near-tight subgraphs to show f_CEB_n(δ) = f_comp(δ) + O(1/n), hence F_δ(CEB_n) = O(1/n) → 0. The model is correct; the paper’s conclusion is plausible and matches the model, but the proof is incomplete at key steps.

Referee report (LaTeX)

\textbf{Recommendation:} major revisions

\textbf{Journal Tier:} specialist/solid

\textbf{Justification:}

The work provides a clear, operational definition of network fragility and introduces asymptotic robustness with a compelling comparison to the complete-graph baseline. The claim that CEB graphs are asymptotically robust is correct, but the proof omits a key extremal step in the bipartite case and relies on special-case limits before generalizing. Adding a discrete-convexity/majorization lemma and an explicit construction to realize the upper bound would resolve the main gap and raise the paper’s rigor.