Critical Asymmetric Ball Twins in Directed Graphs: Structural Characterization, Reciprocity Effects, and Asymptotic Scaling
Fuente:
Zenodo
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Recurso digital |
| Sprache: | Englisch |
| Veröffentlicht: |
Zenodo
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866901649756258304 |
|---|---|
| author | vural, mehmet TOZAR, Ali |
| author_facet | vural, mehmet TOZAR, Ali |
| contents | <p>In asymmetric (quasi-metric) spaces, the forward closed balls B⁺(x, d(x,y)) and B⁺(y, d(y,x)) centered at distinct points x,y with their respective critical radii generally differ.<br>We study pairs where these balls coincide, termed critical asymmetric ball twins (CABT), and prove complete characterization theorems for fundamental graph families.<br>We establish exact CABT density formulas:<br>(i) complete graphs Kₙ achieve density 1 for all n;<br>(ii) star graphs Sₙ have density 1 − 2/n, where the 2(n−1) non-CABT pairs are exactly the hub–leaf pairs;<br>(iii) wheel graphs Wₙ have density 1 − 4/n, with the 4(n−1) non-CABT pairs consisting of hub–rim and adjacent-rim pairs;<br>(iv) cycles satisfy ρ(Cₙ) = 1/(n−1) for even n and 2/(n−1) for odd n, with CABT pairs being exactly the diametrically opposite vertices;<br>(v) paths satisfy ρ(Pₙ) = 2/[n(n−1)], with only the two endpoint pairs being CABT.<br>A structural dichotomy theorem shows hub-dominated graphs are asymptotically CABT-dense (ρ → 1) while sparse families are CABT-free (ρ → 0).<br>In random directed graphs G(n,p,α) with controllable reciprocity α ∈ [0,1], CABT density exhibits strong nonlinear dependence, well-approximated by a cubic polynomial (R² = 0.995).<br>A confound-control experiment with fixed arc count isolates the pure reciprocity effect, revealing that reciprocity monotonically increases CABT density; the non-monotonic U-shaped curve observed in the original model is driven by the joint variation of reciprocity and edge density.<br>Statistical validation via ANOVA (F = 81.9, p < 10⁻⁶), Kruskal–Wallis (H = 483.6, p < 10⁻⁶), and 10,000-iteration bootstrap confirms robustness.<br>We provide a polynomial-time detection algorithm using prefix-ball signatures with O(1) per-pair verification, and connect CABT to domain-theoretic formal balls and metric identification theory.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_19547047 |
| institution | Zenodo |
| language | eng |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Critical Asymmetric Ball Twins in Directed Graphs: Structural Characterization, Reciprocity Effects, and Asymptotic Scaling vural, mehmet TOZAR, Ali quasi-metric spaces asymmetric balls <p>In asymmetric (quasi-metric) spaces, the forward closed balls B⁺(x, d(x,y)) and B⁺(y, d(y,x)) centered at distinct points x,y with their respective critical radii generally differ.<br>We study pairs where these balls coincide, termed critical asymmetric ball twins (CABT), and prove complete characterization theorems for fundamental graph families.<br>We establish exact CABT density formulas:<br>(i) complete graphs Kₙ achieve density 1 for all n;<br>(ii) star graphs Sₙ have density 1 − 2/n, where the 2(n−1) non-CABT pairs are exactly the hub–leaf pairs;<br>(iii) wheel graphs Wₙ have density 1 − 4/n, with the 4(n−1) non-CABT pairs consisting of hub–rim and adjacent-rim pairs;<br>(iv) cycles satisfy ρ(Cₙ) = 1/(n−1) for even n and 2/(n−1) for odd n, with CABT pairs being exactly the diametrically opposite vertices;<br>(v) paths satisfy ρ(Pₙ) = 2/[n(n−1)], with only the two endpoint pairs being CABT.<br>A structural dichotomy theorem shows hub-dominated graphs are asymptotically CABT-dense (ρ → 1) while sparse families are CABT-free (ρ → 0).<br>In random directed graphs G(n,p,α) with controllable reciprocity α ∈ [0,1], CABT density exhibits strong nonlinear dependence, well-approximated by a cubic polynomial (R² = 0.995).<br>A confound-control experiment with fixed arc count isolates the pure reciprocity effect, revealing that reciprocity monotonically increases CABT density; the non-monotonic U-shaped curve observed in the original model is driven by the joint variation of reciprocity and edge density.<br>Statistical validation via ANOVA (F = 81.9, p < 10⁻⁶), Kruskal–Wallis (H = 483.6, p < 10⁻⁶), and 10,000-iteration bootstrap confirms robustness.<br>We provide a polynomial-time detection algorithm using prefix-ball signatures with O(1) per-pair verification, and connect CABT to domain-theoretic formal balls and metric identification theory.</p> |
| title | Critical Asymmetric Ball Twins in Directed Graphs: Structural Characterization, Reciprocity Effects, and Asymptotic Scaling |
| topic | quasi-metric spaces asymmetric balls |
| url | https://doi.org/10.5281/zenodo.19547047 |