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)

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

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)