Core congestion is inherent in hyperbolic networks

DOI10.1137/1.9781611974782.149MaRDI QIDQ4575897zbMATH OpenOpenAlexFDO

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)

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

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)

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$.

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 \)

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
• scientific article; zbMATH DE number 31767 (Why is no real title available?)
• Hyperbolic models for \(\mathrm{CAT}(0)\) spaces
• 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)