Hyperbolicity of a graph
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.
An improvement over the naive algorithm has been proposed in [CCL12], and is implemented in the current module. Like the naive algorithm, it has complexity \(O(n^4)\) but behaves much better in practice. It uses the following fact :
Assume that \(S_1 = dist(a, b) + dist(c, d)\) is the largest 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, we ensure that \(S_1\) is larger than \(S_2\) and \(S_3\) using an ordering of the pairs by decreasing lengths. Furthermore, we use the best value \(h\) found so far to cut exploration.
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.
TODO:
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. |
AUTHORS:
Return an elimination ordering of simplicial vertices.
An elimination ordering of simplicial vertices is an elimination ordering of the vertices of the graphs such that the induced subgraph of their neighbors is a clique. More precisely, as long as the graph has a vertex u such that the induced subgraph of its neighbors is a clique, we remove u from the graph, add it to the elimination ordering (list of vertices), and repeat. This method is inspired from the decomposition of a graph by clique-separators.
INPUTS:
OUTPUT:
TESTS:
Giving anything else than a Graph:
sage: from sage.graphs.hyperbolicity import elimination_ordering_of_simplicial_vertices
sage: elimination_ordering_of_simplicial_vertices([])
Traceback (most recent call last):
...
ValueError: The input parameter must be a Graph.
Giving two small bounds on degree:
sage: from sage.graphs.hyperbolicity import elimination_ordering_of_simplicial_vertices
sage: elimination_ordering_of_simplicial_vertices(Graph(), max_degree=0)
Traceback (most recent call last):
...
ValueError: The parameter max_degree must be > 0.
Giving a graph built from a bipartite graph plus an edge:
sage: G = graphs.CompleteBipartiteGraph(2,10)
sage: G.add_edge(0,1)
sage: from sage.graphs.hyperbolicity import elimination_ordering_of_simplicial_vertices
sage: elimination_ordering_of_simplicial_vertices(G)
[2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 11]
sage: elimination_ordering_of_simplicial_vertices(G,max_degree=1)
[]
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 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)\).
- '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+' is an additive constant approximation algorithm. It proceeds by first removing the simplicial vertices and then applying the 'cuts' algorithm on the remaining graph, as documented in [CCL12]. By default, the additive constant of the approximation is one. This value can be increased by setting the additive_gap to the desired value, provide additive_gap \geq 1. In some cases, the returned result is proven optimal. However, this algorithm cannot be used to compute an approximation with multiplicative factor, and so the approximation_factor parameter is just ignored here.
- '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' or 'cuts+'. The parameter must be \geq 1 when used with '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:
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='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='cuts+')
(1, [(0, 0), (0, 9), (1, 0), (1, 9)], 2)
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')
... d2,_,_ = hyperbolicity(G,algorithm='cuts')
... d3,_,_ = hyperbolicity(G,algorithm='cuts+')
... l3,_,u3 = hyperbolicity(G,approximation_factor=2)
... if d1!=d2 or d1<d3 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.
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:
OUTPUT:
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.