Core congestion is inherent in hyperbolic networks

DOI10.1137/1.9781611974782.149zbMATH Open1410.68031arXiv1605.03059OpenAlexW2963518458MaRDI QIDQ4575897FDOQ4575897

Authors: Victor Chepoi, Feodor F. Dragan, Yann Vaxès 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network $G$ admits a core, thus answering in the positive a conjecture by Jonckheere, Lou, Bonahon, and Baryshnikov, Internet Mathematics, 7 (2011) which is based on the experimental observation by Narayan and Saniee, Physical Review E, 84 (2011) that real-world networks with small hyperbolicity have a core congestion. Namely, we prove that for every subset $X$ of vertices of a $delta$-hyperbolic graph $G$ there exists a vertex $m$ of $G$ such that the disk $D(m,4delta)$ of radius $4delta$ centered at $m$ intercepts at least one half of the total flow between all pairs of vertices of $X$, where the flow between two vertices $x,yinX$ is carried by geodesic (or quasi-geodesic) $(x,y)$-paths. A set $S$ intercepts the flow between two nodes $x$ and $y$ if $S$ intersect every shortest path between $x$ and $y$. Differently from what was conjectured by Jonckheere et al., we show that $m$ is not (and cannot be) the center of mass of $X$ but is a node close to the median of $X$ in the so-called injective hull of $X$. In case of non-uniform traffic between nodes of $X$ (in this case, the unit flow exists only between certain pairs of nodes of $X$ defined by a commodity graph $R$), we prove a primal-dual result showing that for any $ho>5delta$ the size of a $ho$-multi-core (i.e., the number of disks of radius $ho$) intercepting all pairs of $R$ is upper bounded by the maximum number of pairwise $(ho-3delta)$-apart pairs of $R$.

Full work available at URL: https://arxiv.org/abs/1605.03059

Recommendations

• Euclidean versus hyperbolic congestion in idealized versus experimental networks
• Traffic congestion in expanders and \((p,\delta )\)-hyperbolic spaces
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Non-hyperbolicity in random regular graphs and their traffic characteristics
• Upper bound on scaled Gromov-hyperbolic \(\delta \)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Helly-type theorems and geometric transversal theory (52A35) Network design and communication in computer systems (68M10)

Cited In (22)

• The hyperbolicity constant of infinite circulant graphs
• Kirszbraun-type theorems for graphs
• Fast approximation and exact computation of negative curvature parameters of graphs
• Eccentricity terrain of \(\delta\)-hyperbolic graphs
• Hyperbolic models for \(\mathrm{CAT}(0)\) spaces
• Title not available (Why is that?)
• Injective hulls of various graph classes
• Gromov hyperbolicity in Mycielskian graphs
• Hyperbolicity on graph operators
• Coarse injectivity, hierarchical hyperbolicity and semihyperbolicity
• Obstructions to a small hyperbolicity in Helly graphs
• Gromov hyperbolicity in the Cartesian sum of graphs
• Projection complexes and quasimedian maps
• Leanness computation: small values and special graph classes
• Applying clique-decomposition for computing Gromov hyperbolicity
• Fast approximation and exact computation of negative curvature parameters of graphs
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Discrete groups of packed, non-positively curved, Gromov hyperbolic metric spaces
• Euclidean versus hyperbolic congestion in idealized versus experimental networks
• On subgroups with narrow Schreier graphs
• Traffic congestion in expanders and \((p,\delta )\)-hyperbolic spaces
• Fellow travelers phenomenon present in real-world networks

This page was built for publication: Core congestion is inherent in hyperbolic networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575897)