Hyperbolicity¶
Definition :
The hyperbolicity \(\delta\) of a graph \(G\) has been defined by Gromov [Gro1987] 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(d, 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 [FIV2012]. 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.
Another upper bound on \(hyp(a, b, c, d)\) has been proved in [CCL2015]. 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 ‘CCL’ 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 [Sot2011] 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
\[dist(w,a)+dist(a,b) > dist(w,b) \text{ and }dist(w,b)+dist(a,b) > dist(w,a)\]Determining the set of far-apart pairs can be done in time \(O(nm)\) using BFS. Now, it is proved in [Sot2011] 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 ‘CCL+FA’ or ‘CCL+’ algorithm improves the ‘CCL’ algorithm since it uses far-apart pairs.
This algorithm was further improved in [BCCM2015]: instead of iterating twice over all pairs of vertices, in the “inner” loop, we cut several pairs by exploiting properties of the underlying graph.
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. |
AUTHORS:
- David Coudert (2012): initial version, exact and approximate algorithm, distribution, sampling
- David Coudert (2014): improved exact algorithm using far-apart pairs
- Michele Borassi (2015): cleaned the code and implemented the new algorithm
- Karan Desai (2016): fixed minor typo in documentation
Methods¶
-
sage.graphs.hyperbolicity.hyperbolicity(G, algorithm='BCCM', approximation_factor=None, additive_gap=None, verbose=False)¶ Returns the hyperbolicity of the graph or an approximation of this value.
The hyperbolicity of a graph has been defined by Gromov [Gro1987] 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.hyperbolicityfor more information.INPUT:
G– a connected Graphalgorithm– (default:'BCCM'); 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)\).'CCL'is an exact algorithm proposed in [CCL2015]. 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.'CCL+FA'or'CCL+'uses the notion of far-apart pairs as proposed in [Sot2011] to significantly reduce the overall computation time of the'CCL'algorithm.'BCCM'is an exact algorithm proposed in [BCCM2015]. It improves'CCL+FA'by cutting several 4-tuples (for more information, see the module’s documentation).'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'CCL'and sometimes faster. Try it to know if it is interesting for you. Theadditive_gapandapproximation_factorparameters 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 optimally. This parameter is used only when the chosen algorithm is'CCL','CCL+FA', or'BCCM'.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 optimally. This parameter is used only when the chosen algorithm is'CCL'or'CCL+FA', or'BCCM'.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 fordelta. Whendelta == delta_UB, the returned solution is optimal. Otherwise, the approximation factor ifdelta_UB/delta.
EXAMPLES:
Hyperbolicity of a \(3\times 3\) grid:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.Grid2dGraph(3, 3) sage: L,C,U = hyperbolicity(G, algorithm='BCCM'); L,sorted(C),U (2, [(0, 0), (0, 2), (2, 0), (2, 2)], 2) sage: L,C,U = hyperbolicity(G, algorithm='CCL'); L,sorted(C),U (2, [(0, 0), (0, 2), (2, 0), (2, 2)], 2) sage: L,C,U = hyperbolicity(G, algorithm='basic'); L,sorted(C),U (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: L,C,U = hyperbolicity(G, algorithm='BCCM'); L,sorted(C),U (1/2, [6, 7, 8, 9], 1/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL'); L,sorted(C),U (1/2, [0, 1, 2, 3], 1/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL+'); L,sorted(C),U (1/2, [0, 1, 2, 3], 1/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL+FA'); L,sorted(C),U (1/2, [0, 1, 2, 3], 1/2) sage: L,C,U = hyperbolicity(G, algorithm='basic'); L,sorted(C),U (1/2, [0, 1, 2, 3], 1/2) sage: L,C,U = hyperbolicity(G, algorithm='dom'); L,sorted(C),U (0, [0, 1, 2, 6], 1)
Asking for an approximation in a grid graph:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.Grid2dGraph(2, 10) sage: L,C,U = hyperbolicity(G, algorithm='CCL', approximation_factor=1.5); L,U (1, 3/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL+', approximation_factor=1.5); L,U (1, 1) sage: L,C,U = hyperbolicity(G, algorithm='CCL', approximation_factor=4); L,U (1, 4) sage: L,C,U = hyperbolicity(G, algorithm='CCL', additive_gap=2); L,U (1, 3) sage: L,C,U = hyperbolicity(G, algorithm='dom'); L,U (1, 5)
Asking for an approximation in a cycle graph:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.CycleGraph(10) sage: L,C,U = hyperbolicity(G, algorithm='CCL', approximation_factor=1.5); L,U (2, 5/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL+FA', approximation_factor=1.5); L,U (2, 5/2) sage: L,C,U = hyperbolicity(G, algorithm='CCL+FA', additive_gap=1); L,U (2, 5/2)
Comparison of results:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: for i in range(10): # long time ....: G = graphs.RandomBarabasiAlbert(100,2) ....: d1,_,_ = hyperbolicity(G, algorithm='basic') ....: d2,_,_ = hyperbolicity(G, algorithm='CCL') ....: d3,_,_ = hyperbolicity(G, algorithm='CCL+') ....: d4,_,_ = hyperbolicity(G, algorithm='CCL+FA') ....: d5,_,_ = hyperbolicity(G, algorithm='BCCM') ....: l3,_,u3 = hyperbolicity(G, approximation_factor=2) ....: if (not d1==d2==d3==d4==d5) or l3>d1 or u3<d1: ....: print("That's not good!") sage: from sage.graphs.hyperbolicity import hyperbolicity sage: import random sage: random.seed() sage: for i in range(10): # long time ....: n = random.randint(2, 20) ....: m = random.randint(0, n*(n-1) / 2) ....: G = graphs.RandomGNM(n, m) ....: for cc in G.connected_components_subgraphs(): ....: d1,_,_ = hyperbolicity(cc, algorithm='basic') ....: d2,_,_ = hyperbolicity(cc, algorithm='CCL') ....: d3,_,_ = hyperbolicity(cc, algorithm='CCL+') ....: d4,_,_ = hyperbolicity(cc, algorithm='CCL+FA') ....: d5,_,_ = hyperbolicity(cc, algorithm='BCCM') ....: l3,_,u3 = hyperbolicity(cc, approximation_factor=2) ....: if (not d1==d2==d3==d4==d5) or l3>d1 or u3<d1: ....: print("Error in graph ", cc.edges())
The hyperbolicity of a graph is the maximum value over all its biconnected components:
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.PetersenGraph() * 2 sage: G.add_edge(0, 11) sage: L,C,U = hyperbolicity(G); L,sorted(C),U (1/2, [6, 7, 8, 9], 1/2)
-
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 [Gro1987] 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 ofsampling_size4-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 whenalgorithm == 'sampling'.
OUTPUT:
hdict– A dictionary 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}