# Congestion in networks and manifolds,
and fair-division problems

Dong Zhang  Department of Mathematics, University of Southern California, Los
Angeles CA 90089-2532, U.S.A<EMAIL_ADDRESS>
###### Abstract.

Several large scale networks, such as the backbone of the Internet, have been
observed to behave like convex Riemannian manifolds of negative curvature. In
particular, this paradigm explains the observed existence, for networks of
this type, of a “congestion core” through which a surprising large fraction of
the traffic transits, while this phenomenon cannot be detected by purely local
criteria. In this practical situation, it is important to estimate and predict
the size and location of this congestion core. In this article we reverse the
point of view and, motivated by the physical problem, we study congestion
phenomena in the purely theoretical framework of convex Riemannian manifolds
of negative curvature. In particular, we introduce a novel method of fair-
division algorithm to estimate the size and impact of the congestion core in
this context.

This work was partially supported by the grant DMS-1711297 from the US
National Science Foundation.

##  1\. Introduction

###  1.1. Congestion on networks

Traffic congestion problems are critical in the study of network
transportation, from rush-hour traffic jams on city highways to routing data
between internet users. With applications to internet traffic, biological and
social sciences, and material transportation, understanding the key structural
properties of large-scale data networks is crucial for analyzing and
optimizing performances, and for improving security and reliability [13].

In recent years, a great amount of empirical results have shown that many
different types of data networks share features with negatively curved graphs
with small hyperbolicity constants [1, 5, 7, 9, 10, 11, 12, 13, 14]. A
consequence of this, consistent with experimental data, is that a large
percentage of the traffic between vertices (nodes) tends to go through a
relatively small subset of the network. This approach is based on a common and
broadly applied method using insights from Riemannian geometry to study large
scale networks. In particular, E. Jonckheere, M. Lou, F. Bonahon and Y.
Baryshnikov [10] used this paradigm to predict the existence of a congestion
core in negatively curved networks, which turned out to be consistent with
observational data in [13].

On a more theoretical level, V. Chepoi, F. Dragan and Y. Vaxès [6] proved a
more quantitative result: A Gromov $\delta$-hyperbolic space admits a
congestion core which intercects at least one-half of all geodesics of the
space. They also found that such a core admits a radius of $4\delta$.

Our goal is to better relate the congestion in a network to its geometric
characteristics, such as its scale and curvature. In particular, we want to
improve the quantitive measure of the density of congestion, namely, the
percentage of all geodesic passing through a core, as well as providing
methods to identify the location of the congestion core.

With is goal in mind, we reverse the point of view and, motivated by the
congestion network problems, we consider similar properties for Riemannian
manifolds. In particular, we exploit a completely new idea for this type of
problem, borrowed from the general area of fair division algorithms; see the
Fair-Cut Theorem 3 below.

###  1.2. The main theorem and its supporting properties

Our more precise result currently requires that we consider manifolds of
constant negative curvature. We believe that a similar property should hold
for variable negative curvature.

Recall that a Riemannian manifold is _convex_ if any two points are joined by
a unique geodesic arc, whose interior is disjoint from the boundary of the
manifold. In particular, a compact convex manifold is always diffeomorphic to
a closed ball.

######  Theorem 1 (Main Theorem).

Let $M$ be a compact convex $m$-dimensional Riemannian manifold with constant
negative sectional curvature $-k^{2}$, with $k>0$. Then, there exists a point
$x_{0}\in M$ and a universal radius
$r_{0}=\frac{1}{k}\log\left(\sqrt{2}+1\right)$, such that at least
$\frac{1}{m+1}$ of all the geodesics of the manifold pass through the ball
$B(x_{0},r_{0})$.

The dependence of the estimate on the dimension $m$ is certainly a flaw for
applications to network. However, see Conjecture 23 in §6.2 for a conjectured
uniform bound coming from our approach.

Our proof of Theorem 1 relies on two intermediate steps. The first one uses
the following fundamental property of spaces of negative curvature.

In a convex Riemannian manifold $M$ of negative curvature $M$, a point $x\in
M$ and a unit vector $v\in T_{x}^{1}M$ determine a _half-space_ $H(x,v)$,
consisting of all $y\in M$ such that the geodesic $[x,y]$ makes an angle
$\leqslant\frac{\pi}{2}$ with $v$ at $x$.

######  Theorem 2 (Blocked View Theorem).

Let $M$ be a convex Riemannian manifold of negative sectional curvature
bounded above by $-k^{2}$, with $k>0$. Then, there exist a universal radius
$r_{0}=\frac{1}{k}\log\left(\sqrt{2}+1\right)$ satisfying the following
property: for every $x$, $p\in M$, the set of $q\in M$ such that the geodesic
$[p,q]$ meets the ball $B(x,r_{0})$ contains the whole half-space
$H(x,v_{p})$, where $v_{p}$ is the unit tangent vector of the geodesic $[p,x]$
at $x$.

In other words, the view of $H(x,v_{p})$ from the point $p$ is completely
blocked by the ball $B(x,r_{0})$. Such a property clearly fails if the
curvature is allowed to approach 0.

This leads us to investigate the volumes of half-spaces $H(x,v)$ in $M$. In
Section 4, we introduce a geometric quantity that we call the _fair-cut index_
of the manifold $M$. It is defined as

$\Phi(M)=\max_{x\in M}\min_{v\in
T_{x}^{1}M}\frac{\operatorname{vol}{H(x,v)}}{\operatorname{vol}M},$

The next big idea in the proof of Theorem 1 is the following.

######  Theorem 3 (Fair-Cut Theorem).

Let $M$ be a compact convex $m$-dimensional Riemannian manifold with non-
positive constant sectional curvature that is also compact and convex. Then,

$\Phi(M)\geqslant\frac{1}{m+1}.$

Although our proof currently requires the curvature to be constant, this
hypothesis is likely to be unnecessary.

A point $x_{0}$ where the maximum $\Phi(M)$ is attained is a fair-cut center
for $M$. The Fair-Cut Theorem can be rephrased as saying that every hyperplane
passing through a fair-cut center cuts $M$ into pieces whose volume is at
least $\frac{1}{m+1}$ times the volume of the whole manifold.

In Proposition 21, we show that the fair-cut centers form a convex subset of
$M$. In practice, this set is very often reduced to a single point, and the
fair-cut center is unique.

##  2\. Counting geodesics

###  2.1. Counting geodesics on a graph

To motivate the Riemannian setup, we first consider the case of graphs (or
networks), which provides the motivation for this work.

A _graph_ $G$ consists of a set $V$ of _vertices_ (or _nodes_) and a set $E$
of _edges_ (or _links_), such that every edge connects two vertices. The graph
is _connected_ if any two vertices $p$, $q\in V$ can be connected by a path in
$G$, namely by a finite sequence of edges such that any two consecutive edges
share an endpoint.

If we assign a positive length to each edge of $E$ (for instance a uniform
length $1$), this defines a _length_ for each path in $G$, namely the sum of
the lengths of the edges in the path. This defines the metric on the vertex
set $V$, where the distance between two vertices is the shortest length of a
path joining them. A path in $G$ is _geodesic_ if its length is shortest among
all paths connecting its endpoints. We are interested in the set $\Gamma(G)$
of (oriented) geodesics of $G$.

An important case is when the geodesic connecting two vertices $p$, $q\in V$
is unique. In this case, we can label this geodesic as $[p,q]$. Then, the set
$\Gamma(G)$ is then the same as the square $V\times V$ of the vertex set $V$.
In particular,

$\left|\Gamma(G)\right|=|V|^{2},$

where $|\cdot|$ measures the size of a set.

To study congestion phenomena in a connected graph $G$, we want to count the
number of geodesics on a graph $G=(V,E)$ that pass through a given vertex
$x\in V$, or more generally near that vertex, and compare it to the total
number of geodesics.

With this in mind, we introduce the set

$C(x)=\\{\gamma\in\Gamma(G);x\in\gamma\\}$

of _geodesic traffic_ passing through the vertex $x\in V$, as well as, for
$r>0$, the _geodesic traffic set through the ball $B(x,r)$_

$C(x,r)=\\{\gamma\in\Gamma(G);d(x,\gamma)\leqslant r\\}.$

Here $d(x,\gamma)$ denotes the shortest distance between $x$ and a vertex of
the path $\gamma$.

These are quantified by the numbers

$\displaystyle D(x)$ $\displaystyle=\frac{|C(x)|}{|\Gamma(G)|}$ $\displaystyle
D(x,r)$ $\displaystyle=\frac{|C(x,r)|}{|\Gamma(G)|}$

which measure the density of traffic passing through the vertex $x$, or
through the ball $B(x,r)$.

In this discrete setting, the sets $C(x)$ and $C(x,r)$ of course coincide when
$r$ is less than the length of the shortest edge of $G$.

###  2.2. Counting geodesics in a Riemannian manifold

We want to extend these ideas from graphs and networks to Riemannian
manifolds.

Let $M$ be a compact Riemannian manifold with boundary. It is _convex_ if any
two points $p$, $q\in M$ can be connected by a unique geodesic $[p,q]$,
meeting the boundary only at its endpoints (if at all). In particular, $M$ is
then diffeomorphic to a closed ball.

In this case, we can identify the set $\Gamma(M)$ of geodesics of $M$ to the
product $M\times M$, and it makes sense to quantify the size of $\Gamma(M)$ as
$|\Gamma(M)|=(\operatorname{vol}{M})^{2}$ where $\operatorname{vol}M$ is the
volume of $M$.

By analogy with the case of graphs, we then introduce the _geodesic traffic
set through the ball $B(x,r)$_ as

$C(x,r)=\\{(p,q)\in M\times M;[p,q]\cap B(x,r)\neq\emptyset\\},$

and the _density of the geodesic traffic passing through $B(x,r)$_

$D(x,r)=\frac{\operatorname{vol}{C(x,r)}}{(\operatorname{vol}{M})^{2}}$

where, for the volume form $d\mu$ of $M$, the volume
$\operatorname{vol}{C(x,r)}$ is defined by

(1) $\operatorname{vol}{C(x,r)}=\int_{C(x,r)}d\mu(p)\,d\mu(q).$

Note that, in this manifold setting, we are not interested in the geodesic
traffic set passing through a single point, since it has measure 0 for the the
volume form of $M\times M$ (except in the trivial case where $\dim(M)\leqslant
1$).

##  3\. The Blocked View Theorem

We will restrict our attention to Riemannian manifolds of negative sectional
curvature, which is the main framework where convexity occurs and is stable
under perturbation. The Blocked View Theorem below is typical of negative
curvature, and will provide a key estimate for our analysis.

We begin with a definition. Recall that $[p,q]$ denotes the geodesic arc going
from $p$ to $q$.

######  Definition 4 (The blocked view).

Let $M$ be a compact convex Riemannian manifold. For $p$, $x\in M$ and a
radius $r>0$ the _blocked view set_ $C_{p}(x,r)$ is

$C_{p}(x,r)=\big{\\{}q\in M;[p,q]\cap B(x,r)\neq\emptyset\big{\\}}.$

In other words, $C_{p}(x,r)$ is the set of points $q$ whose view from $p$ is
blocked by the ball $B(x,r)$.

Then, Equation (1) can be rewritten as

(2) $\operatorname{vol}{C(x,r)}=\int_{p\in
M}\operatorname{vol}{C_{p}(x,r)}~{}d\mu(p).$

A point $x\in M$ and a unit tangent vector $v\in T_{x}^{1}M$ determine a
_half-space_

$H(x,v)=\big{\\{}q\in M;~{}\langle v_{q},v\rangle\leqslant 0\text{ for the
tangent vector }v_{q}\text{ of }[q,x]\text{ at }x\big{\\}}.$

######  Theorem 5 (Blocked View Theorem).

Let $M$ be a compact convex Riemannian manifold whose sectional curvature is
bounded above by $-k^{2}$ with $k>0$. Then, there exists a universal radius
$r_{0}=\frac{1}{k}\log(\sqrt{2}+1)$ such that, for any two distinct points
$x$, $p\in M$, the blocked view set $C_{p}(x,r_{0})$ contains the half-space
$H(x,v_{p})$ determined by the tangent vector $v+p$ of the geodesic $[p,x]$ at
$x$.

In other words, the view of the whole half-space $H(x,v_{p})$ from the point
$p\in M$ is completely blocked by the ball $B(x,r_{0})$. We call the universal
radius $r_{0}=\frac{1}{k}\log(\sqrt{2}+1)$ the _blocking radius_ corresponding
to the curvature bound $-k^{2}$.

The proof of Theorem 5 is based on the following two lemmas.

######  Lemma 6.

In the $m$-dimensional space $H^{m}_{k^{2}}$ of constant curvature $-k^{2}$,
consider two geodesics $[\bar{x},\bar{y}]$ and $[\bar{x},\bar{z}]$ making a
right angle at $\bar{x}$. Then, the distance from $\bar{x}$ to the geodesic
$[\bar{y},\bar{z}]$ is uniformly bounded by
$\frac{1}{k}\log\left(\sqrt{2}+1\right)$.

###### Proof.

After rescaling the metric and restricting attention to a totally geodesic
plane containing the three points $\bar{x}$, $\bar{y}$ and $\bar{z}$, we can
arrange that $k=1$ and $m=2$, and identify $H^{2}_{1}$ to the Poincaré disk
model for the hyperbolic plane. After applying a suitable isometry, we can in
addition assume that $\bar{x}$ coincides with the center $O$ of the disk.
Also, moving $\bar{y}$ and $\bar{z}$ away from $x$ increases the distance from
$\bar{x}$ to $[\bar{y},\bar{z}]$. It therefore suffices to consider the case
where $\bar{y}$ and $\bar{z}$ are in the circle at infinity
$\partial_{\infty}H^{2}_{1}$. In this special case, a simple computation in
the Poincaré model shows that the distance from $x=O$ to $[\bar{y},\bar{z}]$
is exactly equal to $\log\left(\sqrt{2}+1\right)$. This provides the required
bound in the general case. ∎

######  Lemma 7.

Let $M$ be a convex Riemannian manifold whose sectional curvature is uniformly
bounded above by $-k^{2}<0$. Given a geodesic triangle $xyz$ in $M$ with a
right angle at $x$ consider, in the space $H^{m}_{k^{2}}$ of constant
curvature $-k^{2}$, a triangle $\bar{x}\bar{z}\bar{p}$ with a right angle at
$\bar{x}$ and whose legs are such that $d(x,y)=d(\bar{x},\bar{y})$ and
$d(x,z)=d(\bar{x},\bar{z})$. Then, the distance from $x$ to the geodesic
$[y,z]$ is less than or equal to the distance from $\bar{x}$ to
$[\bar{y},\bar{z}]$. Namely,

$d\big{(}x,[y,z]\big{)}\leqslant d\big{(}\bar{x},[\bar{y},\bar{z}]\big{)}.$

Figure 1. Comparing the triangles $xzp$, $x^{\prime}z^{\prime}p^{\prime}$ and
$\bar{x}\bar{z}\bar{p}$

###### Proof.

Consider another comparison triangle $x^{\prime}y^{\prime}z^{\prime}$ in
$H^{m}_{k^{2}}$, where $d(x,y)=d(x^{\prime},y^{\prime})$,
$d(x,z)=d(x^{\prime},z^{\prime})$ and $d(y,z)=d(y^{\prime},z^{\prime})$. Using
Proposition 1.7 of [2, Chap. II.1], ,

(3) $d(x,[y,z])\leqslant d(x^{\prime},[y^{\prime},z^{\prime}]).$

By Toponogov’s theorem (see for instance [4, Chap. 2]), the angle of
$x^{\prime}y^{\prime}z^{\prime}$ at $x^{\prime}$ is greater than the angle of
$xyz$ at $x$, so it is larger than $\pi/2$. As a consequence, in the constant
curvature space $H^{m}_{k^{2}}$, the geodesic triangles
$x^{\prime}y^{\prime}z^{\prime}$ and $\bar{x}\bar{y}\bar{z}$ are such that
$d(x^{\prime},y^{\prime})=d(\bar{x},\bar{y})$,
$d(x^{\prime},z^{\prime})=d(\bar{x},\bar{z})$, and the angle of
$x^{\prime}y^{\prime}z^{\prime}$ at $x^{\prime}$ is greater than the angle of
$\bar{x}\bar{y}\bar{z}$ at $\bar{x}$. Moving these comparison triangles by
isometries of $H^{m}_{k^{2}}$, we can arrange that
$x^{\prime}y^{\prime}z^{\prime}$ and $\bar{x}\bar{y}\bar{z}$ are contained in
the same 2-dimensional space $H^{2}_{k^{2}}\subset H^{m}_{k^{2}}$, modeled as
the Poincaré disk. In addition, we can arrange that $x^{\prime}=\bar{x}$,
$y^{\prime}=\bar{y}$, and the two triangles are on the same same side of
$[x^{\prime},y^{\prime}]=[\bar{x},\bar{y}]$, as illustrated in Figure 1. Since
the legs $[x^{\prime},z^{\prime}]$ and $[\bar{x},\bar{z}]$ are also of the
same length, a simple geometric argument in the Poincaré disk shows that

(4) $d(x^{\prime},[y^{\prime},z^{\prime}])\leqslant
d(\bar{x},[\bar{y},\bar{z}]).$

The combination of (3) and (4) completes the proof. ∎

We are now ready to prove Theorem 5.

###### Proof of the Blocked View Theorem 5.

Remember that we are trying to show that, for
$r_{0}=\frac{1}{k}\log(\sqrt{2}+1)$, the blocked view set

$C_{p}(x,r)=\big{\\{}q\in M;[p,q]\cap B(x,r)\neq\emptyset\big{\\}}$

contains, for the tangent vector $v_{p}$ of the geodesic $[p,x]$ at $x$, the
half-space

$H(x,v_{p})=\big{\\{}q\in M;~{}\langle v_{p},v_{q}\rangle\leqslant 0\text{ for
the tangent vector }v_{q}\text{ of }[q,x]\text{ at }x\big{\\}}.$

With this goal in mind, consider a point $q\in H(x,v_{p})$. Since $p$ is in
the complement of the half-space $H(x,v_{p})$, there exists a point $z$ in the
intersection of the geodesic $[p,q]$ and of the boundary $\partial
H(x,v_{p})$. By construction, the triangle $xpz$ has a right angle at the
vertex $x$.

The combination of Lemmas 6 and 7 then shows that $x$ is at distance at most
$r_{0}$ from the geodesic $[p,z]$, and therefore from the geodesic $[p,q]$. As
a consequence, the view from $p$ to $q$ is blocked by the ball $B(x,r_{0})$,
and $q$ belongs to the blocked view set $C_{p}(x,r)$.

This concludes the proof of the Blocked View Theorem 5. ∎

##  4\. The fair cut of a pie

This section is now devoted to an apparently unrelated problem. The connection
with the congestion problem will be explained in §5.

The issue is a fair-division scheme for a pie. Suppose that Alice and Bob want
to split a cake, and that each of them wants to optimize the size of their
share. Alice decides a point through which the knife should cut, and Bob
decides in which direction to apply the cut. Alice knows that, wherever she
picks a point, Bob will choose the cut through this point that will maximize
his share, and consequently minimize Alice’s share. So Alice’s goal is to find
a point where any cut will guarantee her an optimum share of the cake. We call
such a point a “fair-cut center”.

In our case, the cake is replaced by a convex Riemannian manifold $M$ of
negative curvature, and the knife cut at the point $x\in M$ occurs along a
geodesic hyperplane $\partial H(x,v)$.

###  4.1. Definitions and the Fair-Cut Theorem

Let $M$ be a compact convex Riemannian manifold. For a point $x\in M$ and a
unit vector $v\in T_{x}^{1}M$, the half-space

$H(x,v)=\big{\\{}q\in M;\langle v_{q},v\rangle\leqslant 0\text{ for the
tangent vector }v_{q}\text{ of }[q,x]\text{ at }x\big{\\}}$

is bounded by the _geodesic hyperplane_

$\partial H(x,v)=\big{\\{}q\in M;\langle v_{q},v\rangle=0\text{ for the
tangent vector }v_{q}\text{ of }[q,x]\text{ at }x\big{\\}}$

######  Definition 8 (A fair cut of the pie).

Let $M$ be a compact, convex $m$-dimensional Riemannian manifold with non-
positive sectional curvature. The _fair-cut index_ of $M$ is the number

(5) $\Phi(M)=\max_{x\in M}{\min_{v\in
T_{x}^{1}M}{\frac{\operatorname{vol}{H(x,v)}}{\operatorname{vol}{M}}}}.$

In other words, if we consider the function $f_{x}\colon
T_{x}^{1}M\longrightarrow[0,1]$ defined by

$f_{x}(v)=\frac{\operatorname{vol}{H(x,v)}}{\operatorname{vol}{M}},$

which measures the percentage of the pie corresponding to $H(x,v)$, and the
function $\varphi_{M}\colon M\longrightarrow[0,1]$ defined as the minimum

$\varphi_{M}(x)=\min_{v\in T_{x}^{1}M}{f_{x}(v)},$

then the fair cut index is

(6) $\Phi(M)=\max_{x\in M}\varphi_{M}(x)=\max_{x\in M}{\min_{v\in
T_{x}^{1}M}{f_{x}(v)}}=\max_{x\in M}\min_{v\in
T_{x}^{1}M}\frac{\operatorname{vol}{H(x,v)}}{\operatorname{vol}M}.$

We will obtain the following estimate.

######  Theorem 9 (Fair-cut Theorem).

Let $M$ be a compact, convex $m$-dimensional Riemannian manifold with constant
non-positive sectional curvature.

Then,

$\frac{1}{m+1}\leqslant\Phi(M)\leqslant\frac{1}{2}.$

The upper bound is an immediate consequence of the observation that

$\operatorname{vol}{H(x,v)}+\operatorname{vol}{H(x,-v)}=\operatorname{vol}{M}.$

The lower bound $\frac{1}{m+1}$ will require more elaborate arguments,
described in the next sections.

Note that there exists manifolds $M$ for which the upper bound
$\Phi(M)=\frac{1}{2}$ is achieved. This will happen when $M$ is radially
symmetric about a point $x_{0}$, in the sense that for every $p\in M$ there is
a point $q\in M$ such that $x_{0}$ is the midpoint of the geodesic arc
$[p,q]$. Indeed, in this case,
$\operatorname{vol}{H(x_{0},v)}=\operatorname{vol}{H(x_{0},-v)}=\frac{1}{2}\operatorname{vol}{M}$
for every $v\in T^{1}_{x_{0}}M$.

We begin with a couple of lemmas, in the next two sections

###  4.2. Lipschitz continuity for the volume function

We will need an estimate on the local variation of the volume function
$\operatorname{vol}{H(\cdot,\cdot)}:T^{1}M\longrightarrow\mathbb{R}_{+}$.

######  Lemma 10 (Lipschitz bound for the volume function).

Let $M$ be a compact, convex $m$-dimensional Riemannian manifold with non-
positive sectional curvature bounded in an interval $[-k_{1}^{2},0]$ with
$k_{1}\geqslant 0$. Suppose that $t\mapsto(x(t),v(t))$ is a smooth curve in
the unit tangent bundle of $M$. Then

(7) $\Big{|}\frac{d}{dt}\operatorname{vol}{H(x(t),v(t))}\Big{|}\leqslant
C(k_{1},D)\Big{|}\frac{d}{dt}\big{(}x(t),v(t)\big{)}\Big{|}$

where $C(k_{1},D)$ is a constant depending only on the lower curvature bound
$-k_{1}^{2}$ and on an upper bound $D$ for the diameter of $M$.

###### Proof.

The proof uses the property that

$\frac{d}{dt}\operatorname{vol}{H\big{(}x(t),v(t)\big{)}}=\int_{\partial
H(x(t),v(t))}\langle N(y(t)),J(y(t))\rangle~{}d\mu(t),$

where $d\mu(t)$ is the volume form on the hyperplane, $y(t)$ is any point on
the hyperplane, $N(y(t))$ is the normal vector of $\partial H(x(t),v(t))$ at
$y(t)$, and $J(y(t))=\frac{d}{dt}y(t)$. A proof can for instance be found in
[8, Eqn. (7.2)].

Also, standard comparison arguments with Jacobi fields gives

$\big{|}\langle
N(y(t)),J(y(t))\rangle\big{|}\leqslant\big{|}J(y(t))\big{|}\leqslant\big{|}\cosh_{k_{1}}(D)+\sinh_{k_{1}}(D)\big{|},$

where the functions $\cosh_{k_{1}}$ and $\sinh_{k_{1}}$ are defined as

$\displaystyle\cosh_{k_{1}}(x)$ $\displaystyle=\cosh(k_{1}x)$
$\displaystyle\sinh_{k_{1}}(x)$ $\displaystyle=\frac{1}{k_{1}}\sinh(k_{1}x).$

Finally, the volume $\operatorname{vol}{\partial H(x(t),v(t))}$ is bounded by
a universal constant times $\sinh_{k_{1}}(D)^{n-1}$. The required property
then follows from these estimates. ∎

In particular, the function $\varphi_{M}$ is continuous. By compactness of the
unit tangent bundle $T^{1}M$, it attains its maximum at a point $x_{0}\in M$
such that

$\displaystyle\varphi_{M}(x_{0})$ $\displaystyle=\Phi(M)=\max_{x\in
M}{\varphi_{M}(x)}$ $\displaystyle=\max_{x\in M}\min_{v\in
T_{x_{0}}^{1}M}{f_{x_{0}}(v)}=\max_{x\in M}\min_{v\in
T_{x_{0}}^{1}M}{\frac{\operatorname{vol}{H(x_{0},v)}}{\operatorname{vol}{M}}}.$

######  Definition 11.

Let $M$ be a compact, convex $m$-dimensional Riemannian manifold with non-
positive sectional curvature. A point $x_{0}\in M$ such that
$\varphi_{M}(x_{0})=\Phi(M)$ is a _fair-cut center_ for $M$.

###  4.3. Moving half-spaces to their interiors

######  Lemma 12.

Let $M$ be an $m$-dimensional Riemannian manifold of negative sectional
curvature, then the sum of the angles of a geodesic triangle in $M$ is less
than $\pi$.

###### Proof.

This is an easy application of comparison theorems; see for instance [2, Prop
II.1.7]. ∎

The next lemma requires the curvature of our manifold $M$ to be constant.

######  Lemma 13.

In an $m$-dimensional Riemannian manifold $M$ of constant negative sectional
curvature, let $H(x_{0},v_{0})\subset M$ be the half-space defined by a point
$x_{0}\in M$ and a unit vector $v_{0}\in T_{x_{0}}^{1}M$. For any $x$ in the
interior of the half-space $H(x_{0},v_{0})$, there exists a vector $v\in
T_{x}^{1}M$ such that $H(x,v)$ is contained in the interior of
$H(x_{0},v_{0})$. In particular,
$\operatorname{vol}H(x,v)<\operatorname{vol}H(x_{0},v_{0})$.

Similarly, if $x$ is in $M\setminus H(x_{0},v_{0})$, there exists $v\in
T_{x}^{1}M$ such that the interior of $H(x,v)$ contains $H(x_{0},v_{0})$, and
$\operatorname{vol}H(x,v)>\operatorname{vol}H(x_{0},v_{0})$.

###### Proof.

Let $z$ be a point in the boundary $\partial H(x_{0},v_{0})$ that is closest
to $x$, and let $w\in T_{z}^{1}M$ be the vector tangent to the geodesic
$[z,x]$ at $z$. Because the curvature is constant, $H(z,w)=H(x_{0},v_{0})$. If
$v\in T_{x}^{1}M$ is tangent to $[z,x]$ at $x$, we conclude that $H(x,v)$ is
contained in the interior of $H(z,w)=H(x_{0},v_{0})$. (Otherwise, one would
see a triangle with two right angles, which is excluded by the negative
curvature.)

The second part of the statement is proved in a similar way. ∎

######  Remark 14.

This is the only point where we need the curvature of $M$ to be constant. It
is quite likely that a similar statement can be proved under a weaker
hypothesis, for instance the classical curvature pinching property that the
sectional curvature is in an interval $[-4a^{2},-a^{2}]$ with $a>0$.

###  4.4. Minimizing directions at a fair-cut center

We now focus on a fair-cut center $x_{0}$ for the manifold $M$.

######  Proposition 15.

Suppose that $M$ is a compact convex manifold with constant negative
curvature, and let $x_{0}\in M$ be a fair-cut center. Let

$\displaystyle V_{x_{0}}$ $\displaystyle=\big{\\{}v\in
T_{x_{0}}^{1}M;f_{x_{0}}(v)=\varphi_{M}(x_{0})=\Phi(M)\\}$
$\displaystyle=\big{\\{}v\in
T_{x_{0}}^{1}M;\operatorname{vol}{H(x_{0},v)}=\Phi(M)\operatorname{vol}(M)\\}$

be the set of minimizing directions at $x_{0}$. Then

$M=\bigcup_{v\in V_{x_{0}}}H(x_{0},v).$

###### Proof.

Suppose, in search of a contradiction, that the half-spaces $H(x_{0},v)$ with
$v\in V_{x_{0}}$ do not cover all of $M$. We will then show that $x_{0}$ is
not a local maximum of the function $\varphi_{M}$, contradicting its
definition.

If there exists a point $p\in M$ that is not in the union of the $H(x_{0},v)$
with $v\in V_{x_{0}}$, the tangent of the geodesic arc $[x_{0},p]$ at $x_{0}$
provides a unit tangent vector $u_{0}\in T_{x_{0}}^{1}M$ such that $\langle
u_{0},v\rangle<0$ for every $v\in V_{x_{0}}$.

In particular, the set $\\{v\in T_{x_{0}}^{1}M;\langle u_{0},v\rangle<0\\}$ is
an open neighborhood of the minimizing set $V_{x_{0}}=\\{v\in
T_{x_{0}}^{1}M;\operatorname{vol}{H(x_{0},v)}=\Phi(M)\operatorname{vol}(M)\\}$.
By compactness of $V_{x_{0}}$, there consequently exists an $\alpha_{0}>0$
such that

$\\{v\in
T_{x_{0}}^{1}M;\operatorname{vol}{H(x_{0},v)}<\Phi(M)\operatorname{vol}(M)+\alpha_{0}\\}\subset\\{v\in
T_{x_{0}}^{1}M;\langle u_{0},v\rangle<0\\}$

In other words, for every $v_{0}\in T_{x_{0}}^{1}M$, either

(8)
$\operatorname{vol}{H(x_{0},v_{0})}\geqslant\Phi(M)\operatorname{vol}M+\alpha_{0}$

or

(9) $\langle u_{0},v_{0}\rangle<0.$

Let $g\colon(-\varepsilon,\varepsilon)\to M$ be a small geodesic arc with
$g(0)=x_{0}$ and $g^{\prime}(0)=u_{0}$. For $t>0$, set $x_{t}=g(t)$.

By definition of the function $\varphi_{M}(x)=\inf_{v\in
T_{x}^{1}M}(\operatorname{vol}H(x,v))/(\operatorname{vol}M)$ and since $x_{0}$
realizes the maximum of this function, there exists $v_{t}\in T_{x_{t}}^{1}M$
such that

$\operatorname{vol}H(x_{t},v_{t})=\varphi_{M}(x_{t})\operatorname{vol}M\leqslant\varphi_{M}(x_{0})\operatorname{vol}M=\Phi(M)\operatorname{vol}M.$

Let $v_{0}\in T_{x_{0}}^{1}M$ be obtained by parallel translating $v_{t}$
along the geodesic $g$.

The Lipschitz continuity property of Lemma 10 shows that, provided we chose
$x_{t}$ sufficiently close to $x_{0}$ (depending only on the constant
$\alpha_{0}>0$ arising in (8) ), we have that

$\displaystyle\operatorname{vol}H(x_{0},v_{0})$
$\displaystyle\leqslant\operatorname{vol}H(x_{t},v_{t})+{\textstyle\frac{1}{2}}\alpha_{0}$
$\displaystyle\leqslant\Phi(M)\operatorname{vol}M+{\textstyle\frac{1}{2}}\alpha_{0}$

by choice of $v_{t}$. As a consequence, (8) cannot hold.

Therefore, $v_{0}$ satisfies (9). Since $v_{t}$ is obtained by parallel
translating $v_{0}$ along the geodesic $g$, $\langle
v_{t},g^{\prime}(t)\rangle=\langle v_{0},u_{0}\rangle<0$. Lemma 13 then
provides another vector $w_{0}\in T_{x_{0}}^{1}M$ such that

$\operatorname{vol}H(x_{0},w_{0})<\operatorname{vol}H(x_{t},v_{t})\leqslant\varphi_{M}(x_{0})\operatorname{vol}M.$

However, the existence of $w_{0}$ would contradict the fact that
$\varphi_{M}(x_{0})$ is defined as the infimum of
$\operatorname{vol}H(x_{0},v)/\operatorname{vol}M$ over all $v\in
T_{x_{0}}^{1}M$.

This final contradiction concludes the proof of Proposition 15. ∎

We now improve Proposition 15, by bounding the number of half-spaces
$H(x_{0},v)$, with $v\in V_{x_{0}}$, needed to cover the manifold $M$.

This is based on the following elementary observation.

######  Lemma 16.

In a compact convex manifold $M$ with nonpositive curvature, let $V$ be a
subset of the unit tangent space $T_{x_{0}}^{1}M$. The following properties
are equivalent:

  1. (1)

$M$ is the union of the half-spaces $H(x_{0},v)$ as $v$ ranges over all
vectors of $V$;

  2. (2)

for every $w\in T_{x_{0}}^{1}M$, there exists $v\in V$ with $\langle
v,w\rangle\geqslant 0$;

  3. (3)

in the vector space $T_{x}M$, the point $0$ is in the convex hull
$\mathrm{Conv}(V)$ of $V$.

###### Proof.

The equivalence of (1) and (2) is easily seen by considering, for every $x\in
M$, the tangent vector $w$ of the geodesic $[x_{0},x]$ at $x_{0}$.

The equivalence of (2) and (3) is an elementary property of convex sets in
$\mathbb{R}^{m}$. ∎

######  Proposition 17.

Let $M$ be a compact convex manifold with constant negative curvature, and let
$x_{0}\in M$ be its fair-cut center. Then, there exists $n$ vectors $v_{1}$,
$v_{2}$, …, $v_{n}\in V_{x_{0}}$ in the mininimizing set $V_{x_{0}}\subset
T_{x_{0}}^{1}M$, with $n\leqslant\dim M+1$, such that

$M=\bigcup_{i=1}^{n}H(x_{0},v_{i}).$

###### Proof.

By Proposition 15,

$M=\bigcup_{v\in V_{x_{0}}}H(x_{0},v).$

Lemma 16 then shows that $0$ is in the convex hull of $V_{x_{0}}$. By
Caratheodory’s theorem [3], there exists a subset
$\\{v_{1},v_{2},\dots,v_{n}\\}\subset V_{x_{0}}$ of cardinal $n\leqslant\dim
M+1$ whose convex hull also contains $0$. Another application of Lemma 16 then
shows that $M$ is the union of the $H(x_{0},v_{i})$ with $i=1$, $2$, …, $n$. ∎

###  4.5. Proof of the Fair-Cut Theorem

We are now ready to prove the Fair-Cut Theorem 9. We already observed that
$\Phi(M)\leqslant\frac{1}{2}$, so we just need to restrict attention to the
lower bound. .

By definition of the fair-cut center $x_{0}\in M$ and of the minimizing set
$V_{x_{0}}\subset T_{x_{0}}^{1}M$,

$\frac{\operatorname{vol}{H(x_{0},v)}}{\operatorname{vol}{M}}=\varphi_{M}(x_{0})=\Phi(M).$

for every $v\in V_{x_{0}}$.

Proposition 17 then shows that there exists
$\\{v_{1},v_{2},\dots,v_{n}\\}\subset V_{x_{0}}$ with $n\leqslant m+1$ such
that

$M=\bigcup_{i=1}^{n}H(x_{0},v_{i}).$

As a consequence,

$\operatorname{vol}{M}\leqslant\sum_{i=1}^{n}\operatorname{vol}{H(x_{0},v_{i})}=n\Phi(M)\operatorname{vol}{M}\leqslant(m+1)\Phi(M)\operatorname{vol}{M}.$

This proves that $\Phi(M)\geqslant\frac{1}{m+1}$. ∎

######  Remark 18.

The only place where we used the condition that the sectional curvature is
constant was in the proof of Lemma 13. It seems quite likely that Proposition
17 and Theorem 9 hold without this hypothesis.

##  5\. Proof of the Main Theorem

We now combine the Blocked View Theorem 5 and the Fair-Cut Theorem 9 to
provide an estimate on the percentage density of geodesic traffic.

######  Theorem 19.

Let $M$ be an $m$-dimensional compact convex Riemannian manifold of constant
negative sectional curvature $-k^{2}$, with $k>0$. Then, there exists a
universal radius $r_{0}=\frac{1}{k}\log(\sqrt{2}+1)$ and a point $x_{0}\in M$
such that at least $\frac{1}{m+1}$ of all the geodesics of the manifold pass
through the ball $B(x_{0},r_{0})$.

###### Proof.

Let $x_{0}$ be the fair-cut center of $M$ provided by the Fair-Cut Theorem 9,
and let $r_{0}=\frac{1}{k}\log(\sqrt{2}+1)$ be the radius of the Blocked View
Theorem 5. As in Section 2.2, let

$C(x_{0},r_{0})=\\{(p,q)\in M\times M;[p,q]\cap
B(x_{0},r_{0})\neq\emptyset\\}$

be the set of geodesics $[p,q]$ of $M$ passing through the ball
$B(x_{0},r_{0})$, and for $p\in M$ let

$C_{p}(x_{0},r_{0})=\\{q\in M;[p,q]\cap B(x_{0},r_{0})\neq\emptyset\\}$

be the set of points whose view from $p$ is obstructed by $B(x_{0},r_{0})$.

We saw in Equation 2 that

$\operatorname{vol}{C(x_{0},r_{0})}=\int_{p\in
M}\operatorname{vol}{C_{p}(x_{0},r_{0})}~{}d\mu(p).$

where $d\mu$ is the volume form of $M$.

For a given $p\in M$, the Blocked View Theorem 5 asserts that
$C_{p}(x_{0},r_{0})$ contains a half-space $H(x_{0},v_{p})$, so that

$\operatorname{vol}{C_{p}(x_{0},r_{0})}\geqslant\operatorname{vol}H(x_{0},v_{p}).$

By definition of the fair-cut center $x_{0}\in M$ and by the Fair-Cut Theorem
9,

$\operatorname{vol}H(x_{0},v_{p})\geqslant\varphi_{M}(x_{0})\operatorname{vol}M\geqslant\Phi(M)\operatorname{vol}M\geqslant\frac{1}{m+1}\operatorname{vol}M.$

Combining these inequalities then gives

$\operatorname{vol}{C(x_{0},r_{0})}=\int_{p\in
M}\operatorname{vol}{C_{p}(x_{0},r_{0})}~{}d\mu(p)\geqslant\frac{1}{m+1}(\operatorname{vol}M)^{2}.$

As a consequence, at least $\frac{1}{m+1}$ of all the geodesics of the
manifold pass through the ball $B(x_{0},r_{0})$. ∎

######  Definition 20.

The ball $B(x_{0},r_{0})$ is the _congestion core_ of $M$.

Note that the size of this congestion core is uniquely determined by the
curvature, the dimension of the manifold provides an estimate of the density
of the congestion, while the global geometry of the manifold contributes to
the location of the core.

##  6\. Additional comments

We conclude with a few observations and conjectures.

###  6.1. The set of fair-cut centers

######  Proposition 21.

In a compact convex manifold of constant nonpositive curvature, the set of
fair-cut centers is convex.

###### Proof.

Let $x_{1}$ and $x_{2}$ be two fair-cut centers for $M$. We want to show that
every point $x$ in the geodesic arc $[x_{1},x_{2}]$ is also a fair-cut center.

By Proposition 15, $x_{2}$ belongs to some minimizing half-space $H(x_{1},v)$,
namely a half-space such that

$\frac{\operatorname{vol}H(x_{1},v)}{\operatorname{vol}M}=\varphi(x_{1})=\Phi(M).$

We claim that, for any such minimizing half-space $H(x_{1},v)$ containing
$x_{2}$, the point $x_{2}$ is necessarily on the boundary $\partial
H(x_{1},v)$. Indeed, if $x_{2}$ was not in $H(x_{1},v)$, let $p$ be the point
of $\partial H(x_{1},v)$ that is closest to $x_{2}$ and let $w\in
T_{x_{2}}^{1}M$ be the unit tangent vector to the geodesic arc $[x_{2},p]$.
Because the curvature is constant, the half-space $H(x_{2},-w)$ is strictly
contained in $H(x_{1},v)$. In particular,
$\operatorname{vol}H(x_{2},-w)<\operatorname{vol}H(x_{1},v)$, this would imply
that

$\varphi(x_{2})<\varphi(x_{1})=\Phi(M)=\varphi(x_{2}),$

a contradiction.

Let $x\in[x_{1},x_{2}]$ be different from $x_{1}$ and $x_{2}$, and let
$H(x,v)$ be a minimizing hyperplane for $x$. The same argument as before shows
that $x_{2}$ cannot be contained in the interior of $H(x,v)$, as this would
again provide the contradiction

$\varphi(x_{2})<\varphi(x)\leqslant\Phi(M)=\varphi(x_{2}).$

Therefore, $x_{2}$ is in the boundary of $H(x,v)$ and, since the curvature is
constant, $H(x,v)=H(x_{2},v_{2})$ for some $v_{2}\in T_{x_{2}}^{1}M$. Then,

$\varphi(x)=\frac{\operatorname{vol}H(x,v)}{\operatorname{vol}M}=\frac{\operatorname{vol}H(x_{2},v_{2})}{\operatorname{vol}M}\geqslant\varphi(x_{2})=\Phi(M),$

from which we conclude that $x$ is also a maximum of the function $\varphi$,
namely is also a fair-cut center. ∎

In fact, we conjecture the much stronger result that the fair-cut center is
unique.

###  6.2. Heuristics about the fair-cut index $\Phi(M)$

Our lower bound $\frac{1}{m+1}$ for the fair-cut index $\Phi(M)$ seems far
from being sharp. A heuristic argument suggests a lower bound that is
independent of the dimension, which would also improve our congestion
estimates. We briefly discuss this argument.

In a given dimension $m$, we can try to find a manifold $M$ that approximates
the infimum of $\Phi(M)$ over all $m$–dimensional convex manifolds of negative
curvature. Because $\Phi(M)$ is invariant under rescaling of the metric by a
positive scalar, it makes sense to assume that such an approximatively
minimizing manifold exists in curvature 0. Then, by trial and error based on
the Marching Hyperplanes method of the next section, it seems that the infimum
in this curvature 0 case is realized by a simplex $\Delta_{n}$ in Euclidean
space $\mathbb{R}^{m}$. Since any two simplices in $\mathbb{R}^{m}$ are
equivalent under an affine isomorphism, they have the same fair-cut index
$\Phi(\Delta_{n})$.

The set of fair-cut centers is invariant under all the symmetries of the
simplex, and is convex by Proposition 21. It follows that the barycenter
$x_{0}$ of $\Delta_{n}$ is necessarily a fair-cut center.

######  Conjecture 22.

Let $\Delta_{n}$ be a simplex in the Euclidean space $\mathbb{R}^{m}$, with
nonempty interior. Then

$\Phi(\Delta_{n})=\left(\frac{m}{m+1}\right)^{m}.$

This is equivalent to the statement that, for the barycenter $x_{0}$ of
$\Delta_{n}$, the minimizing set $V_{x_{0}}\subset T_{x_{0}}^{1}\Delta_{n}$
consists of all unit vectors pointing towards the vertices of $\Delta_{n}$.

Note that $\left(\frac{m}{m+1}\right)^{m}$ is a decreasing function of $m$,
and converges to $\mathrm{e}$ as $m$ tends to $\infty$. All these
considerations lead us to the following conjecture.

######  Conjecture 23.

The fair-cut index $\Phi(M)$ of any compact convex manifold $M$ with non-
positive sectional curvature satisfies the sharp inequality

$\Phi(M)\geqslant\frac{1}{\mathrm{e}}.$

###  6.3. A method to estimate the fair-cut centers

The existence of fair-cut centers was abstractly established by minimizing the
function $\varphi(x)$. In practice, it may be useful to have a rough estimate
of the location of these fair-cut centers. For this, we can use the following
consequence of our Main Theorem 1.

######  Lemma 24.

If $\operatorname{vol}{H(x_{1},v_{1})}<\frac{1}{m+1}\operatorname{vol}{M}$ for
some $v_{1}\in T_{x_{1}}^{1}M$, then any fair-cut center $x_{0}$ is located
outside of the half-space $H(x_{1},v_{1})$.

###### Proof.

Suppose not, meaning that $x_{0}$ is located inside $H(x_{1},v_{1})$. Then,
let $x_{2}$ be the projection of $x_{0}$ to $\partial H(x_{1},v_{1})$, and let
the vectors $v_{2}\in T_{x_{2}}^{1}M$ and $v_{0}\in T_{x_{0}}^{1}M$ be tangent
to the geodesic arc $[x_{2},x_{1}]$. Then, $H(x_{0},v_{0})$ is contained in
$H(x_{2},v_{2})=H(x_{1},v_{1})$, and

$\varphi_{M}(x_{0})\leqslant\frac{\operatorname{vol}H(x_{0},v_{0})}{\operatorname{vol}M}\leqslant\frac{\operatorname{vol}H(x_{1},v_{1})}{\operatorname{vol}M}<\frac{1}{m+1}\leqslant\Phi(M),$

contradicting the fact that $\varphi_{M}(x_{0})=\Phi(M)$. ∎

Now let us provide a procedure which we call the _Marching Hyperplanes Method_
, in attempt to locate the whereabouts of the fair-cut center.

Figure 2. One marching hyperplane

Step 1: Start from a point $x_{1}$ on the boundary of $M$, pick a direction
$v_{x_{1}}$ that is perpendicular to $\partial M$ at $x_{1}$ and point inward,
then march forward inside $M$ along the geodesic $g_{1}$ starting from $x_{1}$
following $v_{x_{1}}$, until reached a point $x_{1,0}$ such that the half-
space $H(x_{1,0},-v_{x_{1,0}})$ has the volume of
$\frac{1}{m+1}\operatorname{vol}{M}$, where $v_{x_{1,0}}$ is the parallel
translation of $v_{x_{1}}$ along $g_{1}$. We mark $\partial H_{1}=\partial
H(x_{1,0},-v_{x_{1,0}})$, as shown in Figure 2.

Step 2 to m+1 and maybe more: Pick points $\\{x_{i}\\}$, $i=2,...,m+1$, and
maybe more, on $\partial M$, together with directions $v_{x_{i}}$ that is
perpendicular to $\partial M$ at $x_{i}$ and point inward, then repeat the
marching forward as Step 1, so we end up with lots of marked hyperplanes
$\\{\partial H_{i}\\}$, $i=2,...,m+1$, and maybe more.

Final Step: By Proposition 24, the fair-cut center $x_{0}$ is outside any
half-spaces that we have marched over, namely, it is located inside the entity
that is bounded by all the hyperplanes, as shown in Figure 3.

Although this method does not provide a precise location the fair-cut center,
for a small amount of steps, it does give us a very refined vicinity to locate
the fair-cut center. In practice, I will suggest using the lower bound in
Conjecture 23, i.e., $\frac{1}{e}$, instead of $\frac{1}{m+1}$, when the
dimension increases.

Figure 3. Many marching hyperplanes

## References

  * [1] Aaron B Adcock, Blair D Sullivan, and Michael W Mahoney.  Tree-like structure in large social and information networks.  In 2013 IEEE 13th International Conference on Data Mining, pages 1–10. IEEE, 2013.
  * [2] Martin R Bridson and André Haefliger.  Metric spaces of non-positive curvature, volume 319.  Springer Science & Business Media, 2013.
  * [3] Constantin Carathéodory.  Über den variabilitätsbereich der koeffizienten von potenzreihen, die gegebene werte nicht annehmen.  Mathematische Annalen, 64(1):95–115, 1907.
  * [4] Jeff Cheeger and David G Ebin.  Comparison theorems in Riemannian geometry, volume 365.  American Mathematical Soc., 2008.
  * [5] Wei Chen, Wenjie Fang, Guangda Hu, and Michael W Mahoney.  On the hyperbolicity of small-world and treelike random graphs.  Internet Mathematics, 9(4):434–491, 2013.
  * [6] Victor Chepoi, Feodor F Dragan, and Yann Vaxès.  Core congestion is inherent in hyperbolic networks.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2264–2279. SIAM, 2017.
  * [7] Fabien De Montgolfier, Mauricio Soto, and Laurent Viennot.  Treewidth and hyperbolicity of the internet.  In 2011 IEEE 10th International Symposium on Network Computing and Applications, pages 25–32. IEEE, 2011.
  * [8] Harley Flanders.  Differentiation under the integral sign.  The American Mathematical Monthly, 80(6):615–627, 1973.
  * [9] Edmond Jonckheere, Poonsuk Lohsoonthorn, and Francis Bonahon.  Scaled Gromov hyperbolic graphs.  Journal of Graph Theory, 57(2):157–180, 2008.
  * [10] Edmond Jonckheere, Mingji Lou, Francis Bonahon, and Yuliy Baryshnikov.  Euclidean versus hyperbolic congestion in idealized versus experimental networks.  Internet Mathematics, 7(1):1–27, 2011.
  * [11] W Sean Kennedy, Onuttom Narayan, and Iraj Saniee.  On the hyperbolicity of large-scale networks.  arXiv preprint arXiv:1307.0031, 2013.
  * [12] Poonsuk Lohsoonthorn.  Hyperbolic geometry of networks.  2003\.  PhD thesis, University of Southern California.
  * [13] Onuttom Narayan and Iraj Saniee.  Large-scale curvature of networks.  Physical Review E, 84(6):066108, 2011.
  * [14] Yuval Shavitt and Tomer Tankel.  Hyperbolic embedding of internet graph for distance estimation and overlay construction.  IEEE/ACM Transactions on Networking, 16(1):25–36, 2008.