Nathann Cohen
email: nathann.cohen@lri.fr

David Coudert
email: david.coudert@inria.fr

Aurélien Lancin
email: aurelien.lancin@inria.fr

Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs

Keywords: Hyperbolicity, algorithm, graph, approximation Hyperbolicité, algorithme, graphe, approximation

Let G be a connected graph, and let d(a, b) denotes the shortest path distance between vertices a and b of G. The graph G is δ-hyperbolic if for any vertices a, b, c, d of G, the two largest of the three sums S 1 = d(a, b) + d(c, d), S 2 = d(a, c) + d(b, d), and S 3 = d(a, d) + d(b, c) differ by at most 2δ. This can be determined in time O(n 4 ) which could be prohibitive for large graphs.

In this document, we propose an exact algorithm for determining the hyperbolicity of a graph that is scalable for large graphs. The time complexity of this algorithm is a function of the size of the largest bi-connected component of the graph, of the shortest path distance distribution in this component and of the value of the hyperbolicity. In the worst case, the time complexity remains in O(n 4 ), but it is much faster in practice. Indeed, it allowed us to compute the exact hyperbolicity of all maps of the autonomous systems of the Internet provided by CAIDA and DIMES. We also propose both a multiplicative factor and an additive constant approximation algorithms. Finally, we also analyze further the time complexity of our exact algorithm for several class of graphs.

Introduction

In the last years, extensive work have been carried out to better understand the structural properties of the Internet topology. One of the main objective of these studies is to design new routing models that could face the current growth rate of the Internet topology and improve upon the actual inter-domain routing protocol, BGP (Border Gateway Protocol), in terms of scalability. In particular, it has been shown that the Internet topology can be accurately embedded into an hyperbolic space [START_REF] Boguna | Sustaining the Internet with Hyperbolic Mapping[END_REF] and that a simple greedy-forwarding algorithm can be expected to perform very well [START_REF] Papadopoulos | Greedy forwarding in scale-free networks embedded in hyperbolic metric spaces[END_REF].

The (Gromov) hyperbolicity of a graph reflects how the metric space (distances) of a graph is close to the metric space of a tree. Gromov [START_REF] Gromov | Hyperbolic groups[END_REF] defines the notion of δ-hyperbolic metric spaces using the notion of δ-thin triangles. More precisely, given any three points x, y, and z of a hyperbolic metric space, the triangle (x, y, z) is δ-thin if any point of the geodesic joining x and y is at distance at most δ of one of the geodesics joining x to z or y to z. A δ-hyperbolic space is a geodesic metric space in which every geodesic triangle is δ-thin. In other words, a graph has hyperbolicity at most δ if, for any u, v, w ∈ V (G) and for any shortest paths P uv , P vw , P uw between these three vertices, any vertex in P uv is at distance at most δ from P vw ∪P uw . Intuitively, in a graph with small hyperbolicity, the shortest-paths joining a pair of vertices are close to each other. For instance, trees and cliques are 0-hyperbolic which reflects the uniqueness of shortest paths, while n × n grids are n -1 hyperbolic since these graphs have many different shortest paths between pairs of vertices.

An alternative definition given by Gromov [START_REF] Gromov | Hyperbolic groups[END_REF], and called the 4-points condition, is the following. Let d(u, v) denote the distance between vertices u and v. A metric space is δhyperbolic if for any four points u, v, w, x the two largest of the distance sums d(u, v) + d(w, x), d(u, w) + d(v, x), d(u, x) + d(v, w) differ by at most 2δ. This notion extends to connected graphs and we say that a connected graph G = (V, E) equipped with its standard graph metric d G (shortest path distance) is δ-hyperbolic if the metric space (V, d G ) is δ-hyperbolic. In other words, a connected graph G is δ-hyperbolic if it satisfies the 4-points condition. The hyperbolicity of a graph measures its tree-likeness. The less the value of δ is, the more the graph looks like a tree. Moreover, it can be observed that the hyperbolicity of a connected graph is the maximum value of the hyperbolicity of its biconnected components.

From this second definition it is obvious that determining the hyperbolicity δ of a graph of order n can be done in time O(n 4 ), by testing all 4-tuples of vertices of the graph. An implementation of the naive algorithm for determining the hyperbolicity of a graph as been included into the distory (Distance Between Phylogenetic Histories) package [START_REF]distory: Distance between phylogenetic histories[END_REF] of the CRAN (The Comprehensive R Archive Network) project [START_REF]CRAN: The Comprehensive R Archive Network project[END_REF]. This package is devoted to the study of geodesic distance between phylogenetic trees and associated functions. The implementation uses the "revolving doors Gray code" principle [START_REF] Knuth | The art of computer programming, volume 4, Fascicle 2, chapter Generating All tuples and permutations[END_REF] for visiting all 4-tuples of the input graph. The time complexity has recently been improved to O(n 3.69 ) [START_REF] Fournier | Computing the Gromov hyperbolicity of a discrete metric space[END_REF] using the fast (max,min)matrix multiplication algorithm proposed in [START_REF] Duan | Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths[END_REF]. However, the computation time for large-scale graphs remains prohibitive. For instance, for a graph with 25 815 vertices (size of the largest biconnected component of the last CAIDA map of the Autonomous Systems of the Internet [START_REF]The Cooperative Association for Internet Data Analysis (CAIDA)[END_REF]), the algorithm has to iterate over around 1.85 10 16 4-tuples which represents several weeks of computations.

Also, a heuristic algorithm for determining the hyperbolicity of CAIDA AS maps has been used in [START_REF] De Montgolfier | Treewidth and hyperbolicity of the internet[END_REF], and a 2-approximation algorithm, with running time in O(n 3 ), is obtained fixing one vertex and evaluating all possible 4-tuples containing that vertex [START_REF] Chepoi | Notes on diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs[END_REF]. Clearly, faster exact and approximate algorithms are needed. Furthermore, these algorithms would be useful in other research fields where the hyperbolicity property is used such as network security [START_REF] Jonckheere | A hyperbolic geometric approach to multipath routing[END_REF][START_REF] Jonckheere | Geometry of network security[END_REF], traffic flow [START_REF] Narayan | The Large Scale Curvature of Networks[END_REF] and phylogenetics [START_REF] Dress | Basic Phylogenetic Combinatorics[END_REF].

The need for more efficient algorithms has been expressed by many authors, for instance it has recently been mentioned in the conclusion of [START_REF] Chen | On the hyperbolicity of small-world and tree-like random graphs[END_REF] that "exact computation of δ by its definition takes O(n 4 ) time, which is not scalable to large graphs, and thus the design of more efficient exact or approximation algorithms would be of interest".

Our results

In this paper, we present a new exact algorithm for computing the hyperbolicity of a graph. It is the first exact algorithm scalable for large graphs. Indeed, applied to the latest CAIDA map (2012/06/01), we have been able to reduce the computation time from 24 expected days with the naive algorithm to 8 days with our algorithm. Furthermore, the proposed algorithm can be turned into an approximation algorithm with tunable multiplicative factor or additive constant. While the worst case time complexity of the proposed algorithm is O(n 4 ), it is much faster in practice.

We start in Section 2 with some definitions and notations. Then we formally describe our algorithm for computing the hyperbolicity of a graph in Section 3 and give hints on its time complexity. We also explain how to turn this algorithm into an approximation algorithm. Then we show in Section 4 how to use a partition by clique-separators to speed-up the running time of the algorithm. In Section 5, we evaluate experimentally the performances of our exact algorithm. Next, in Section 6, we report on the computation of the hyperbolicity of large-scale graphs, namely CAIDA and DIMES maps of the Internet autonomous systems topology. Last, we list some simple results and proofs on the hyperbolicity of particular graph classes in Appendix A.

Definitions and known results

In this section, we first recall the definition of the hyperbolicity of a graph and fix some notations. Then, we survey some known results, in particular the value of the hyperbolicity of some families of graphs, and general lower and upper bounds.

Let G be a connected graph, and let d(a, b) denotes the shortest path distance between vertices a and b of G. The hyperbolicity of a graph has been defined by Gromov [START_REF] Gromov | Hyperbolic groups[END_REF] as follows. In this paper, we consider unweighted graphs only. Therefore, the possible values of δ are half-integers, that is

δ ∈ i 2 , i ∈ N . Furthermore δ ≤ D 2 ,
where D is the diameter of the graph. This result also follows from Lemma 5 that we will prove in next section.

The hyperbolicity of a graph is the maximum of the hyperbolicity of its biconnected components. To show this, let x be a cut-vertex of the graph G and w.l.o.g. let B 1 and B 2 be the two components of G separated by x. Let now a, b, c ∈ B 1 and d ∈ B 2 . We have is the same than for the 4-tuple a, b, c, x (See Fig. 2a). Similarly, when a, b ∈ B 1 and c, d ∈ B 2 , the computed value will always be 0 (See Fig. 2b). For some families of graphs it is possible to give either the exact value of their hyperbolicity. In particular, we have:

S 1 = d(a, b)+d(c, d) = d(a, b)+d(c, x)+d(x, d), S 2 = d(a, c)+d(b, d) = d(a, c)+d(b, x)+d(x,
Inria S 1 = d(a, b) + d(c, d) S 2 = d(a, c) + d(b, d) S 3 = d(a, d) + d(b, c) If S 1 ≥ S 2 ≥ S 3 , then δ ≤ S1-S2 2
• Block graphs (i.e., connected graph in which every 2-connected subgraph is a clique) are 0-hyperbolic, and so are trees and cliques;

• Cycles of order n = 4p + ε, with p ≥ 1 and ε ∈ {0, 1, 2, 3}, are (p -1/2)-hyperbolic when ε = 1, and p-hyperbolic otherwise;

• n × m grids, with 2 ≤ n ≤ m, are (n -1)-hyperbolic;

• d-dimensional grids of side s are (s -1) d/2 -hyperbolic (see proof in Appendix A);

• The hypercube H 2 (n) of dimension n and order 2 n is n/2 -hyperbolic (see proof in Appendix A);

• Chordal graphs are (≤ 1)-hyperbolic and 1-hyperbolic chordal graphs have been characterized [START_REF] Bandelt | 1-hyperbolic graphs[END_REF][START_REF] Brinkmann | On the hyperbolicity of chordal graphs[END_REF][START_REF] Koolen | Hyperbolic bridged graphs[END_REF];

• k-chordal graphs with k ≥ 4 are (≤ k/4 )-hyperbolic [START_REF] Wu | Hyperbolicity and chordality of a graph[END_REF].

Some theoretical bounds according to other graph parameters have also been established. Let g(G) denotes the girth of a graph (i.e., length of the shortest cycle of the graph). We have

g(G) 4
-ε g ≤ δ, where ε g = 1 2 when g(G) ≡ 1 (mod 4) and 0 otherwise. An upper bound has been established similarly in [START_REF] Carballosa | Gromov hyperbolicity of line graphs[END_REF] using the circumference c(G) of the graph, that is the maximum length of its cycles. A tighter upper bound follows from the chordality k(G) of the graph since for any k-chordal graph we have k(G) ≤ c(G). Summarizing, Theorem 2. For every graph G, we have g(G)

4 -ε g ≤ δ(G) ≤ k(G)

4

, where ε g = 1 2 when g(G) ≡ 1 (mod 4) and 0 otherwise.

Other bounds on the hyperbolicity of a graph have been established. Let β(G) be the independence number of G (i.e., cardinality of the largest independent set) and let γ(G) be the domination number of G (i.e., size of the smallest dominating set). We have, Theorem 3 ( [26]). For every graph G of order n, we have δ(G) ≤ min β(G), n-β(G)+2

2

. Theorem 4 ( [START_REF] Rodríguez | Bounds on Gromov hyperbolicity constant in graphs[END_REF]). For every graph G, we have δ(G) ≤ 3 2 γ(G).

Exact algorithm for computing the hyperbolicity

In this section, we formally describe a new exact algorithm for computing the hyperbolicity of graphs. We then give some hints on its time-complexity and explain how to turn this algorithm into an approximation algorithm.

The algorithm

Our algorithm is based on the following lemma, In order to make good use of Lemma 5, we adapt the naive O(n 4 ) algorithm so that it first tests the 4-tuples which are the most likely to yield a large hyperbolicity. More precisely, we iterate over the 4-tuples in such a way that a, b, c, d is tested before a , b , c , d if For instance, if the input graph is a n × n grid, with diameter 2n -2 and hyperbolicity δ = n -1 (so h * = 2n -2), the value of the hyperbolicity will be obtained with the first considered 4-tuple. On the other hand, if the input graph is a n × 2 grid, with diameter n and hyperbolicity δ = 1 (so h * = 2), almost all 4-tuples will be considered.

Lemma 5. Let G = (V, E) be a connected graph, let a, b, c, d ∈ V , let S 1 = d(a, b) + d(c, d), S 2 = d(a, c) + d(b,
Since we have n 2 pairs of vertices, and since Algorithm 1 considers pairs of pairs, the worst case time complexity of the algorithm is in O(n 4 ) (and has a quadratic memory usage). However, we observe that we can parameterize the time complexity with the optimal value of the hyperbolicity and the distribution of the path lengths. To do so, we use the set P [ ] of pairs (a, b) such that d(a, b) = to reformulate the algorithm with Algorithm 2.

Inria

Algorithm 1 Hyperbolicity

Require: G = (V, E) is a 2-connected graph. Ensure: δ, the hyperbolicity of G (observe that 2δ = h * ).

1: Let pairs be the list of the n 2 pairs of vertices sorted by decreasing distances 2: Let h * := 0 3: for 0 ≤ i < n 2 do 4:

(c, d) := pairs[i] 5: if d(c, d) ≤ h * then 6: break 7:
for 0 ≤ j < i do Require: G = (V, E) is a 2-connected graph. Ensure: δ, the hyperbolicity of G (observe that 2δ = h * ).

O D 1=2δ |P [ 1 ]| |P [ 1 ]| -1 2 + D 2 = 1 +1 |P [ 2 ]
Proof. Since Algorithm 2 uses Lemma 5, it considers only pairs of pairs ((a, b), (c, d)) such that The result is obtained with the first considered 4-tuple, and then the exploration is stopped and the result is returned. Chordal graphs, which have hyperbolicity at most 1 [START_REF] Brinkmann | On the hyperbolicity of chordal graphs[END_REF], are worst case instances for this algorithm since its running time increases with the gap between the diameter and the hyperbolicity. Algorithm 2 also requires to compute the distances between all pairs of vertices (line 1) and to sort these pairs by decreasing length (line 2). These operations are respectively in time O(m(n + m)) and O(n 2 log n) for a graph with n vertices and m edges.

D ≥ d(c, d) = 2 ≥ d(a, b) = 1 ≥ 2δ.
Computational complexity of Algorithm 2 depends on the distance distribution of the graph and of the computed value of the hyperbolicity. We provide a close formula on its time complexity for some particular graph classes in Appendix A. Furthermore, we show in Section 5 some experimental results which highlight the running time improvements on large-scale graphs.

Turning Algorithm 2 into an approximation algorithm

Observe that at any step of the algorithm, d(a, b)/2 = 1 /2 is an upper bound for the hyperbolicity of G, and h * /2 a lower bound. Therefore, by stopping its execution after a given time and returning the values h * and 1 , Algorithm 2 is turned into an approximation algorithm with approximation ratio 1 h * . More precisely, we can insert one of the following test after line 10 of the algorithm:

• "If computation time is larger than allowed computation time, then stop computations and return h * and 1 ". We get h * 2 ≤ δ ≤ 1 2 ; • "If 1 h * ≤ apx , then stop computations and return h * 2 ." We get an approximation of the value δ of the hyperbolicity with proven approximation factor apx (i.e.,

h * 2 ≤ δ ≤ apx • h * 2 ); • "If 1 2 -h * 2
≤ apx, then stop computations and return h * 2 ." We get an approximation of the value δ of the hyperbolicity with proven additive approximation constant apx (i.e.,

h * 2 ≤ δ ≤ h * 2 + apx).
As we show in the next section, the main part of the running time of the algorithm consists in closing the small gap between lower bounds, that are generally found very quickly, and upper bounds. Depending on the expected result, it may be appropriate to use the above rules that may allow to save time while preserving a sufficient precision.

Decomposition

In Section 2 we have seen that the hyperbolicity of a graph is the maximum of the hyperbolicity of its biconnected components. In this section, we will show that we can further reduce the problem size using a decomposition of the graph by clique-separators [START_REF] Tarjan | Decomposition by clique separators[END_REF]. We then show the benefit of this method on Internet-like graphs.

Recall that a set

X ⊂ V is a separator of a connected graph G = (V, E) if the induced subgraph G[V \ X] has at least two distincts connected components. If furthermore the induced subgraph G[X] is a clique, then X is a clique-separator for G.
Let us now show that the hyperbolicity of any 4-tuples with vertices on different parts of

G[V \ X] is at most 1 when G[X] is a clique. Lemma 7. Let G = (V, E) be a connected graph, let X ⊂ V be a clique-separator for G, and let A, B ⊂ V be two parts of G separated by X. Then for any a 1 , a 2 ∈ A and b 1 , b 2 ∈ B, we have δ(a 1 , a 2 , b 1 , b 2 ) ≤ 1. Proof. Let S 1 = d(a 1 , a 2 ) + d(b 1 , b 2 ), S 2 = d(a 1 , b 1 ) + (a 2 , b 2 ), and S 3 = d(a 1 , b 2 ) + d(a 2 , b 1 ).
We first consider the case where

S 1 ≥ S 2 ≥ S 3 . Let s 1 ∈ X be such that d(a 1 , b 1 ) = d(a 1 , s 1 ) + d(s 1 , b 1 ) and let s 2 ∈ X be such that d(a 2 , b 2 ) = d(a 2 , s 2 ) + d(s 2 , b 2 ).
In other words, s 1 (resp. s 2 ) is a vertex in X that lies on a shortest path between a 1 and b 1 (resp. a 2 and b 2 ). Clearly, we have the following relations:

d(a 1 , a 2 ) ≤ d(a 1 , s 1 ) + 1 + d(s 2 , a 2 ) d(b 1 , b 2 ) ≤ d(b 1 , s 1 ) + 1 + d(s 2 , b 2 )

Inria

From these relations, we get:

S 2 = d(a 1 , b 1 ) + (a 2 , b 2 ) = d(a 1 , s 1 ) + d(s 1 , b 1 ) + d(a 2 , s 2 ) + d(s 2 , b 2 ) ≥ d(a 1 , a 2 ) + d(b 1 , b 2 ) -2 = S 1 -2 We conclude that δ(a 1 , a 2 , b 1 , b 2 ) ≤ (S 1 -S 2 )/2 ≤ 1. Similarly, we obtain that δ(a 1 , a 2 , b 1 , b 2 ) ≤ 1 when S 1 ≥ S 3 ≥ S 2 . Now, when S 2 ≥ S 3 ≥ S 1 we use: d(a 1 , s 2 ) ≤ d(a 1 , s 1 ) + 1 d(a 2 , s 1 ) ≤ d(a 2 , s 2 ) + 1
and we get

S 2 = d(a 1 , b 1 ) + (a 2 , b 2 ) = d(a 1 , s 1 ) + d(s 1 , b 1 ) + d(a 2 , s 2 ) + d(s 2 , b 2 ) ≤ d(a 1 , b 2 ) + d(a 2 , b 1 ) + 2 = S 3 + 2 We conclude that δ(a 1 , a 2 , b 1 , b 2 ) ≤ (S 2 -S 3 )/2 ≤ 1.
Using similar arguments than in the proof of Lemma 7, we can show that 4-tuples with one vertex in one part A and the other vertices in a different part B separated by the clique G[X] from A have hyperbolicity at most 1.

Lemma 8. Let G = (V, E) be a connected graph, let X ⊂ V be a clique-separator for G, and let A, B ⊂ V be two parts of G separated by X. Then for any a ∈ A and b 1 , b 2 , b 3 ∈ B, we have δ(a, b 1 , b 2 , b 3 ) ≤ 1.
From above results, we deduce that Corollary 9. Let G = (V, E) be a connected graph, let X be a clique-separator for G, and let A i ⊂ V with i ≥ 2 be the parts of G separated by X. We have

δ(G) ≤ max 1, max i=1,2,•••k δ(G[A i ∪ X])
Recall that we can decide in linear time if the graph has hyperbolicity at most 1 [START_REF] Bandelt | 1-hyperbolic graphs[END_REF][START_REF] Brinkmann | On the hyperbolicity of chordal graphs[END_REF][START_REF] Koolen | Hyperbolic bridged graphs[END_REF]. Therefore, when we know that the hyperbolicity is at least 1, we use Corollary 9 to decompose the graph into smaller parts on which to compute the hyperbolicity. Moreover, above results can be used recursively if some graph G[A i ∪ X] also has a clique-separator. The complete decomposition of the graph by clique-separators can be done in time O(|V | • |E|) [START_REF] Tarjan | Decomposition by clique separators[END_REF]. Figure 3 illustrates such decomposition. The decomposition is represented as a tree in which internal vertices corresponds to clique separators and leaves to parts that can not be further decomposed. The subtrees attached to vertex X i corresponds to the parts of the graph separated by clique X i . Given such decomposition, it remains to compute the hyperbolicity of the subgraph G

[A j ∪ X i ],
where A j is a leaf vertex and X i is the father of A j in the tree representing the decomposition.

As an example, when the input graph is a 2 × n grid, the pre-processing will decompose the graph using clique-separators of size two (edges) into n -1 4-cycles. Since 4-cycles are 1-hyperbolic, we conclude directly that the 2 × n grid also is.

In view of the interest of the decomposition by clique-separators, one may ask whether separators of larger diameters could also be used to divide the graph into smaller parts when lower bounds on the hyperbolicity are known. Unfortunately, the problem of finding a s -t separator (i.e., a set X of vertices such that s and t belong to distinct connected components of G \ X) of diameter h with h ≥ 2 is NP-hard [START_REF] Heggernes | On the parameterized complexity of finding separators with non-hereditary properties[END_REF] (more precisely, it is W[1]-hard).

Let us now highlights the interest of a decomposition by clique-separators on some maps of the autonomous system (AS) of the Internet collected by CAIDA and DIMES. We have reported in Table 1 for each map the size of the largest biconnected component (LBCC) and the size of the connected component resulting from the following process: we remove successively from the graph a vertex u if the induced subgraph of its neighbors, G[Γ(u)], is a clique (i.e., if the vertex is simplicial ). This is a restricted usage of a decomposition by clique-separators but it already shows that we can significantly reduce the size of the input graph.

AS

Experimental performances

The algorithm presented in this paper will soon be included (patch #13808 [START_REF]Gromov hyperbolicity of graphs[END_REF]) into Sage, an free mathematics software [START_REF]Sage open-source mathematical software system[END_REF] licensed under the GPL combining the power of many existing open-source packages into a common Python-based interface. Is has been also developed into Grph [START_REF] Grph | [END_REF], a Java based library for graph computation.

We have used our implementation in Sage to evaluate the performances of Algorithm 2 coupled with the elimination of simplicial vertices as described in Section 4. We first report some computation results on N * M grids. Next, in Section 5.2 we report experiments on Barabasi-Albert random graphs. Our results show that our algorithm outperforms previous algorithms by orders of magnitude. We then analyze further in Section 5.3 the performances of the algorithm Inria on CAIDA AS maps. In particular, Algorithm 2 allows us to compute the hyperbolicity of the last CAIDA AS maps (n = 25815 for the largest biconnected component of the CAIDA map of September 2012) in 8 days while the running time of the algorithm proposed in [START_REF] Fournier | Computing the Gromov hyperbolicity of a discrete metric space[END_REF] was estimated to be around 24 days (assuming that 10 10 operations are performed per second).

N × M grids

We have reported in Table 2 the evolution of the computation time of Algorithm 2 on N × M grids such that N × M = 2 2 * 3 2 * 4 2 = 576 and N × M = 2 2 * 3 2 * 5 2 = 900. The running times are averages over 10 executions of the algorithm. The hyperbolicity of a N × M grid is δ N ×M = min {N, M } -1. As expected, the computation time on square grids is way smaller than for grids with sides of very different sizes.

In Section 3, we said that rectangular grids are some of the worst case instances for Algorithm 2. To verify this claim, we have plotted in Figure 4 the relative number of visited 4-tuples with Algorithm 2 compared to the total number of 4-tuples in the graph. Recall that a 4-tuple may be visited up to three times by the algorithm. In these plots, we observe that as soon as the sides of the grids differ by a factor at least 6, then the computation time of Algorithm 2 is larger than the naive algorithm, but it is much faster when the sides of the grid differ by a factor less than 6. 2a) and N × M = 2 2 * 3 2 * 5 2 = 900 (Table 2b).

N

Barabasi-Albert (BA) graphs

Recall that BA random graph model has been proposed in [START_REF] Albert | Statistical mechanics of complex networks[END_REF] to generate random scale-free graphs. It proceeds as follows: we start with an initial connected graph on n 0 ≥ 2 nodes (e.g., a random tree), and then we add new nodes with k links using the preferential attachment principle (i.e., the probability of connecting to an existing node depends on its current degree).

To evaluate the performances of Algorithm 2 on BA graphs, we have generated graphs with number of nodes in the range [1 000..10 000] and degree k of new nodes in the range [2..10]. Reported values are averages over 100 graphs. We first report in Figure 5 the average hyperbolicity of generated graphs. We observe that the hyperbolicity of BA graphs decreases with the increase of the degree k of newly added nodes, and that for fixed value of k it increases with the number of nodes. These results are explained by the preferential attachment principle which refrains the creation of long induced cycles. The same behavior is observed when changing the size n 0 of the initial graph with some shifting. Next, we report in Figure 6b the average number of visited 4-tuples during the execution of the algorithm. The ratio of the average number of visited 4-tuples over the total number of 4-tuples of the graphs varies between 10 -3 for N = 7 000 and k = 5 to 10 -8 when N = 10 000 and k = 5. This highlights the drastic running time improvement of Algorithm 2 over the algorithm proposed in [START_REF] Fournier | Computing the Gromov hyperbolicity of a discrete metric space[END_REF] on BA graphs which is from 10 3 to 10 8 times faster. We have to mention that BA graphs have no or very few simplicial vertices and so the decomposition method reported in Section 4 is not helpful in this case.

In Figure 6a we report the average computation time. The general tendency is a slow increase of the computation time with the increase of the parameter k, reflecting that the computation time is in general dominated by the computation of the distances. As reported in Figure 6b, the number of visited 4-tuples is quite small. We also observe a significant increase of the To better illustrate the impact of the parameter k on the computation time, we plotted in Figure 7a the average computation time function of the parameter k together with the distance distribution in Figure 7b for k = 4 to k = 6 when N = 5 000. In Figure 7a, we observe peaks on the computation time for particular combinations of the number of nodes and the parameter k, for instance when N = 5 000 and k = 5. In order to explain this behavior, recall that the search space is cut each time the algorithm discovers a new lower bound on the hyperbolicity, thus reducing the number of 4-tuple on which it has to iterate. However, if the number of pair of vertices at distance l ≥ 2δ is high, then our algorithm will have to spend time on these pairs of vertices to prove the hyperbolicity. When taking a closer look at the value of the hyperbolicity in Figure 5 and the distance distribution in Figure 7b (for BA graphs with N = 5 000, k = 5 and k = 6), we remark that the average hyperbolicity is 2, while when k = 5 there is a larger proportion of pairs at distance larger than 2δ = 4 than with parameter k = 6, leading to a higher number of 4-tuples tested. Finally, when k = 4, the average hyperbolicity is 2.5 and the proportion of pair of vertices at distance 2δ = 5 is very low compared to the graphs generated with k = 5 and k = 6, leading to a smaller average computation time.

CAIDA AS maps

We have reported in Table 3 the size of the largest biconnected component (LBCC), the hyperbolicity, the running time and the number of visited 4-tuples during the execution of Algorithm 2 (using decomposition methods presented in Section 4) when computing the hyperbolicity of some CAIDA AS maps. We have selected the maps with different values of the hyperbolicity to highlight the running time improvement of Algorithm 2. As expected with the time complexity expressed in Proposition 6, the running time improvement is correlated to the hyperbolicity of the CAIDA maps. Indeed, Algorithm 2 is more than 100 times faster than the naive algorithm for these maps. Nevertheless, the running times remains large. As explained in Section 3, at each step of the execution of Algorithm 2 we get proven lower and upper bounds for the hyperbolicity of the considered graph. We plotted in Figure 8a the time at which new lower and upper bounds are obtained when computing the hyperbolicity of the maps of Table 3 and in Figure 8b the corresponding number of visited 4-tuples. We observe that a few minutes of computations is sufficient for the lower bound to reach the optimal value but that the time to decrease the upper bounds to the optimal value could be very long. For maps with low hyperbolicity, almost all computation time is spent to prove the optimality of the lower bound.

AS map name LBCC δ

Time Visited 4-tuples Tot. Table 3: Computation time of the hyperbolicity of some CAIDA AS maps.

In fact, the computational complexity of Algorithm 2 given in Proposition 6 is in the worst case. It is assumed that the certificate for the hyperbolicity of the input graph G is found with the last visited 4-tuple. It is however likely that this certificate will be found soon in the computations as observed in Figure 8a, increasing earlier the lower bound and reducing the search space. This was observed in all our computations. We tried relabeling randomly the vertices to change the ordering in which pairs of vertices at distance are considered. This experiment had no impact on the total number of visited 4-tuples. This shows again that certificates for the hyperbolicity are found very early and that the remaining computation time is devoted reducing the upper bound, hence proving the optimality.

Hyperbolicity of large-scale graphs

Thanks to Algorithm 2 and to the decomposition method reported in Section 4, we have been able to compute the hyperbolicity of all available CAIDA AS maps since 2004 until June 2012 (190 maps). Although the new algorithm improves upon the algorithm proposed in [START_REF] Fournier | Computing the Gromov hyperbolicity of a discrete metric space[END_REF], the overall computation time represents several weeks of computations on a single PC. Indeed, computing the hyperbolicity of the 2012 CAIDA AS map only took 8 days of computations (but maps with hyperbolicity 3 require only a few minutes of computations). The computed values are reported in Figure 9 where we have one dot per CAIDA AS map. The first axis corresponds to the dates the maps where produced. We also reported the linear interpolation of the hyperbolicity. First, in Figure 9 we observe some measurement bias. For instance, the map of 07/06/2004 has hyperbolicity 2 while maps produced in the months before and after have hyperbolicity 2.5. The same holds for the maps with hyperbolicity 3 (05/09/2005 and 06/02/2006). A frequent variation is also observed between consecutive maps in the period from 2007 till 2009. We still do not know whether this behavior is due to some bias of the measurement or whether it comes from some hidden fact.

The main observation resulting from this experiment is that the hyperbolicity of CAIDA maps has decreased in average from 2.5 to 2 and the hyperbolicity is stable since October 2009. This is not surprising and it is clearly due to the fact that the AS network has become bigger during the last decade. In particular, many new links have appeared and have broken large cycles that made 4-tuples with bigger hyperbolicity.

We have also computed the hyperbolicity of all DIMES AS maps [START_REF] Shavitt | DIMES: Let the Internet Measure Itself[END_REF] since 2007 (62 maps). These maps are smaller than CAIDA AS maps and so computations are faster. Moreover, around 40% of these nodes are discarded by recursive deletion of simplicial vertices (see Section 4) so that large portions of these maps are quickly eliminated. The results including certificates are Inria reported in Appendix A. We found that all these maps have hyperbolicity 2 but comparison of the running times of Algorithm 2 highlight the structural differences of these maps.

Conclusion

We proposed a new exact algorithm to compute the hyperbolicity on large graphs. This algorithm cuts the search space each time a new lower bound is found. We analyzed the complexity of the algorithm and showed the dependency with the size of the largest biconnected component, the computed value of the hyperbolicity and the shortest-path distance distribution. This algorithm can be used as an approximation algorithms. If the complexity of the algorithms remains in O(n 4 ), we reduce the computational time from an estimated 24 days of computation for the algorithm proposed in [START_REF] Fournier | Computing the Gromov hyperbolicity of a discrete metric space[END_REF] (assuming that 10 10 operations are performed per second) to only 8 days for our algorithm. Thus, we computed the exact value of the hyperbolicity for all the 190 available CAIDA maps and analyzed their evolution. The hyperbolicity of the AS MAPS is slowly decreasing from 2.5 to 2. Some exceptional graphs with hyperbolicity 3 appear from time to time, which can be explained by measurement bias correlated with a smallest number of nodes and edges comparatively to the others maps. We also explained how to use a decomposition by cliqueseparators to speedup the resolution. We have in particular observed that such decomposition allows to remove around 16% of the vertices of the largest biconnected component of the CAIDA map of 2012 and around 40% of the vertices of DIMES AS maps.

The next step is to implement a parallel version of our algorithms in order to address larger topologies such as the router map of the Internet. Nonetheless, the computation time may still be prohibitive on such large graphs and so new efficient decomposition methods as well as lowerbound heuristics would be helpful. We shall also further analyze the presence of a large number of simplicial vertices in AS maps.

A Simple results

Lemma 10. Cycles of order n = 4p + ε, with p ≥ 1 and ε ∈ {0, 1, 2, 3}, are (p -1/2)-hyperbolic when ε = 1, and p-hyperbolic otherwise.

Proof of Lemma 10. Let C be a cycle of order n = 4p + ε, with p ≥ 1 and ε ∈ {0, 1, 2, 3}, and let the vertices be indexed {0, 1, • • • , 4p + ε -1}. Let a, b, c, d be four vertices of C. In order to break symmetries and w.l.o.g. we assume that a = 0 < b ≤ p < c ≤ 2p+ ε/2 < d ≤ 3p+ ε/2 + ε/3 , and so we have

1 ≤ d(a, b) ≤ p (1a) p + 1 ≤ d(a, c) ≤ 2p + ε/2 (1b) p + ε -ε/2 -ε/3 ≤ d(a, d) ≤ 2p + ε -ε/2 -1 (1c) 1 ≤ d(b, c) ≤ 2p + ε/2 -1 (1d) p + ε/2 + 1 ≤ d(b, d) ≤ 2p + ε/2 (1e) 1 ≤ d(c, d) ≤ 2p + ε/2 + ε/3 -1 (1f)
and, Let us now assume that S 2 = max {S 1 , S 2 , S 3 }. Since S 1 + S 3 = 4p + ε, the best we can do to maximize h(a, b, c, d) is to choose values of a, b, c, d such that the maximum among S 1 and S 3 is the closest possible to 2p + ε/2, and such that S 2 is as large as possible. This can be achieve choosing b = p, c = 2p + ε/2 , and d = 3p + ε/2 + ε/3 . Indeed, with these values, we get S 2 = 4p+2 ε/2 , so the maximum possible value, and S 1 = 2p+ ε/3 and S 3 = 2p+ε-ε/3 ≥ S 1 which are the closest possible of 2p + ε/2. We obtain h(a, b, c, d

2 ≤ S 1 = d(a, b) + d(c, d) ≤ 3p + ε/2 + ε/3 -1 (1g) 2p + ε/2 + 2 ≤ S 2 = d(a, c) + d(b, d) ≤ 4p + 2 ε/2 (1h) p + ε -ε/2 -ε/3 + 1 ≤ S 3 = d(a, d) + d(b, c) ≤ 4p + ε -2 (1i)
) = 2p + 2 ε/2 -ε + ε/3 .
Since ε ∈ {0, 1, 2, 3}, it follows that cycles of order n = 4p + ε, with p ≥ 1, are (p -1/2)hyperbolic when ε = 1, and p-hyperbolic otherwise.

Lemma 11. n × m grids, with 2 ≤ n ≤ m, are (n -1)-hyperbolic. Proof of Lemma 11. Let {v i,j , 1 ≤ i ≤ n, 1 ≤ j ≤ m} the vertices of the n × m grid.
Firstly, suppose that n = m, and consider the four vertices v 1,1 , v 1,n , v n,1 , v n,n . We have

S 1 = d(v 1,1 , v 1,n ) + d(v n,1 , v n,n ) = 2n -2, S 2 = d(v 1,1 , v n,n ) + d(v 1,n , v n,1 ) = 4n -4, S 3 = d(v 1,1 , v n,1 ) + d(v 1,n , v n,n ) = 2n -2, and so h(v 1,1 , v 1,n , v n,1 , v n,n ) = 2n -2. Since h(a, b, c, d) is
less or equal to the diameter of the graph for any 4-tuple (a, b, c, d), this value is optimal. Secondly, let n ≤ x ≤ m and consider the four vertices

v 1,1 , v 1,x , v n,1 , v n,x . We have S 1 = d(v 1,1 , v 1,x ) + d(v n,1 , v n,x ) = 2x -2, S 2 = d(v 1,1 , v n,x ) + d(v 1,x , v n,1 ) = 2n + 2x -4, S 3 = d(v 1,1 , v n,1 ) + d(v 1,x , v n,x ) = 2n -2, and since S 2 ≥ S 1 ≥ S 3 we obtain h(v 1,1 , v 1,x , v n,1 , v n,x ) = 2n -2.

Inria

Let now v i1,j1 , v i2,j2 , v i3,j3 , v i4,j4 be four vertices of the grid such that 1 < i 1 , i 2 ≤ n/2 < i 3 , i 4 < n, and 1 < j 1 , j 3 ≤ n/2 < j 2 , j 4 < n, and let us show that h

(v i1,j1 , v i2,j2 , v i3,j3 , v i4,j4 ) ≤ h(v i1-1,j1-1 , v i2,j2 , v i3,j3 , v i4,j4 ). We have S 1 = d(v i1,j1 , v i2,j2 )+d(v i3,j3 , v i4,j4 ), S 2 = d(v i1,j1 , v i3,j3 )+ d(v i2,j2 , v i4,j4 ), and S 3 = d(v i1,j1 , v i4,j4 ) + d(v i2,j2 , v i3,j3 ).
According the shortest path distance in the grid, we have

d(v i1,j1 , v i2,j2 ) + 1≤ d(v i1-1,j1-1 , v i2,j2 ) ≤ d(v i1,j1 , v i2,j2 ) + 2 (2a) d(v i1,j1 , v i3,j3 ) + 1≤ d(v i1-1,j1-1 , v i3,j3 ) ≤ d(v i1,j1 , v i3,j3 ) + 2 (2b) d(v i1-1,j1-1 , v i4,j4 ) = d(v i1,j1 , v i4,j4 ) + 2 (2c)
and so

S 1 + 1≤ S 1 = d(v i1-1,j1-1 , v i2,j2 ) + d(v i3,j3 , v i4,j4 ) ≤ S 1 + 2 (2d) S 2 + 1≤ S 2 = d(v i1-1,j1-1 , v i3,j3 ) + d(v i2,j2 , v i4,j4 ) ≤ S 2 + 2 (2e) S 3 = d(v i1-1,j1-1 , v i4,j4 ) + d(v i2,j2 , v i3,j3 ) = S 3 + 2 (2f)
From these values, we get

|S 1 -S 2 | ≤ |S 1 -S 2 | + 1, |S 1 -S 3 | ≤ |S 1 -S 3 | + 1, and |S 2 -S 3 | ≤ |S 2 -S 3 | + 1. Therefore, we have h(v i1,j1 , v i2,j2 , v i3,j3 , v i4,j4 ) ≤ h(v i1-1,j1-1 , v i2,j2 , v i3,j3 , v i4,j4
), and we can prove the same result when decreasing some of the values of i 1 , i 2 , j 1 , j 3 or increasing some of the values of i 3 , i 4 , j 2 , j 4 .

Altogether, we conclude that n × m grids, with 2 ≤ n ≤ m, are (n -1)-hyperbolic.

Lemma 12. The d-dimensional grid of side s is (s -1) d/2 -hyperbolic.
Proof. The vertices of the d-dimensional grid of side s are labeled

(u 0 , u 1 , • • • , u d-1 ), with u i ∈ [0..s -1] for i ∈ [0..d -1],
and there is an edge between u = (u

0 , u 1 , • • • , u d-1 ) and v = (v 0 , v 1 , • • • , v d-1 ) if u i = v i for i ∈ [0..j -1] ∪ [j + 1..d -1] and either v j = u j + 1 if u j + 1 < s or v j = u j -1 if u j -1 ≥ 0.
Consider now the four vertices u, v, w, x such that

u = (0, 0, • • • , 0) contains only 0's (3a) v = (s -1, s -1, • • • , s -1) contains only s -1's (3b) w = (w 0 , w 1 , • • • , w d-1 ) contains d/2 0's and d/2 s -1's (3c) x = (x 0 , x 1 , • • • , x d-1
) obtained from w replacing each 0 with a s -1 and each s -1 with a 0 (3d)

We have for instance d(u, w) = (s -1) d/2 , and so

S 1 = d(u, v) + d(w, x) = 2(s -1)d (3e)
S 2 = d(u, w) + d(v, x) = 2(s -1) d/2 (3f)
S 3 = d(u, x) + d(v, w) = 2(s -1) d/2 (3g) We obtain h(u, v, w, x) = S 1 -S 3 = 2(s -1) d/2 .
The optimality proof is similar to the proof of Lemma 11.

Corollary 13. The hypercube H 2 (n) of dimension n and order 2 n is n/2 -hyperbolic.

Proof of Corollary 13. The proof follows from Lemma 12 since the n-dimensional grid of side 2 is the hypercube H 2 (n).

B Hyperbolicity of some CAIDA AS maps

Table 4 lists the hyperbolicity of all CAIDA AS maps since 2004 [START_REF]The Cooperative Association for Internet Data Analysis (CAIDA)[END_REF]. We have also reported in this table the number of 4-tuples with given hyperbolicity among a large set of randomly chosen 4-tuples. We can derive from these values the statistical distribution of the hyperbolicity of the 4-tuples. Last, we have reported some hyperbolicity certificates, i.e., a 4-tuple with maximum hyperbolicity.

Inria

C Hyperbolicity of some DIMES AS maps

Table 5 lists the hyperbolicity of all DIMES AS maps since 2007 [START_REF] Shavitt | DIMES: Let the Internet Measure Itself[END_REF], with the corresponding certificates. We have also reported in this table the number of visited 4-tuples for Algorithm 2 with and without good-core decomposition, as well as the total number of 4-tuples in the largest biconnected components of these graphs. We observe that Algorithm 2 out-performs the basic algorithm by a factor of at least 10 4 , and that the good-core decomposition provides in average a extra factor 10.

Definition 1 (

 1 [START_REF] Gromov | Hyperbolic groups[END_REF]). The graph G is δ-hyperbolic if for any vertices a, b, c, d of G, the two largest of the three sums S 1 = d(a, b) + d(c, d), S 2 = d(a, c) + d(b, d), and S 3 = d(a, d) + d(b, c) differ by at most 2δ.

Figure 1 illustrates

 1 Figure1illustrates Definition 1 also called 4-points condition. In the following, we denote h(a, b, c, d) the difference between the two largest of the three sums S 1 , S 2 , and S 3 , and so we have 2δ = max a,b,c,d∈V h(a, b, c, d).In this paper, we consider unweighted graphs only. Therefore, the possible values of δ are half-integers, that isδ ∈ i 2 , i ∈ N . Furthermore δ ≤ D 2 ,where D is the diameter of the graph. This result also follows from Lemma 5 that we will prove in next section.The hyperbolicity of a graph is the maximum of the hyperbolicity of its biconnected components. To show this, let x be a cut-vertex of the graph G and w.l.o.g. let B 1 and B 2 be the two components of G separated by x. Let now a, b, c ∈ B 1 and d ∈ B 2 . We have

  d), and S 3 = d(a, d)+d(b, c) = d(a, x)+d(x, d)+d(b, c). The computed value for the 4-tuple a, b, c, d

Figure 1 :

 1 Figure 1: The 4-points condition.

Figure 2 :

 2 Figure 2: Hyperbolicity over biconnected components

  d), and S 3 = d(a, d) + d(b, c), and assume w.l.o.g. that S 1 ≥ max {S 2 , S 3 }. We have h(a, b, c, d) ≤ min {d(a, b), d(c, d)} Proof. We have S 2 +S 3 = d(a, c)+d(b, d)+d(a, d)+d(b, c) = (d(a, c) + d(b, c))+(d(a, d) + d(b, d)). Using the triangular inequality, we deduce S 2 + S 3 ≥ 2 • d(a, b). Since S 1 is the largest sum, we have h(a, b, c, d) = S 1 -max {S 2 , S 3 } ≤ S 1 -(S 2 + S 3 )/2 ≤ S 1 -d(a, b) = d(c, d). We obtain similarly that h(a, b, c, d) ≤ d(a, b).

  min(d(c, d), d(a, b)) > min(d(c , d ), d(a , b )). Assuming that pairs is the list of the n 2 pairs of vertices sorted decreasingly (we naturally ignore 4-tuples such that d(a, b) ≤ d(c, d)), this yield Algorithm 1. Thanks to Lemma 5 we know that at any step of the algorithm the value of d(c, d) is an upper bound on the value of h(a, b, c, d). If the current lower bound is h * , none of the 4-tuples such that d(c, d) ≤ h * can be used to improve the lower bound. We can thus cut exploration.

8 : 10 : 2 Algorithm 2

 81022 (a, b) := pairs[j] 9: h * := max {h * , h(a, b, c, d)} if d(a, b) ≤ h * then 11: break 12: return h * /Hyperbolicity (parameterized version)

1 :

 1 Let P [ ] be the list of pairs (a, b) ∈ V × V such that d(a, b) == 2: Sort P [ ] in lexicographic order 3: Let h * := 0 4: for 1 := D down to 1 do 5:

for 2 := D down to 1 do 6 : 7 : 9 : 2 Proposition 6 .

 267926 for all (a, b) ∈ P [ 1 ] do for all (c, d) ∈ P [ 2 ] do {When 1 == 2 , we ensure that (a, b) < (c, d)} 8: h * := max {h * , h(a, b, c, d)} if h * == 1 then 10: return h * /Given a δ-hyperbolic graph of diameter D and the sets P [ ] of pairs of vertices at distance from each other, the time complexity of lines 4-10 of Algorithm 2 is in

  Furthermore, it uses the ordering of P [ ] to test only the |P [ ]| 2 pairs of pairs such that d(a, b) = d(c, d) = . The result follows. Typically, for the n×n grid of diameter 2n-2 and hyperbolicity n-1, we have |P [2n-2]| = 2 and so a single pair of pairs such that d(a, b) = d(c, d) = 2n -2.

Figure 3 :

 3 Figure 3: Decomposition by clique-separators.

Figure 4 :

 4 Figure 4: Relative performance of Algorithm 2 vs. the naive algorithm on N × M grids.

Figure 5 :

 5 Figure 5: Average hyperbolicity for Barabasi-Albert graphs.

  Inria computation time for the particular values of k = 5 and k = 6. (a) Computation time for Barabasi-Albert graphs. (b) Visited 4-tuples for Barabasi-Albert graphs.

Figure 6 :

 6 Figure 6: Computation time of the hyperbolicity and visited 4-tuples of Barabasi-Albert graphs.

  (a) Computation time for Barabasi-Albert graphs. (b) Distribution of distances in Barabasi-Albert graphs.

Figure 7 :

 7 Figure 7: Computation time of the hyperbolicity and distance distribution of Barabasi-Albert graphs.

  (a) Time to reach lower and upper bounds of the hyperbolicity of some CAIDA AS maps since 2004. Computation times for lower bounds are plotted from left to right, and from right to left for upper bounds. (b) Number of visited 4-tuples to reach lower and upper bounds of the hyperbolicity of some CAIDA AS maps since 2004. Number of 4-tuples for lower bounds are plotted from left to right, and from right to left for upper bounds.

Figure 8 :

 8 Figure 8: Computation time of the hyperbolicity and number of visited 4-tuples of CAIDA AS maps

Figure 9 :

 9 Figure 9: Evolution of the hyperbolicity of CAIDA AS maps since 2004.

For

  any values of b, c, d, we have S 1 + S 3 = d(a, b) + d(c, d) + d(a, d) + d(b, c) = 4p + ε, and so maximizing S 1 decreases S 3 and conversely. Observe that the maximum value of S 1 is obtained with b = p, c = p + 1, and d = 3p + ε/2 + ε/3 . For these values we have S 2 = 3p + ε/2 + ε/3 + 1 > S 1 , S 3 = p + ε -ε/2ε/3 + 1 < S 1 , and so h(a, b, c, d) = 1. Similarly, the maximum value of S 3 is obtained with b = 1, c = 2p + ε/2 , and d = 2p + ε/2 + 1, which gives S 1 = 2, S 2 = 4p + 2 ε/2 , and so h(a, b, c, d) = |ε -2 -2 ε/2 | ≤ 2.

Table 1 :

 1 Core of some CAIDA and DIMES AS maps, all with hyperbolicity 2.

	map name	LBCC Removed vertices Final size
		2010/01/20 20 940	5 391	15 549
	CAIDA	2011/01/16 23 214	6 184	16 950
		2012/06/01 25 815	6 747	19 068
		12/2010	18 764	8 056	10 708
	DIMES	10/2011	17 137	7 427	9 710
		4/2012	16 907	7 112	9 795

Table 2 :

 2 Computation time in secondes of the hyperbolicity of N × M grids such that N × M = 2 2 * 3 2 * 4 2 = 576 (Table

Table 4 :

 4 Hyperbolicity of CAIDA AS maps since 2004.

	AS map name	δ	Certificate	Visited 4-tuples Total number
	2004/01/05	5/2	3233, 8338, 8923, 13268	3.9 10 10	4.9 10 14
	2004/02/02	5/2 12497, 20807, 28983, 29226	2.4 10 10	5.1 10 14
	2004/03/01	5/2	8863, 9249, 20515, 28776	3.1 10 10	5.3 10 14
	2004/04/05	5/2 12316, 13092, 21172, 28949	1.6 10 11	5.9 10 14
	2004/05/03	5/2	5434, 12660, 12764, 20633	4.2 10 10	6.2 10 14
	2004/06/07	2	6802, 25454, 30838, 31318	8.8 10 12	6.3 10 14
	2004/07/05	5/2	1955, 6802, 20685, 25454	7.7 10 10	6.6 10 14
	2004/08/02	5/2	2148, 12644, 13105, 29335	5.4 10 10	7.0 10 14
	2004/09/06	5/2	6802, 12615, 16010, 20816	3.7 10 10	7.3 10 14
	2004/10/04	5/2	5434, 12550, 12644, 21341	5.4 10 10	7.7 10 14
	2004/11/01	5/2	5434, 13042, 21341, 30768	6.4 10 10	8.0 10 14
	2004/12/06	5/2	5379, 25454, 25496, 31340	5.5 10 10	8.4 10 14
	2005/01/03	5/2	8880, 13121, 28903, 34214	8.8 10 10	8.10 10 14
	2005/02/07	5/2	6802, 8880, 8923, 25496	9.10 10 10	8.10 10 14
	2005/03/07	5/2 13302, 15378, 15775, 24825	1.2 10 11	9.1 10 14
	2005/04/04	5/2 13105, 28903, 29632, 31258	7.5 10 10	9.5 10 14
	2005/05/02	5/2	6850, 28903, 28949, 29233	8.8 10 10	1.0 10 15
	2005/06/06	5/2 15378, 15775, 24607, 34784	1.1 10 11	1.0 10 15
	2005/07/04	5/2	6736, 8226, 12880, 15595	1.1 10 11	1.1 10 15
	2005/08/01	5/2	8471, 12983, 17480, 21103	1.0 10 11	1.1 10 15
	2005/09/05	3	12739, 12764, 16010, 34645	1.2 10 8	1.2 10 15
	2005/10/03	5/2	8825, 12507, 25306, 31549	6.6 10 10	1.2 10 15
	2005/11/07	5/2 20702, 29390, 29663, 34645	9.7 10 10	1.3 10 15
	2005/12/05	5/2 13365, 16070, 16138, 29442	8.1 10 10	1.3 10 15
	2006/01/02	5/2 13071, 15682, 21011, 29390	1.2 10 11	1.5 10 15
	2006/01/09	5/2 10747, 16070, 28733, 30952	1.5 10 11	1.4 10 15
	2006/01/16	5/2 24416, 29632, 31258, 33818	1.0 10 11	1.4 10 15
	2006/01/23	5/2 10687, 16070, 16130, 29663	1.3 10 11	1.4 10 15
	2006/01/30	5/2	8825, 12507, 29630, 31589	1.3 10 11	1.4 10 15
	2006/02/06	3	1955, 13210, 20722, 34416	4.3 10 10	1.4 10 15
	2006/02/13	5/2 21411, 28752, 29034, 29107	1.2 10 11	1.5 10 15
	2006/02/20	5/2 20778, 28858, 31077, 34775	1.5 10 11	1.5 10 15
	2006/02/27	5/2	2549, 6458, 10490, 17086	1.1 10 12	1.5 10 15
	2006/03/06	5/2 12764, 21411, 29034, 29107	1.2 10 11	1.5 10 15
	2006/03/13	5/2 16190, 29663, 35032, 35147	1.1 10 11	1.4 10 15
	2006/03/20	5/2 13310, 30861, 31023, 34379	1.8 10 11	1.5 10 15
	2006/03/27	5/2	7202, 8982, 15393, 34771	9.2 10 10	1.5 10 15
				Continued on next page
					Inria

Table 5 :

 5 Hyperbolicity of DIMES AS maps since 2007.

	AS map name δ	Certificate	Visited 4-tuples	Total number
				With	Without	of 4-tuples
	ASEdges1_2007	2	9814, 10063, 26415, 38019	3.9 10 10	4.2 10 11	8.7 10 14
	ASEdges2_2007	2 11546, 24398, 38012, 38018 6.9 10 10	6.5 10 11	6.8 10 14
	ASEdges3_2007	2	8809, 9791, 17423, 23647	6.4 10 10	8.5 10 11	1.7 10 15
	ASEdges4_2007	2	80, 6820, 8701, 9814	9.4 10 10	1.1 10 12	1.2 10 15
	ASEdges5_2007	2	2884, 7588, 10755, 40127	3.3 10 10	4.4 10 11	1.8 10 15
	ASEdges6_2007	2	6764, 8517, 9812, 15836	5.6 10 10	7.3 10 11	1.4 10 15
	ASEdges7_2007	2 10022, 27691, 28871, 32341 1.0 10 10	2.9 10 10	2.5 10 15
	ASEdges8_2007	2	8973, 29389, 34870, 35349	3.1 10 9	4.7 10 10	2.3 10 15
	ASEdges9_2007	2	841, 9575, 10550, 22684	1.3 10 10	1.9 10 11	2.3 10 15
	ASEdges10_2007 2	80, 8511, 34870, 39608	2.0 10 10	2.5 10 11	1.9 10 15
	ASEdges11_2007 2	80, 5719, 20661, 35349	1.4 10 10	1.4 10 11	1.7 10 15
	ASEdges12_2007 2 13079, 20661, 34205, 34400 1.1 10 10	1.1 10 11	1.6 10 15
	ASEdges1_2008	2	7588, 9781, 16905, 37977	3.6 10 10	3.9 10 11	1.3 10 15
	ASEdges2_2008	2 18353, 38018, 38319, 41050 6.4 10 10	4.4 10 11	3.9 10 14
	ASEdges3_2008	2	9270, 10063, 19008, 38511	3.6 10 10	4.3 10 11	1.3 10 15
	ASEdges4_2008	2	7588, 24040, 24287, 42918	3.3 10 10	4.2 10 11	1.2 10 15
	ASEdges5_2008	2	8226, 12497, 12987, 37971	3.1 10 10	3.6 10 11	1.2 10 15
	ASEdges6_2008	2 28947, 29394, 31094, 34875 1.6 10 10	1.4 10 11	1.3 10 15
	ASEdges7_2008	2	5572, 23030, 30214, 33962	3.7 10 10	9.1 10 10	3.5 10 15
	ASEdges8_2008	2	5572, 23030, 30214, 33962	2.5 10 10	1.2 10 12	4.4 10 15
	ASEdges9_2008	2	5572, 23030, 30214, 33962	6.0 10 10	2.7 10 11	4.5 10 15
	ASEdges10_2008 2	2588, 12261, 24042, 24475	2.0 10 10	8.0 10 10	4.6 10 13
	ASEdges11_2008 2	3836, 36996, 36982, 38600	4.7 10 10	4.6 10 11	2.3 10 15
	ASEdges12_2008 2	2012, 33852, 40981, 42688	1.2 10 10	1.4 10 11	3.0 10 15
	ASEdges1_2009	2 10063, 25253, 29673, 30947 1.6 10 10	1.3 10 11	2.5 10 15
	ASEdges2_2009	2	4667, 8701, 17752, 38018	5.0 10 9	4.1 10 10	2.8 10 15
	ASEdges3_2009	2 41831, 43040, 47360, 47392	6.1 10 9	7.8 10 10	3.3 10 15
	ASEdges4_2009	2 11182, 21719, 47392, 47732 1.4 10 10	1.6 10 11	2.5 10 15
	ASEdges5_2009	2 34205, 34974, 44674, 48858	2.8 10 9	2.1 10 10	4.7 10 15
	ASEdges6_2009	2 12304, 15895, 47326, 48008 1.4 10 10	5.9 10 10	5.0 10 15
	ASEdges7_2009	2	2148, 9519, 21418, 47645	1.6 10 10	2.7 10 10	4.7 10 15
	ASEdges8_2009	2	4796, 10063, 17585, 35518	1.6 10 9	1.6 10 10	4.9 10 15
	ASEdges9_2009	2	8462, 8940, 25432, 48965	5.4 10 9	1.9 10 11	4.5 10 15
	ASEdges10_2009 2	4667, 6342, 10131, 17484	5.5 10 9	5.6 10 10	4.4 10 15
	ASEdges11_2009 2 13247, 29259, 43910, 47310 2.3 10 11	5.4 10 10	4.0 10 15
					Continued on next page

Table 5 -

 5 continued from previous page AS map name δ

			Certificate	Visited	Total
	ASEdges12_2009 2 16333, 47360, 48011, 48265 5.3 10 10	7.2 10 10	3.7 10 15
	ASEdges1_2010	2 24783, 32277, 34205, 44674	6.2 10 9	6.5 10 10	4.4 10 15
	ASEdges2_2010	2	7588, 10004, 17823, 38550	7.6 10 9	5.1 10 10	4.6 10 15
	ASEdges3_2010	2 15236, 28509, 42688, 65090	3.3 10 9	4.5 10 10	4.9 10 15
	ASEdges4_2010	2	9038, 28666, 29238, 48832	5.6 10 9	6.0 10 10	4.8 10 15
	ASEdges5_2010	2 14328, 19915, 22512, 33738 5.5 10 10	6.2 10 10	5.2 10 15
	ASEdges6_2010	2	9082, 45012, 45844, 47442	6.2 10 10	2.7 10 11	4.8 10 15
	ASEdges7_2010	2	8601, 39644, 48759, 50164	2.4 10 10	4.6 10 11	4.6 10 15
	ASEdges8_2010	2 16030, 28951, 29015, 35444 9.4 10 10	3.9 10 11	5.7 10 15
	ASEdges9_2010	2	8395, 18239, 23850, 42136	1.5 10 10	1.1 10 11	5.2 10 15
	ASEdges10_2010 2 10150, 18252, 23940, 38195			5.7 10 15
	ASEdges11_2010 2 10282, 16292, 196840, 39425 5.6 10 9	5.2 10 10	5.3 10 15
	ASEdges12_2010 2	8557, 18352, 38437, 55454	2.5 10 10	7.6 10 11	5.2 10 15
	ASEdges1_2011	2	2503, 18088, 36790, 38043	9.2 10 10	7.9 10 11	5.9 10 15
	ASEdges2_2011	2 12576, 29032, 29039, 36892 3.8 10 10	1.7 10 11	6.8 10 15
	ASEdges3_2011	2 15633, 16030, 25247, 31483 9.0 10 10	1.5 10 11	4.9 10 15
	ASEdges4_2011	2	8193, 34557, 41904, 43246	1.6 10 9	2.3 10 10	5.0 10 15
	ASEdges5_2011	2 10207, 11879, 262815, 28174 1.4 10 10	6.2 10 10	4.8 10 15
	ASEdges6_2011	2	841, 6853, 8338, 25103	4.0 10 10	6.3 10 11	4.3 10 15
	ASEdges7_2011	2	2874, 29498, 44192, 45289	1.1 10 11	8.9 10 11	4.7 10 15
	ASEdges8_2011	2 23817, 25669, 33516, 40335 3.9 10 10	1.0 10 11	4.1 10 15
	ASEdges9_2011	2 32017, 37187, 37245, 49283	6.8 10 9	8.7 10 10	4.0 10 15
	ASEdges10_2011 2 12705, 29304, 34875, 53603 1.4 10 10	2.0 10 11	3.6 10 15
	ASEdges1_2012	2 10110, 18021, 35794, 38305 2.6 10 10	2.5 10 11	3.1 10 15
	ASEdges2_2012	2 24490, 28249, 45344, 45410 2.7 10 10	3.2 10 11	3.7 10 15
	ASEdges3_2012	2	7491, 41579, 47654, 56384	3.3 10 10	4.4 10 11	3.7 10 15
	ASEdges4_2012	2 24337, 38296, 38738, 47652 4.6 10 10	5.6 10 11	3.4 10 15

Inria

RESEARCH CENTRE SOPHIA ANTIPOLIS -MÉDITERRANÉE 2004 route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr

RR n°8074

Acknowledgments

This work has been partially supported FP7 STREP EULER, and ANRs AGAPE and GRATEL.

RR n°8074


Elodie Maître D'hôtel

Tristan Le Cotty

Thomas Jayne

Elodie Maitre D Hôtel
email: elodie.maitredhotel@cirad.fr

Tristan Le Cotty

Elodie Maitre

Tristan Hôtel

Thom Le Cotty

Jayne

Is a public regulation of food price volatility feasible in Africa? An arch approach in Kenya

Keywords: volatility, predictability, consistency, food, policy, Kenya JEL: D84, Q13, Q18

The 2007-2008 food crisis and current food price swings led economists to re-evaluate the potential for policy instruments to manage food price volatility. Many developing countries recently pursued price regulation policies, but the difficulties of these policies in promoting price stability is not fully understood. In particular, the ability of a stabilization policy to lower food price volatility does not depend on the nature of the policy instrument only, but also on the institutional conditions of its implementation. Kenya is a particularly interesting case as it is characterized by a rather long tradition of public intervention, and by the persistence of highly volatile prices. The consistency of the policy use appears to be key factor influencing the degree of price volatility. Applied to trade policies, this consistency is defined by the temporal relationship between the tariff level and the international price changes. To test the influence of policy consistency on price volatility, we develop an autoregressive conditionally heteroskedastic model of price determination in which prices and prices volatility are jointly estimated, using monthly data over the 1994 -2009 period in Kenya. period in Kenya.

effects both on consumers and producers [START_REF] Byerlee | Managing food price risks and instability in a liberalizing market environment : Overview and policy options[END_REF] 1 , and there are probably more voices in favor of state management of price volatility than before 2007.

A new stage for stabilization policies in developing countries

In the context of food crises, and despite unresolved debates on the respective roles that the states and the private sector should play in mitigating price instability [START_REF] Abbott | Stabilisation policies in developing countries after the 2007-2008 food crisis[END_REF], several developing countries governments have reinforced their intervention in their food markets, through tighter control of trade and marketing functions [START_REF] Demeke | Country responses to the food security crisis: Nature and preliminary implications of the policies pursued[END_REF]. The food crisis provided an invigorated rationale for stabilization policies in developing countries. Many policies have been pursued, such as trade policies (changes in import tariffs and fees, restriction and prohibition of exports) and marketing policies (reduction of taxes, release of public stocks, and price controls). Some of these policies aimed at lowering food price volatility have been accompanied by policies aimed at lowering the negative effects of food price volatility (safety nets).

The regulation of food price volatility: the feasibility debate

Despite the existence of a consensus on the adverse effects of instability, the way to manage food price volatility and the role of regulatory institutions are issues that have long divided economists. To reduce food price volatility, the question whether we should primarily rely on markets2 or whether markets require a direct public intervention (like public storage policy) is a longstanding debate.

Beyond this first best policy debate stands another debate, on the feasibility of such a policy [START_REF] Poulton | State intervention for food price stabilisation in Africa : Can it work?[END_REF]. Indeed, many countries did intervene in the regulation of their food markets, and many still do. Some have managed to achieve an effective price stability and some have not. The question unsolved is whether those who have not achieved stabilization used inappropriate instruments or whether they used appropriate instruments in an inadequate manner. This observation is the starting point of our paper that analyzes the pragmatic conditions for success of such a public intervention.

Inefficiencies may arise

A literature review of 14 different developing countries brought to light that, under certain circumstances, policies as implemented could fail to lower food price volatility or even increase it [START_REF] Gérard | Managing food price volatility for food security and development[END_REF]. This paper addresses the ability of stabilization policies to effectively lower food price volatility in Africa, considering that policies should not necessarily produce a constant price but a pattern of prices that either stabilizes and/or adds predictability to the market. In other words, an efficient stabilization policy lowers the unpredictable part of price variations. We want to test here the assumption that for a policy to be effectively able to remove price unpredictability, it 3 of 16 must be temporally consistent, i.e., the policy level must be appropriate to the price stabilization at each period of time. For instance, a tariff policy is not consistent per se in the objective of price stabilization. It is consistent if its level varies adequately with the objective of domestic price stabilization (a proportionate increase when world prices lower and a proportionate decrease when world price increases). To test the effect of policy consistency on the improvement of price predictability, we build an ARCH model adapted from [START_REF] Barrett | Liberalization and food price distributions : ARCH-M evidence from Madagascar[END_REF], where we introduce policy consistency as explanatory variables of price level and of price conditional variance.

The rest of the paper is organized as follows. In section 2, we present a literature review on the influence of pursued domestic policies on food price volatility. In section 3, we present the Kenyan case study and describe the ARCH model and the data used to test this model. In section 4, we present the results. A discussion follows on the policy recommendations that can be derived from these results.

The effects of State-led regulation on food price volatility (literature review)

Agricultural and food policies are among the many factors3 that are likely to influence food price volatility [START_REF] Abbott | Stabilisation policies in developing countries after the 2007-2008 food crisis[END_REF][START_REF] Gilbert | Food price volatility[END_REF][START_REF] Roache | What explains the rise in food price volatility?[END_REF]), but there is no consensus in the economic literature on the impact of policies pursued at national level on domestic food price volatility.

Price volatility definition and measure

The Organization for Economic Cooperation and Development defines price volatility as variations of such a frequency and scale that instead of constituting market signals to agents, they exceed agents capacity to adapt .

A common indicator to measure price variations is the coefficient of variation, which corresponds to the unconditional variance. However, agents capacity to adapt to price depends on their capacity to predict prices. Indeed, some part of price variations is predictable (for example, seasonal price variations), and necessary for the functioning of markets. To take into account these predictable factors, conditional variance indicators have been developed (price forecast models). In this paper, we define price volatility as the unanticipated component of price instability, i.e., the conditional variance, while instability could be defined as the unconditional variance in food prices over a time period, as summarized in table 1 [START_REF] Chapoto | The impacts of trade barriers and market interventions on maize price predictability : Evidence from Eastern and Southern Africa[END_REF] The effect of economic reforms on food price volatility

Most of the analysis on food price volatility deal with international markets, and as a result relatively little information is available on domestic markets. However, domestic food prices can differ substantially from international prices because of localized production shocks, transport and transaction costs, and because of the insulating effect of trade and marketing policies. So far, the literature has not reached a consensus on the effects of policy on food price volatility. Over the past twenty years, several authors have considered the relationship between agricultural liberalization reforms and food price volatility, with different results. We build our model upon the seminal empirical works of Barrett and Shively in the late nineties, which have been considering the effect of liberalization policies on food price volatility [START_REF] Shively | Food price variability and economic reform: An ARCH approach for Ghana[END_REF][START_REF] Barrett | Liberalization and food price distributions : ARCH-M evidence from Madagascar[END_REF]. Some empirical findings indicate that liberalization has caused an increase in cereals price volatility [START_REF] Barrett | Liberalization and food price distributions : ARCH-M evidence from Madagascar[END_REF][START_REF] Region | Agricultural liberalization policy and commodity price volatility: a GARCH application[END_REF], while other findings stand that market-oriented measures tend to reduce cereals price volatility [START_REF] Crain | Volatility in wheat spot and future markets, 1950-1993: government farm programs, seasonality, and causality[END_REF][START_REF] Shively | Food price variability and economic reform: An ARCH approach for Ghana[END_REF]. Now, considering the recent renewal of policies to deal with food price volatility in the context of food crisis, we didn t find studies addressing their effect.

This could be related to a short delay between food crisis, policy responses and the present time. This paper is motivated by the absence of any clear relationship between the recent renewal of public intervention to cope with food price volatility and the evolution of food price distributions in developing countries.

Low policy consistency may entail policy ability to lower food price volatility

A growing literature on price stabilization policies deals with the concrete mechanisms through which policies are implemented. Part of this literature points out that the capacity of public intervention to regulate food price volatility may be entailed by governance problems [START_REF] Poulton | State intervention for food price stabilisation in Africa : Can it work?[END_REF], governance failures [START_REF] Tschirley | sectors: Market failures or governance failures?[END_REF] or coordination failures [START_REF] Dorward | Beyond liberalization : "Developmental coordination" policies for african smallholder agriculture[END_REF].

Seminal empirical studies have demonstrated that, in a context of prices leap, a public intervention aimed at containing the price surge could indeed result in having no effect on it (Galtier 2010), or worse, in an aggravation of it (Nijhoff, [START_REF] Mwanaumo | Zambia's 2005 maize import and marketing experience: lessons and implications[END_REF][START_REF] Mwanaumo | Zambia's 2005 maize import and marketing experience: lessons and implications[END_REF][START_REF] Chapoto | The impacts of trade barriers and market interventions on maize price predictability : Evidence from Eastern and Southern Africa[END_REF]. These inefficiencies can be due to:

announce a food stabilization policy but fail to effectively implement it, because of (i) deficient enforcement control and/or (ii) low financial capacities. Examples from Western Africa are given below. These low effectiveness problems are more likely to occur in low income countries because of reduced financial means allocated to regulation policies and dependence from international donors, and in landlocked countries because of practical difficulties to control borders. On the contrary, countries with specific financial means (as it is the case in Zambia with copper revenues) and island countries or countries presenting relatively few land frontiers are less exposed to the mentioned problems of deficient enforcement control and low financial capacities. The problem of low financial capacities is crucial in the case of public stockholding that requires important specific funds to effectively lower food price spikes. In the case of Mali, the government implemented a buffer stock in 2004, called the Stock d Intervention de l Etat, but because of deficient financial resources, this stock was too narrow to effectively lower food price raises in 2005 and 2008. The problem of deficient enforcement control is crucial both in the case of trade control and marketing policies. In the case of Mali, the government implemented export restrictions in 2008, but this measure did not succeed in containing price raises as it was impossible for the state to physically control the frontiers (illegal exports occurred). This problem of deficient control has been mentioned for marketing policies as well, as in the example of Zambia in 2001 where consumer subsidies, allocated to specific millers, were not passed through to consumers.

-(ii) A lack of policy predictability. When governments intervene in a discretionary and unpredictable way, the private sector cannot correctly anticipate government actions and may decide not to operate in food markets (crowing out effect). The behavioral interactions between the state and private sector in an environment of policy uncertainty has the potential These analyses, applied to prices stabilization policies, are consistent with more general analyses on governance forms that prevail in the elaboration and implementation of policies and that insist on the capacity of diverse players (government, private actors ) to satisfy their objectives [START_REF] Kaufmann | The Worldwide Governance Indicators: Methodology and Analytical Issues[END_REF]). The World Bank has developed governance indicators to evaluate the capacity of the government to effectively formulate and implement sound policies (Kaufmann, Kraay et al. 2010, p4). Somewhat summarized, these works suggest that the precise policies may be less important than the fact that they exist and that main stakeholders find them credible (Tschirley and Jayne 2010).

The other dimension we want to explore in this line is the temporal consistency in the use of the policy that makes prices more or less predictable. For instance, a tariff policy can increase or decrease domestic price volatility depending on the institutional capacity to ensure a counter cycling phasing of the tariff.

The regulation of maize market in Kenya (model and data)

Our aim is to test the influence of the recent renewal of public intervention on the distribution of food prices, focusing on the effectiveness and predictability of this intervention. The case of Kenya is particularly interesting as it is characterized by a long tradition of public intervention to regulate maize prices and still by the persistence of highly volatile maize prices. In the recent years, and especially starting from 2008, the country has been facing severe food insecurity problems.

Low predictability

Maize trade and marketing policies pursued in Kenya

Maize prices are a crucial social and political issue in Kenya, maize being the main staple food, accounting for 36% of total food caloric intake in the country [START_REF] Ariga | Staple food prices in Kenya. COMESA policy seminar "Variation in staple food prices : Causes, consequence, and policy options, Maputo[END_REF]. Besides being the main staple food, maize is also the most common crop grown by rural poor households [START_REF] Nyoro | Evolution of Kenya s Maize Marketing Systems in the Post Liberalization Era[END_REF]). The Kenyan government has been intervening extensively in maize markets through trade and marketing policies, even during the so-called liberalization period, and has reinforced its intervention in the last ten years.

Trade policies

Except in good harvest years, Kenya requires substantial maize imports. These imports, mainly coming from Uganda and Tanzania accounted for more than 10% of domestic consumption in the last ten years (WorldBank 2009). Government imposed tariffs on maize imports from 1994, but these

tariffs have fluctuated since then, as it is represented in Figure 2. Imports from countries that are not part of either the East African Community or the Common Market for Eastern and Southern Africa are typically taxed at the rate of 50%, but this tariff can be waived and re-imposed without prior notification and is a source of major uncertainty for market participants. If the tariff rate is waived unexpectedly, local prices could quickly become higher than the cost of importing. While the tariff waiver normally triggers imports by the private sector, it can take many months before sufficient volumes are able to be move through a port and transport system with constrained supply capacities to push local prices back down to import parity [START_REF] Tschirley | sectors: Market failures or governance failures?[END_REF]. In addition to these tariffs, numerous non-tariff barriers to regional trade remain, as food quality and safety standard certificates [START_REF] Ariga | Staple food prices in Kenya. COMESA policy seminar "Variation in staple food prices : Causes, consequence, and policy options, Maputo[END_REF]. Indeed, prices seem to be characterized by lower amplitude variations in the recent period that corresponds to reinforcement of maize marketing and trade policies. We calculated the coefficients of variation corresponding to the period 1994-1999 and to the period 2000-2009. This choice has been motivated by the fact that 2000 corresponds to a reinforcement of both maize marketing and trade policies. It appears that prices are more stable in the 2000-2009 period (CV = 19%) than in the 1994-1999 period (CV = 24%). However, if the coefficient of variation is a meaningful measure of price variations, we saw that it does not account for the predictable component of volatility.

An ARCH modelization of food price distributions in Kenya

ARCH models are used to characterize and model observed time series [START_REF] Engle | Autoregressive Conditional Heteroscedasticity with Estimates of the Variance of United Kingdom Inflation[END_REF]. ARCH modeling allows simultaneous estimation of temporal variation in the conditional mean and variance of a dependent variable, which is in our case the deflated maize price. The analysis of the error term of the mean equation at any time t can provide useful information when one wants to interpret price predictability. In particular, the conditional variance of the error term of the mean equation is rarely homoscedastic, and this variance can be interpreted as a measure of price unpredictability: this is basically what has been done by Shively and Barrett who wanted to assess the impact of policy reforms on price volatility [START_REF] Shively | Food price variability and economic reform: An ARCH approach for Ghana[END_REF][START_REF] Barrett | Liberalization and food price distributions : ARCH-M evidence from Madagascar[END_REF]. Therefore, significant explanatory variables of conditional variance are valuable explanatory factors of price unpredictability. This price unpredictability is not exactly synonymous with volatility; it captures the unpredictable component of price volatility as measured by the squared difference between the actual price and the predicted price 10 of 16 from a model using a given set of explanatory variables known by most market participants at the time that the prediction is made.

The ARCH model general structure is as follows.

it it s k k t i k it X p p            ' 1 , 0 ) , 0 ( it it h iid  (1) it it q k k t i k r k k it k it X p h                  ' 1 , 1 2 0 (2)
Where the subscripts i and t stand for region and monthly period respectively. Equation ( 1) is the mean equation, that determines the maize price p it process as an autoregressive process of s periods, and a vector X it of exogenous variables explaining the level of maize price. A least square estimation of such a process generates a heteroscedastic error term and biased estimates. Equation ( 2) determines the conditional variance of the error term of equation ( 1), as an autoregressive process of q periods, by past prices, and by the same vector of exogenous variables explaining price unpredictability, X it . The observed price for a month is a linear function of a constant, the lagged month s price, a monthly time trend, the real exchange rate, the international price, maize buffer stock release, and a seasonal dummy variable.

Data

Many factors are likely to influence food price volatility. Basically, food price volatility is related to supply and demands fundamentals, which are likely to include market-specific and broader economic factors [START_REF] Roache | What explains the rise in food price volatility?[END_REF], and changes in these factors may have large effects because the short run supply and demand elasticities of food prices are typically low [START_REF] Balcombe | The nature and determinants of volatility in agricultural prices: An empirical study from 1962[END_REF]. The following factors are taken into account in our analysis, and correspond to the ones included in Barrett s model specification [START_REF] Barrett | Liberalization and food price distributions : ARCH-M evidence from Madagascar[END_REF]).

Past prices. There are periods of relatively high and low price volatility, though the underlying unconditional volatility remains unchanged. This principle underlines the choice of an ARCH model.

Nominal data were deflated by Kenyan consumer price index to construct real price series for maize from January 1994 to December 2009.

Inflation. Inflation has an obvious direct effect on food price volatility: to account for this effect, we have been working on consumer price index deflated price series.

Stock levels. Stocks have an important role in theoretical models of commodity pricing [START_REF] Williams | Storage and commodity markets[END_REF][START_REF] Deaton | On the behaviour of commodity prices[END_REF]. In theory, when stocks are low, volatility is expected to increase; empirical evidence, so far, has been mixed. To account for this potential effect, we used data of the United State Department of Agriculture (USDA PSD database) to include stocks levels in our model.

Exchange rate. Volatile exchange rates are likely to induce a higher volatility in food prices, as the riskiness of returns increases [START_REF] Balcombe | The nature and determinants of volatility in agricultural prices: An empirical study from 1962[END_REF]. Exchange rate data, obtained from the Kenyan Bureau of Statistics, are included in the first step of our model. International price. International price was calculated as prevailing international market prices, extracted from the database of United Nations Conference on Trade and Development (UNCTAD) converted into KSH at the nominal exchange rate and then deflated by Kenyan CPI.

Other economic factors that potentially influence food price volatility were not included because of lack of data or redundant information, such as weather patterns5 , oil price volatility6 , and speculation7 .

Added to these common economic factors that constitute the heart of Barrett s model specification, we integrate in our model one additional institutional factors reflecting policy inconsistency. We approximate policy inconsistency by the dynamic analysis of import tariffs policies in Kenya related to international prices. Two proxies are tested: instantaneous inconsistency and temporal inconsistency.

INST_INCONS is a dummy that equals one for the event of simultaneously high international price (higher than its average) and high tariff (higher than its average) or of simultaneously low world prices and low tariff. In these events, policy is inconsistent with the objective of removing effects of world price instability. In all other cases, INST_INCONS equals zero; TEMP_INCONS is a dummy that equals one at time t if the moving average of the world price has been increasing for 6 months before t, and if the tariff has not been decreasing between t-1 and t or, conversely, if the moving average of the world price has been decreasing for the last 6 periods of time before t, and if the tariff has not been increasing between t-1 and t.

The variables description is summarized in table 2.

Empirical model specification

Above data have been collected in 6 areas in Kenya, and we thus have 6 time series for price. We introduce a dummy variable for each of these areas (but one to avoid multicollinearity), both in mean and variance. We also introduce a dummy variable for the post-harvest season to capture seasonal regularities in prices and in price unpredictability. We also introduce a monthly trend in both processes. The level of stock at the beginning of each year (STOCK) is also an explanatory factor both for the price level (with a negative effect expected) and for price unpredictability (with a negative effect expected). Mean and conditional variance specific variables are international price level (IP), the yearly exchange rate (ER), the level of stock (STOCK), and the policy inconsistency (INCONS) taking the value INST_INCONS or TEMP_INCONS.

                        6 1 3 3 5 4 3 2 1 1 1 0 (3) it r r r t t t t t it it it R S INCONS TREND STOCK ER IP p h                            6 1 3 3 5 4 3 2 1 1 2 1 1 0 . (4)
Positive coefficient for UNPREDI,  5 >0, means that the tariff policy unpredictability tends to favour more volatile prices.

Results

Results from the ARCH model estimates from maximum likelihood estimation are found in Table 3.

The mean equation shows that the maize price is an autoregressive process with a strong monthly autocorrelation. In average, maize price in Kenya appears significantly decreasing. There is no significant effect of international prices on price level. As expected, the exchange rate tends to increase domestic price, and the level of stock has a significant decreasing effect on price level. Highly significant seasonal effects are as expected, and correspond to post-harvest times. These results are consistent with Sively (1996) and [START_REF] Barrett | Liberalization and food price distributions : ARCH-M evidence from Madagascar[END_REF]. Regarding the analysis of the conditional variance, the most interesting result is the highly significant positive effect of tariff policy inconsistency, showing that unpredictable policies tend to generate more volatile prices. It might appear unsurprising that policy inconsistency increase price volatility but the contribution is essentially empirical. It draws the attention on the fact that a policy instrument like variable tariff is not per se a stabilizing policy. Only when it is used with temporal consistency is it an efficient policy for stabilization. Stocks and policy effectiveness do not appear to have a significant effect on food price volatility. We do not have convincing explanation for the absence of any significant effect of stock on food price volatility. This finding stands in contrast with Jayne, Myers and Nyoro s observations that NCPB activities have stabilized maize prices in Kenya [START_REF] Jayne | The effects of NCPB marketing policies on maize market prices in Kenya[END_REF]) and with Barrett results [START_REF] Barrett | Liberalization and food price distributions : ARCH-M evidence from Madagascar[END_REF]). It could be interpreted in another way: it may be less the choice of the policy (public storage) than the fact that this policy is implemented in a transparent way that matters. Indeed, the structural effect of institutions (policy unpredictability) has a potentially greater role than short term environment, including stock level. The absence of significant effect of policy effectiveness may be related to the proxy used in this paper: this proxy, extracted from the World Governance Indicators database, is not specific to maize price policies implemented in Kenya, and encompass a rather large set of policies (to better address institutional factors, our paper may benefit from a fieldwork research in Kenya).

Conclusion

In the last twenty years, the debate has shifted from whether State led regulation is better than market led regulation, to one in which the major issues concern the way in which state and market can be integrated to provide the most effective coordination [START_REF] Dorward | Beyond liberalization : "Developmental coordination" policies for african smallholder agriculture[END_REF]. Drawing from the Kenyan case, we found that a low predictability of policies could reduce the capacity of these policies to lower food price volatility. Policy inconsistency is likely to be even more prevalent in the context of fragile states. The fact that these factors may influence policy results does not mean that no public intervention is needed to manage food price volatility but rather, that government actions should be as rule-based and transparent as possible [START_REF] Poulton | State intervention for food price stabilisation in Africa : Can it work?[END_REF]), or at least based on transparent advance consultation between the state and the private sector over future policy actions. In the current context of price swings, governments may be tempted to implemented policies that were successful in tackling food price volatility in other contexts. Our results indicate that « context matters » and suggest to care together about the nature of the policy tool and the institutional conditions of its enforcement.

Our results appeal for a better integration of governance issues in the analysis of food prices stabilization policies, and some important research questions arise. How to reinforce policy predictability and policy effectiveness? How to design institutions that engender greater trust between public and private actors? Empirical policy analysis set out that concertation between different stakeholders could facilitate policy credibility [START_REF] David-Benz | Les politiques de stabilisation des prix du riz à Madagascar[END_REF]. The implementation of consultative processes involving a broad range of stakeholders should be recommended, even if the policies emerging from such a process are not likely to approximate first best recommendations (Tschirley and Jayne 2010).

  to exacerbate price instability by leading to actions (or inaction) by one set of market actors that was not anticipated by the other[START_REF] Byerlee | Managing food price risks and instability in a liberalizing market environment : Overview and policy options[END_REF][START_REF] Tschirley | sectors: Market failures or governance failures?[END_REF]. In such a situation, public intervention may produce unanticipated consequences, such as crowding out private trade or imports that otherwise might have occurred, or were indeed expected by the government. Many examples from Eastern Africa countries are given in the Food Security Research Project. This is summarized in figure1.

Figure 1 .

 1 Figure 1. Policy predictability: The examples ofZambia (2001Zambia ( ,2002)),Malawi (2005) and Kenya(2008)

Figure 2 .

 2 Figure 2. Maize import tariffs at Mombasa Port (from Kenyan Ministry of Trade and industry)

Figure 3 .Figure 4 .

 34 Figure 3. NCPB maize purchases (MT) (from (Ariga, Jayne et al. 2010))

Table 2 .

 2 Explanatory variables used

	Variable name		Variable description	Sources
	lagged prices		Nairobi maize wholesale	Bureau of Statistics (CPI),	Ministry of
			real prices (ZMK/kg)	Agriculture (nominal prices)
	Stock levels (STOCK) Annual stock level (MT)	USDA PSD database
	Exchange rate (ER)	ZMK/USD	Bureau of Statistics
	International	price	Maize real international	US Bureau of Labor Statistics (US CPI),
	(IP)		price (USD/kg)	UNCTAD (nominal prices)
	Policy inconsistency	Import tariffs variability	Calculations from Ministry of Trade and
	(INST_INCONS and		Industry data
	TEMP_INCONS)

Table 3 .

 3 Estimates of ARCH model

		Instantaneous inconsistency	Temporal Inconsistency
		Mean	Conditional	Mean	Conditional
			variance		variance
	Constant	-0.003	0,007	0,053	1,05 E-8
		(-0,07)	(1,36)	(1,3)	(0)
	Lagged price	0.90	0,0099	0,014	0,018
		(63,36)	(6,63)	(64,7)	(8,0)
	International	0,03	-5,8 E-22	0,055	-1,7 E-20
	price	(1,64)	(0)	(2,76)	(0)
	Exchange rate	0,002	9,7 E-24	0,0019	0,0001
		(3,34)	(0)	(3,18)	(2,48)
	Stock	-0,000097	6,4 E-9	-0,00014	-1,39 E-24
		(-2,75)	(0)	(-4,01)	(0)
	Trend	-0,000035	2,5 E-9	0,00017	-7,7 E-23
		(-0,15)	(0)	(0,79)	(0)
	INST_INCONS	-0.004	0,003	-	-
		(-0,49)	(3,63)
	TEM_PINCONS	-	-	-0,029	0,0029
				(-3,34)	(3,39)
	Post harvest	-0,038	0,0008	-0,04	0,0009
	dummy	(-4,47)	(0,87)	(-5,32)	(1,05)
	Region Kit	0,001	0,0026	0,006	0 ,003
		(0,11)	(2,21)	(0,54)	(2,81)
	Region NAi	0,0006	-9,97 E-23	0,006	1,06 E-22
		(0,05)	(0)	(0,53)	(0)
	Region Kis	-0,0008	-5,1 E21	0,002	4,88 E-22
		-0,06)	(0)	(0,21)	(0)
	Region Mom	-0,001	8,7 E-24	0,005	-4,4 E-24
		(-0,08)	(0)	(0,43)	(0)
	Region Eld	-0,004	0,0005	0,00001	0,00014
		(0,01)	(0,48)	(0)	(0,14)
	ARCH1		0,10		0,12
			(2,39)		(2,8)
		N=912		N=912
		R²=0,87		R²=0,88
	t value in parentheses

These negative effects are likely to be more important in African countries, where markets are spatially segmented and where food expenditures account for most of household expenditures.

In this case, the State role would be limited to the promotion of a regulatory framework and to investments in public goods.

Some of these factors enter our model (see section3, presentation of the data used)

Researchers have often resorted to compare price coefficient of variation across different periods characterized by varying policy regimes, but in our literature review we will only consider analyses that have been made with conditional estimates of price sensitivity.

Extreme weather events (drought, floods) are directly affecting agricultural productivity (Haile 2005). Thus, these events are one important source of food price volatility and extreme climate indices are used to analyze the impact of climate volatility on poverty (Ahmed et al 2009).

Recent empirical work has suggested a transmission of prices between oil and food prices, trough the channel of fertilizer prices, mechanized agriculture and freight costs[START_REF] Balcombe | The nature and determinants of volatility in agricultural prices: An empirical study from 1962[END_REF]. To account for this effect, some authors introduce the US CPI deflated petroleum spot price (International Monetary Fund data).

The impact of speculation on food price volatility is a controversial debate[START_REF] Roache | What explains the rise in food price volatility?[END_REF].[START_REF] Roache | What explains the rise in food price volatility?[END_REF]. What explains the rise in food price volatility? . I. W. P. WP/10/129, International Monetary Fund.[START_REF] Roache | What explains the rise in food price volatility?[END_REF]. What explains the rise in food price volatility? . I. W. P. WP/10/129, International Monetary Fund.