PaperlayerView exact revision on arXiv

Source-linked AI summary

A General Capacity Frontier of Complex Networks

Nicholas Kunz, H. Oliver Gao

arXiv:2610.09574v1cs.SIphysics.soc-ph

TL;DR

The paper asks whether maxima can be constrained across disciplinary boundaries despite differences among systems. It represents qualifying systems with paired substrate and process vectors and evaluates a log-additive frontier. The frontier bounded maxima in withheld domains and disciplines, with performance comparable to random resampling, while degrading under deliberate falsification.

  • Problem

    The paper asks whether maxima can be constrained across disciplines despite differences in subject, size, scale, units, and dynamics.

    Source: Discussion · p. 9

  • Method

    SCT represents qualifying systems with standardized graph-invariant and process-signature vectors and evaluates a log-additive frontier.

    Source: Shared Coordinate System · p. 3, Discussion · p. 9, N3S Definition · p. 9

  • Results

    A frontier trained without a domain or discipline bounded withheld maxima with performance comparable to repeated random resampling, while deliberate falsification degraded performance.

    Source: Discussion · p. 9

  • Takeaways & Limitations

    Empirical evidence from another system can inform capacity estimates across substantive boundaries, while domain-specific models remain important for causal explanation and intervention.

    Source: Discussion · p. 9

    Findings are conditioned on 25 systems, 21 graph invariants, seven process signatures, nine estimators, the log-additive decomposition, and daily temporal aggregation.

    Source: Discussion · p. 9

Abstract

from arXiv · show

From cells to cities, ecosystems to economies, complex networks exhibit peak intensities that define their empirical limit. Estimating these limits traditionally requires domain-specific knowledge. We demonstrate that a wide range of complex networks share a capacity frontier that constrains these maxima. We formalize this regularity by proposing Structural Capacity Theory for Network Substrate Structured Systems. These systems couple a fixed network substrate with an observable dynamical process. The frontier is learned from a vector representation of the network substrate and modulated log-additively by a vector representation of the dynamical process. Frontiers trained on one set of domains reliably bound empirical maxima of entirely different ones without observing their peak intensities or simulating their dynamics. Independent learning paradigms converge on consistent upper bounds. Frontier performance is stable under perturbation, yet degrades under deliberate falsification, with no performance gain under ablation. These findings support the capacity frontier as a generalizable constraint that describes how network structure bounds dynamical processes across otherwise unrelated systems.

Shared Coordinate System

A shared representation of network substrates and dynamical processes placed 25 systems in a common coordinate system. The resulting frontier generalized across withheld domains, remained stable under tested perturbations, and degraded under falsification.

Shared Coordinate System

  • Encoding 25 systems from five domains with 21 graph invariants and seven process signatures placed unlike systems in a common vector space.Under repeated 5-fold and 10-fold cross-validation, frontier efficiency was 0.77 and 0.76, respectively.Source: Shared Coordinate System · p. 3

Transfer Across Domains

  • Under domain-level LOGO-CV, frontier efficiency was 0.75 and estimation-observation consensus was 0.84 for withheld domains.For withheld disciplines, efficiency was 0.73; performance was equivalent across domain-level LOGO-CV and repeated k-fold resampling, with median efficiency differences of 0.00 and consensus differences at most 0.01.Source: Transfer Across Domains · p. 4, Figure 2 · p. 5

Consensus Across Paradigms

  • 0.90 pairwise model consensus indicated agreement among nine estimators from three learning paradigms on full-corpus fits.Consensus combined rank agreement, top-weighted overlap, and statistical dependence; the analyses used in-sample predictions.Source: Consensus Across Paradigms · pp. 5–6, Figure 3 · p. 7

Degradation Under Falsification

  • All 12 falsification comparisons showed lower frontier efficiency and consensus, whether models were frozen or retrained.The three procedures deliberately destroyed the correspondence between substrate and process vectors and the target maxima.Source: Degradation Under Falsification · p. 6, Figure 4 · p. 8

Stable Under Perturbation

  • At the highest tested perturbation intensity, efficiency shifts ranged from -0.02 to +0.01, and all 12 perturbations met equivalence margins.Only the highest intensity was formally tested; response curves across intensities were descriptive.Source: Stable Under Perturbation · p. 6, Figure 4 · p. 8

Parsimony Under Ablation

  • No alternative formulation meaningfully outperformed the log-additive decomposition across the four ablations and both performance metrics.The alternatives removed or combined substrate and process features; tests supported non-inferiority of the log-additive formulation.Source: Parsimony Under Ablation · p. 7, Figure 4 · p. 8

Discussion

The frontier transfers across disciplinary boundaries and remains stable under perturbation, while deliberate falsification degrades performance. Its practical interpretation is limited by unresolved slack and the scope of the tested systems and representations.

Discussion

  • A frontier trained without a domain or discipline bounded withheld maxima with performance comparable to random resampling, across differences in subject, size, scale, units, and dynamics.This supports using empirical evidence beyond a system’s own substantive boundary.Source: Discussion · p. 9
  • The frontier does not require dynamical-process models, but its slack was nearly 3 orders of magnitude higher than the maximum rate and remains unclear.Possible explanations include a loose envelope, unequal observation windows, measurement differences, or a combination.Source: Discussion · p. 9
  • Perturbations generally preserved frontier performance, but falsifications that destroyed representation–target correspondence degraded it, unrecoverably even after retraining.Estimator consensus also degraded only after falsification and ablation.Source: Discussion · p. 9
  • Findings are conditioned on 25 systems, 21 graph invariants, 7 process signatures, 9 estimators, log-additive decomposition, and daily aggregation; decomposition exhaustiveness remains unresolved.Broader corpora, alternative representations, learning paradigms, and temporal scales provide direct tests.Source: Discussion · p. 9

Methods

The methods define eligible systems through a fixed network substrate, an attributable observed process, and its measurable maximum rate. They then describe the corpus and how substrates and processes were operationalized.

N3S Definition

  • An N3S requires a fixed substrate, an observable dynamical process corresponding to it, and a measurable maximum rate corresponding to that process.Systems without an identifiable substrate or with aggregate observations lacking substrate attribution are excluded.Source: N3S Definition · p. 9

Data and Corpus Composition

  • The corpus contains 25 systems across five broad domains, with five disciplines per domain and one record per system.Substrates range from 5 to 10,356,390 nodes and 10 to 7,220,486,175 edges; maximum rates range from 3 to 1,323,743 observations per day.Source: Data and Corpus Composition · p. 10

Network Substrate Construction

  • Substrates were treated as fixed, static, unweighted, undirected simple graphs, converting directed or weighted edges and removing multi-edges and self-loops while retaining isolated nodes.Nodes represent units; edges represent native connections or constructed associations.Source: Network Substrate Construction · p. 10

Dynamical Process Construction

  • Dynamical processes were built from empirical observations, discretized or counted in daily intervals, and represented as chronologically ordered daily rate series.One exception reconstructed celegans developmental transitions from published timings using a 30-day dauer duration; source conventions determined interval inclusion.Source: Dynamical Process Construction · p. 10

Maximum Rate Target

The target is each system’s log-transformed maximum rate over its recorded observation window. Substrates and processes are encoded as standardized feature vectors for frontier estimation.

Maximum Rate Target

  • The target is the log-transformed maximum rate realized across each system’s observation window, and the frontier remains conditional on that recorded duration.Observation windows were held at their recorded lengths because maxima can grow with window length.Source: Maximum Rate Target · p. 11

Encoding and Standardization

  • Each substrate is encoded with 21 graph invariants and each process with 7 process signatures, then centered and scaled using in-sample means and population standard deviations.Zero standard deviations are replaced by 1; means and scales are fit strictly in-sample.Source: Encoding and Standardization · p. 11
  • The feature set admits classical, deterministic, global, finite descriptors without arbitrary thresholds or external parameters; complete bipartite substrates use exact analytical invariant expressions.The analytical expressions avoid instantiating billions of edges.Source: Encoding and Standardization · p. 11

Frontier Learning

Frontier learning combines a structural upper-envelope with a process contribution in a two-stage log-additive formulation. The stages use quantile-based fitting to estimate a bound on log-transformed maxima.

Frontier Learning

  • The estimated frontier is the sum of structural and process components, and bounds log-transformed maxima subject to slack and potential violations.The formulation is log-additive in the standardized substrate and process representations.Source: Frontier Learning · p. 11
  • Stage 1 fits the structural component to maxima by asymmetric regression at τC = 0.99; stage 2 fits process signatures to signed slack at τR = 0.50 and centers that contribution before summing.Centering the process-stage training mean fixes its additive offset while leaving the structural component unchanged.Source: Frontier Learning · p. 12
  • The learning paradigms include linear parametric estimators, non-linear ensembles, and neural networks, each using the quantile assigned to its active stage.The supplied methods describe linear quantile regression and LAWS, quantile forest and boosted models, and MLP and input-convex networks.Source: Frontier Learning · p. 12

Performance Metrics

Frontier performance is assessed through containment and fidelity, using paired metrics because neither alone establishes both. The Efficiency Index measures boundary containment and tightness, while the Consensus Index measures fidelity across predicted and observed values and among estimators.

Performance Metrics

  • The Efficiency Index (EI) combines non-violation, bounded mean-violation, and mean-slack terms; perfect efficiency requires no violations and no slack.Mean violation and mean slack are normalized by the sample mean absolute target and expressed in natural-log units.Source: Performance Metrics · p. 12
  • The Consensus Index (CI) combines rescaled Spearman rank correlation, top-weighted Rank-Biased Overlap, and distance correlation.Its components capture monotonic ordering, top-capacity overlap, and statistical dependence.Source: Performance Metrics · p. 13
  • EI and CI are complementary: a high, slack-heavy constant frontier can score well on EI but poorly on consensus, while a strong ranking can fail to bound observations.A valid capacity frontier must demonstrate both containment and fidelity.Source: Performance Metrics · p. 13

Resampling and Leakage Control

Generalization is tested with repeated k-fold and leave-one-group-out resampling at domain and discipline levels. Standardization and model fitting use training data only, and out-of-sample inference excludes target values and raw rate series.

Resampling and Leakage Control

  • Four resampling regimes assess generalization: repeated 5-fold and 10-fold cross-validation, plus domain-level and discipline-level LOGO-CV.The LOGO-CV regimes withhold one of five broad domains or one of 25 disciplines; k-fold resampling uses 30 random reshufflings.Source: Resampling and Leakage Control · p. 13
  • Within each fold, standardizers, estimators, and the process-centering mean are fit exclusively on the training set.Estimators are freshly cloned for each fold, and the held-out system's target and raw rate series are unavailable at inference.Source: Resampling and Leakage Control · p. 13
  • Negative-control corpora and additive-noise scales are specified using full-corpus operations, while stress-test standardizers and estimators are fit on each corresponding training set.Source: Resampling and Leakage Control · p. 13

Perturbation, Falsification, Ablation

The evaluation perturbs substrate graphs, graph and process features, and dynamical rate series while retaining original targets; falsification instead breaks the representation–target mapping. Ablations compare the log-additive decomposition with feature-restricted, joint-feature, and interaction alternatives.

Perturbation, Falsification, Ablation

  • Network-substrate perturbations modify graphs through degree-preserving rewiring, edge densification, or node removal, then recompute graph invariants.Node removal uses induced subgraphs; some graph perturbations use deterministic approximations.Source: Perturbation, Falsification, Ablation · pp. 13–14
  • Dynamical-process perturbations apply power-law scaling, trailing-mean smoothing, or bootstrapping to rate series and recompute process signatures.The perturbation procedures retain each system's original target.Source: Perturbation, Falsification, Ablation · p. 14
  • Graph invariants and process signatures are also perturbed separately through additive noise, multiplicative jitter, and coordinate masking before standardization.The retained coordinate count is controlled by a retention fraction.Source: Perturbation, Falsification, Ablation · p. 14
  • Three falsification procedures deliberately destroy the mapping from substrate and process vectors to the target: target permutation, random generation, and vector generation.Source: Perturbation, Falsification, Ablation · p. 14
  • Ablations compare the log-additive decomposition with invariants-only, signatures-only, joint-feature, and interaction-term alternatives.The interaction alternative adds 147 pairwise coordinates formed from 21 network invariants and 7 process signatures.Source: Perturbation, Falsification, Ablation · p. 14

Evaluation and Statistical Inference

The evaluation summarizes estimator-by-domain comparisons across repetitions and uses paired differences against regime-specific baselines. Statistical tests address equivalence, degradation, and non-inferiority, with adjustments for multiple testing; full-corpus consensus tests are descriptive.

Evaluation and Statistical Inference

  • Inference summarizes 45 estimator-by-domain comparisons over 30 repetitions, with paired differences computed against regime-specific baselines.Perturbation and ablation comparisons use repetition means; consensus uses seed-averaged predictions except for stochastic perturbations.Source: Evaluation and Statistical Inference · pp. 14–15
  • One-sided Wilcoxon signed-rank tests assess paired differences, while TOST tests equivalence and separate tests evaluate falsification degradation and ablation non-inferiority.Inference is conditional on the panel, whose shared estimators and cross-validation folds may affect p-value calibration.Source: Evaluation and Statistical Inference · p. 15
  • Holm–Bonferroni adjustments are applied separately for EI and CI across five test families, using a 0.05 significance threshold.The families are resampling, perturbation, falsification, simple ablations, and complex ablations.Source: Evaluation and Statistical Inference · p. 15
  • Full-corpus consensus tests are descriptive, using seed-averaged predictions and median pairwise consensus across 36 estimator pairs.Original fits are frozen for evaluation on the highest-intensity perturbed and falsified corpora; ablations are refit on the original corpus.Source: Evaluation and Statistical Inference · p. 15

Implementation and Reproducibility

The analyses used pinned Python dependencies and seeded stochastic procedures, with deterministic execution settings and reproducibility caveats documented.

Implementation and Reproducibility

  • Analyses used Python 3.11.9, with pinned graph, data, estimator, and plotting dependencies; unspecified settings followed library defaults.The listed dependencies include python-igraph, NumPy, SciPy, pandas, scikit-learn, XGBoost, PyTorch, and matplotlib.Source: Implementation and Reproducibility · p. 15
  • Randomized procedures used seed 42 with fixed repeat-index offsets; permutations, folds, and perturbation realizations came from seeded generators.Source: Implementation and Reproducibility · p. 15
  • PyTorch deterministic algorithms ran in warn-only mode, CUDA was used when available, and reproduced results remain subject to floating-point imprecision.Source: Implementation and Reproducibility · p. 15

Additional Information

Supplementary materials are listed, and correspondence is directed to N. Kunz.

Additional Information

  • Supplementary information comprises Tables 1–9 and Notes 1–2; correspondence and materials requests should be addressed to N. Kunz.Source: Additional Information · p. 16

Supplementary Tables

The supplementary tables document corpus observation and data-processing conventions, feature definitions, and evaluation protocols, including perturbation rules for complete bipartite network substrates. They specify exact calculations for node removal and deterministic approximations for rewiring and densification.

Supplementary Tables

  • Corpus maxima are conditional on native, non-standardized observation windows, and series conventions vary between complete daily records, event-only records, and weekly chickenpox totals converted to daily averages.The seven API systems also use fixed script query dates; n is the inclusive date span and need not equal series length L.Source: Supplementary Tables · p. 27
  • Supplementary evaluation tables define descriptive domain-transfer summaries and paired tests for resampling, perturbation, falsification, and decomposition non-inferiority, with inference conditional on a shared estimator-domain panel.The summaries use 30 seeds and nine estimators; the paired contrasts use 45 estimator-by-domain cells across five domains.Source: Supplementary Tables · pp. 28–31, Table 2 · p. 28
  • Invariant and process-signature features are admitted only when they are global, deterministically computable, finite, and non-trivially variable, with definitions specifying edge cases and conventions.Graph descriptors depend solely on topology, while process descriptors depend solely on the rate series and use consecutive included observations for lag and trend calculations.Source: Supplementary Tables · pp. 32–33
  • Stress tests pair 30 model-fitting seeds with stochastic perturbation realizations or a deterministic realization, retain original maximum targets, and assess effects across 45 estimator-by-domain cells.Seven-point intensity grids include identity scaling; the most severe tested setting is not always the largest parameter value.Source: Supplementary Tables · p. 34

Supplementary Note 1: Complete Bipartite Perturbations

  • For four very large complete bipartite substrates, node removal is computed exactly from fold sizes, whereas rewiring and densification use a deterministic degree-class approximation.The explicit graphs can contain up to 7.2 billion edges; node removal uses 30 realizations, while the other two perturbations use one.Source: Supplementary Note 1: Complete… · p. 35
  • Complete-bipartite perturbations interpolate invariants under rewiring and adjust degree, edge-count, and selected invariant estimates under densification.Rewiring interpolates each invariant between its exact K_m,n value and Φ using α = 1 − (1 − ϵ)^2. Densification adds a = min(⌊ϵM⌋, C) edges among within-fold vertex pairs, adjusts degrees and M′, scales articulation points, bridges, and assortativity by 1 − q, and updates clustering.Source: Supplementary Note 1: Complete… · p. 35

Supplementary Note 2: Corpus Processing Conventions

  • Corpus processing applies explicit date, missing-speed, loader-lag, timestamp, and entity-matching conventions.The federal series excludes non-positive awards and out-of-range start dates; zero speeds are treated differently in metrla and pemsbay. Other conventions include dropping incomplete Montevideo hours, converting GPS timestamps to UTC without leap-second correction, retaining an undated 12-node crop network, and isolating unmatched country names and spelling variants.Source: Supplementary Note 2: Corpus… · p. 36
Loading 2610.09574v1…