Hyperbolicity

Definition :

The hyperbolicity \(\delta\) of a graph \(G\) has been defined by Gromov [Gromov87] as follows (we give here the so-called 4-points condition):

Let \(a, b, c, d\) be vertices of the graph, let \(S_1\), \(S_2\) and \(S_3\) be defined by

\[\begin{split}S_1 = dist(a, b) + dist(b, c)\\ S_2 = dist(a, c) + dist(b, d)\\ S_3 = dist(a, d) + dist(b, c)\\\end{split}\]

and let \(M_1\) and \(M_2\) be the two largest values among \(S_1\), \(S_2\), and \(S_3\). We define \(hyp(a, b, c, d) = M_1 - M_2\), and the hyperbolicity \(\delta(G)\) of the graph is the maximum of \(hyp\) over all possible 4-tuples \((a, b, c, d)\) divided by 2. That is, the graph is said \(\delta\)-hyperbolic when

\[\delta(G) = \frac{1}{2}\max_{a,b,c,d\in V(G)}hyp(a, b, c, d)\]

(note that \(hyp(a, b, c, d)=0\) whenever two elements among \(a,b,c,d\) are equal)

Some known results :

  • Trees and cliques are \(0\)-hyperbolic
  • \(n\times n\) grids are \(n-1\)-hyperbolic
  • Cycles are approximately \(n/4\)-hyperbolic
  • Chordal graphs are \(\leq 1\)-hyperbolic

Besides, the hyperbolicity of a graph is the maximum over all its biconnected components.

Algorithms and complexity :

The time complexity of the naive implementation (i.e. testing all 4-tuples) is \(O( n^4 )\), and an algorithm with time complexity \(O(n^{3.69})\) has been proposed in [FIV12]. This remains very long for large-scale graphs, and much harder to implement.

Several improvements over the naive algorithm have been proposed and are implemented in the current module.

  • It is shown in [Soto11] that \(hyp(a, b, c, d)\) is upper bounded by the smallest distance between the vertices in \(\{a,b,c,d\}\) multiplied by 2.

    \[hyp(a, b, c, d) \leq \min_{u,v\in\{a,b,c,d\}}2dist(u,v)\]

    This result is used to reduce the number of tested 4-tuples in the naive implementation (called ‘basic+’).

  • Another upper bound on \(hyp(a, b, c, d)\) has been proved in [CCL12]. It is used to design an algorithm with worse case time complexity in \(O(n^4)\) but that behaves much better in practice.

    Assume that \(S_1 = dist(a, b) + dist(c, d)\) is the largest sum among \(S_1,S_2,S_3\). We have

    \[\begin{split}S_2 + S_3 =& dist(a, c) + dist(b, d) + dist(a, d) + dist(b, c)\\ =& [ dist(a, c) + dist(b, c) ] + [ dist(a, d) + dist(b, d)]\\ \geq &dist(a,b) + dist(a,b)\\ \geq &2dist(a,b)\\\end{split}\]

    Now, since \(S_1\) is the largest sum, we have

    \[\begin{split}hyp(a, b, c, d) =& S_1 - \max\{S_2, S_3\}\\ \leq& S_1 - \frac{S_2+ S_3}{2}\\ \leq& S_1 - dist(a, b)\\ =& dist(c, d)\\\end{split}\]

    We obtain similarly that \(hyp(a, b, c, d) \leq dist(a, b)\). Consequently, in the implementation of the ‘cuts’ algorithm, we ensure that \(S_1\) is larger than \(S_2\) and \(S_3\) using an ordering of the pairs by decreasing lengths. Then, we use the best value \(h\) found so far to stop exploration as soon as \(dist(a, b) \leq h\).

    The worst case time complexity of this algorithm is \(O(n^4)\), but it performs very well in practice since it cuts the search space. This algorithm can be turned into an approximation algorithm since at any step of its execution we maintain an upper and a lower bound. We can thus stop execution as soon as a multiplicative approximation factor or an additive one is proven.

  • The notion of ‘’far-apart pairs’’ has been introduced in [Soto11] to further reduce the number of 4-tuples to consider. We say that the pair \((a,b)\) is far-apart if for every \(w\) in \(V\setminus\{a,b\}\) we have

    \[\begin{split}dist(w,a)+dist(a,b) > dist(w,b) \text{ and }dist(w,b)+dist(a,b) > dist(w,a)\end{split}\]

    Determining the set of far-apart pairs can be done in time \(O(nm)\) using BFS. Now, it is proved in [Soto11] that there exists two far-apart pairs \((a,b)\) and \((c,d)\) satisfying \(\delta(G) = hyp(a, b, c, d)/2\). For instance, the \(n\times m\)-grid has only two far-apart pairs, and so computing its hyperbolicity is immediate once the far-apart pairs are found. The ‘cuts+’ algorithm improves the ‘cuts’ algorithm since it uses far-apart pairs.

TODO:

  • Add exact methods for the hyperbolicity of chordal graphs
  • Add method for partitioning the graph with clique separators

This module contains the following functions

At Python level :

hyperbolicity() Return the hyperbolicity of the graph or an approximation of this value.
hyperbolicity_distribution() Return the hyperbolicity distribution of the graph or a sampling of it.

REFERENCES:

[CCL12]N. Cohen, D. Coudert, and A. Lancin. Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs. Research Report RR-8074, Sep. 2012. [http://hal.inria.fr/hal-00735481].
[FIV12]H. Fournier, A. Ismail, and A. Vigneron. Computing the Gromov hyperbolicity of a discrete metric space. ArXiv, Tech. Rep. arXiv:1210.3323, Oct. 2012. [http://arxiv.org/abs/1210.3323].
[Gromov87](1, 2, 3) M. Gromov. Hyperbolic groups. Essays in Group Theory, 8:75–263, 1987.
[Soto11](1, 2, 3, 4, 5) M. A. Soto Gomez. 2011. Quelques proprietes topologiques des graphes et applications a internet et aux reseaux. Ph.D. Dissertation. Univ. Paris Diderot (Paris 7).

AUTHORS:

  • David Coudert (2012): initial version, exact and approximate algorithm, distribution, sampling
  • David Coudert (2014): improved exact algorithm using far-apart pairs

Methods

sage.graphs.hyperbolicity.hyperbolicity(G, algorithm='cuts', approximation_factor=None, additive_gap=None, verbose=False)

Return the hyperbolicity of the graph or an approximation of this value.

The hyperbolicity of a graph has been defined by Gromov [Gromov87] as follows: Let \(a, b, c, d\) be vertices of the graph, let \(S_1 = dist(a, b) + dist(b, c)\), \(S_2 = dist(a, c) + dist(b, d)\), and \(S_3 = dist(a, d) + dist(b, c)\), and let \(M_1\) and \(M_2\) be the two largest values among \(S_1\), \(S_2\), and \(S_3\). We have \(hyp(a, b, c, d) = |M_1 - M_2|\), and the hyperbolicity of the graph is the maximum over all possible 4-tuples \((a, b, c, d)\) divided by 2. The worst case time complexity is in \(O( n^4 )\).

See the documentation of sage.graphs.hyperbolicity for more information.

INPUT:

  • G – a connected Graph

  • algorithm – (default: 'cuts') specifies the algorithm to use among:

    • 'basic' is an exhaustive algorithm considering all possible 4-tuples and so have time complexity in \(O(n^4)\).
    • 'basic+' uses a cutting rule proposed in [Soto11] to significantly reduce the overall computation time of the 'basic' algorithm.
    • 'cuts' is an exact algorithm proposed in [CCL12]. It considers the 4-tuples in an ordering allowing to cut the search space as soon as a new lower bound is found (see the module’s documentation). This algorithm can be turned into a approximation algorithm.
    • 'cuts+' uses the notion of far-apart pairs as proposed in [Soto11] to significantly reduce the overall computation time of the 'cuts' algorithm.
    • 'dom' is an approximation with additive constant four. It computes the hyperbolicity of the vertices of a dominating set of the graph. This is sometimes slower than 'cuts' and sometimes faster. Try it to know if it is interesting for you. The additive_gap and approximation_factor parameters cannot be used in combination with this method and so are ignored.
  • approximation_factor – (default: None) When the approximation factor is set to some value (larger than 1.0), the function stop computations as soon as the ratio between the upper bound and the best found solution is less than the approximation factor. When the approximation factor is 1.0, the problem is solved optimaly. This parameter is used only when the chosen algorithm is 'cuts'.

  • additive_gap – (default: None) When sets to a positive number, the function stop computations as soon as the difference between the upper bound and the best found solution is less than additive gap. When the gap is 0.0, the problem is solved optimaly. This parameter is used only when the chosen algorithm is 'cuts'.

  • verbose – (default: False) is a boolean set to True to display some information during execution: new upper and lower bounds, etc.

OUTPUT:

This function returns the tuple ( delta, certificate, delta_UB ), where:

  • delta – the hyperbolicity of the graph (half-integer value).
  • certificate – is the list of the 4 vertices for which the maximum value has been computed, and so the hyperbolicity of the graph.
  • delta_UB – is an upper bound for delta. When delta == delta_UB, the returned solution is optimal. Otherwise, the approximation factor if delta_UB/delta.

EXAMPLES:

Hyperbolicity of a \(3\times 3\) grid:

sage: from sage.graphs.hyperbolicity import hyperbolicity
sage: G = graphs.GridGraph([3,3])
sage: hyperbolicity(G,algorithm='cuts')
(2, [(0, 0), (0, 2), (2, 0), (2, 2)], 2)
sage: hyperbolicity(G,algorithm='basic')
(2, [(0, 0), (0, 2), (2, 0), (2, 2)], 2)

Hyperbolicity of a PetersenGraph:

sage: from sage.graphs.hyperbolicity import hyperbolicity
sage: G = graphs.PetersenGraph()
sage: hyperbolicity(G,algorithm='cuts')
(1/2, [0, 1, 2, 3], 1/2)
sage: hyperbolicity(G,algorithm='cuts+')
(1/2, [0, 1, 2, 3], 1/2)
sage: hyperbolicity(G,algorithm='basic')
(1/2, [0, 1, 2, 3], 1/2)
sage: hyperbolicity(G,algorithm='basic+')
(1/2, [0, 1, 2, 3], 1/2)
sage: hyperbolicity(G,algorithm='dom')
(0, [0, 2, 8, 9], 1)

Asking for an approximation:

sage: from sage.graphs.hyperbolicity import hyperbolicity
sage: G = graphs.GridGraph([2,10])
sage: hyperbolicity(G,algorithm='cuts', approximation_factor=1.5)
(1, [(0, 0), (0, 9), (1, 0), (1, 9)], 3/2)
sage: hyperbolicity(G,algorithm='cuts', approximation_factor=4)
(1, [(0, 0), (0, 9), (1, 0), (1, 9)], 4)
sage: hyperbolicity(G,algorithm='cuts', additive_gap=2)
(1, [(0, 0), (0, 9), (1, 0), (1, 9)], 3)
sage: hyperbolicity(G,algorithm='dom')
(1, [(0, 1), (0, 9), (1, 0), (1, 8)], 5)

Comparison of results:

sage: from sage.graphs.hyperbolicity import hyperbolicity
sage: for i in xrange(10): # long time
...       G = graphs.RandomBarabasiAlbert(100,2)
...       d1,_,_ = hyperbolicity(G,algorithm='basic')
...       d4,_,_ = hyperbolicity(G,algorithm='basic+')
...       d2,_,_ = hyperbolicity(G,algorithm='cuts')
...       d3,_,_ = hyperbolicity(G,algorithm='cuts+')
...       l3,_,u3 = hyperbolicity(G,approximation_factor=2)
...       if (not d1==d2==d3==d4) or l3>d1 or u3<d1:
...          print "That's not good!"

TESTS:

Giving anything else than a Graph:

sage: from sage.graphs.hyperbolicity import hyperbolicity
sage: hyperbolicity([])
Traceback (most recent call last):
...
ValueError: The input parameter must be a Graph.

Giving a non connected graph:

sage: from sage.graphs.hyperbolicity import hyperbolicity
sage: G = Graph([(0,1),(2,3)])
sage: hyperbolicity(G)
Traceback (most recent call last):
...
ValueError: The input Graph must be connected.

Giving wrong approximation factor:

sage: from sage.graphs.hyperbolicity import hyperbolicity
sage: G = graphs.PetersenGraph()
sage: hyperbolicity(G,algorithm='cuts', approximation_factor=0.1)
Traceback (most recent call last):
...
ValueError: The approximation factor must be >= 1.0.

Giving negative additive gap:

sage: from sage.graphs.hyperbolicity import hyperbolicity
sage: G = Graph()
sage: hyperbolicity(G,algorithm='cuts', additive_gap=-1)
Traceback (most recent call last):
...
ValueError: The additive gap must be >= 0 when using the 'cuts' algorithm.

Asking for an unknown algorithm:

sage: from sage.graphs.hyperbolicity import hyperbolicity
sage: G = Graph()
sage: hyperbolicity(G,algorithm='tip top')
Traceback (most recent call last):
...
ValueError: Algorithm 'tip top' not yet implemented. Please contribute.
sage.graphs.hyperbolicity.hyperbolicity_distribution(G, algorithm='sampling', sampling_size=1000000)

Return the hyperbolicity distribution of the graph or a sampling of it.

The hyperbolicity of a graph has been defined by Gromov [Gromov87] as follows: Let \(a, b, c, d\) be vertices of the graph, let \(S_1 = dist(a, b) + dist(b, c)\), \(S_2 = dist(a, c) + dist(b, d)\), and \(S_3 = dist(a, d) + dist(b, c)\), and let \(M_1\) and \(M_2\) be the two largest values among \(S_1\), \(S_2\), and \(S_3\). We have \(hyp(a, b, c, d) = |M_1 - M_2|\), and the hyperbolicity of the graph is the maximum over all possible 4-tuples \((a, b, c, d)\) divided by 2.

The computation of the hyperbolicity of each 4-tuple, and so the hyperbolicity distribution, takes time in \(O( n^4 )\).

INPUT:

  • G – a Graph.
  • algorithm – (default: ‘sampling’) When algorithm is ‘sampling’, it returns the distribution of the hyperbolicity over a sample of sampling_size 4-tuples. When algorithm is ‘exact’, it computes the distribution of the hyperbolicity over all 4-tuples. Be aware that the computation time can be HUGE.
  • sampling_size – (default: \(10^6\)) number of 4-tuples considered in the sampling. Used only when algorithm == 'sampling'.

OUTPUT:

  • hdict – A dictionnary such that hdict[i] is the number of 4-tuples of hyperbolicity i.

EXAMPLES:

Exact hyperbolicity distribution of the Petersen Graph:

sage: from sage.graphs.hyperbolicity import hyperbolicity_distribution
sage: G = graphs.PetersenGraph()
sage: hyperbolicity_distribution(G,algorithm='exact')
{0: 3/7, 1/2: 4/7}

Exact hyperbolicity distribution of a \(3\times 3\) grid:

sage: from sage.graphs.hyperbolicity import hyperbolicity_distribution
sage: G = graphs.GridGraph([3,3])
sage: hyperbolicity_distribution(G,algorithm='exact')
{0: 11/18, 1: 8/21, 2: 1/126}

TESTS:

Giving anythin else than a Graph:

sage: from sage.graphs.hyperbolicity import hyperbolicity_distribution
sage: hyperbolicity_distribution([])
Traceback (most recent call last):
...
ValueError: The input parameter must be a Graph.

Giving a non connected graph:

sage: from sage.graphs.hyperbolicity import hyperbolicity_distribution
sage: G = Graph([(0,1),(2,3)])
sage: hyperbolicity_distribution(G)
Traceback (most recent call last):
...
ValueError: The input Graph must be connected.

Table Of Contents

Previous topic

Lists of graphs

Next topic

Tutte polynomial

This Page