{'fraction_non_alphanumeric': 0.04773275884444675, 'fraction_numerical': 0.019466867391699328, 'mean_word_length': 4.0094916135743075, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Hyperbolic grids and discrete random graphs

We present an efficient algorithm for computing distances in hyperbolic grids. We apply this algorithm to work efficiently with a discrete variant of the hyperbolic random graph model. This model is gaining popularity in the analysis of scale-free networks, which are ubiquitous in many fields, from social network analysis to biology. We present experimental results conducted on real world networks.


Introduction
Hyperbolic geometry has been discovered by 19th century mathematicians wondering about the nature of parallel lines. One of the properties of this geometry is that the amount of area in distance d from a given point is exponential in d; intuitively, the metric structure of the hyperbolic plane is similar to that of an infinite binary tree, except that each vertex is additionally connected to two adjacent vertices on the same level. Anyone who has tried to draw a full binary tree of height 10 knows that there is not enough space in the Euclidean space; exponential expansion typical to hyperbolic geometry has found applications in visualization of hierarchical data [16,19]. Figure 1 shows two tilings of the hyperbolic plane, the order-3 heptagonal tiling and the truncated triangular tiling, in the Poincaré disk model, together with their dual graphs, which we call G 7 and G 67 . In the Poincaré model, the hyperbolic plane is represented as a disk. In the hyperbolic metric, all the triangles, heptagons and hexagons on each of these pictures are actually of the same size, and the points on the boundary of the disk are infinitely far from the center.
Recently, hyperbolic geometry has found application in the analysis of scalefree networks, which are ubiquitous in many fields, from network analysis to biology. [22]. In the hyperbolic random graph (HRG) model, each vertex is randomly assigned a point in the hyperbolic plane (according to some distribution), and then, we connect each pair of vertices with probability depending on the distance between the two points. HRGs turn out to have properties similar to that of scale-free networks. Efficient algorithms have been found for generating HRGs in time O(n) [3] and for MLE embedding real world scale-free networks into the hyperbolic plane in timeÕ(n) [2], which was a major improvement over previous algorithms [21,24].
In this paper, we present efficient algorithms for calculating distances in hyperbolic triangular grids, such as G 67 and G 7 from Figure 1. Our algorithm can be applied to work efficiently with discrete analogs of HRGs, which we call DHRGs, allowing us to compute the log-likelihood of an embedding in time and memory O(nD 2 ), where D is the radius of the grid and can be seen as logarithmic; this is a very important step for MLE embedders. Furthermore, it is possible to dynamically remap a vertex v to another location and compute the log-likelihood of the new embeddding in time O(D 2 + D deg(v)), which yields an efficient local search algorithm to improve the embedding -which might be useful on its own [4]. We can also generate DHRGs in time O(nD 2 + mD). This matches the time and complexity of the best continuous algorithms listed in the previous section up to D O(1) factors.
We believe that such grid-based approach is interesting for the following reasons: Continuity is not essential in the HRG model. For example, the Facebook graph from [2] has 4000 vertices, with typical distances between pairs of vertices connected by an edge are around 10 absolute units, which corresponds to roughly 18 steps in grid G 67 . Thus, moving each point towards the nearest grid point does not significantly affect the distances between points.
Approachability. By avoiding continuous computations, our model is potentially more approachable to theoretical computer scientists who are more focused on discrete problems.
Simplicity. It is worth to note that the major breakthrough in [3] and [2] was achieved by using geometric structures based on partitioning hyperbolic disks into cells. This is in some sense similar to our grids. However, we believe that our approach is more elegant and simpler.
Hyperbolic grids have other applications. Regular grids in the hyperbolic plane have many applications, such as self-organizing maps [20] or game design [14]; in particular, we recommend playing our game HyperRogue as an intuitive introduction to hyperbolic grids and hyperbolic geometry in general. Hyperbolic grids arise naturally when working with bounded degree planar graphs; for example, many constructions in [9] are based on hyperbolic grids.
Precision errors. Radial coordinates as used in [2,12,22] are prone to precision errors. This is unavoidable in any typical coordinate system because of the exponential nature of hyperbolic geometry. Indeed, the circumference of a hyperbolic circle of radius r in 2π sinh(r) = Θ(e r ). Therefore, if we are using b bits for the angular coordinate, two points on the circle of radius b/ log(2)+Θ(1) will be smashed into a single point, even if their exact distance is greater than 1. On the other hand, vertices in grids can be represented with paths from some specific "origin" vertex, thus avoiding these problems. Even if we are working with the continuous hyperbolic plane, a "hybrid" approach where each point is represented by a vertex of our grid together with the coordinates relative to that vertex. Such approach is used in HyperRogue [25].
Visualizations. We can visualize a graph by mapping each of its vertices to a distinct vertex of our grid. Since the vertices in our grids are spaced regularly, this allows for aesthetically pleasant representations of graphs [6].
Hyperbolic grids are interesting on their own. It is well known that many algorithmic problems can be easily solved on trees; it is also well known that many graph problems admit very efficient algorithms on graphs that are similar to a tree, where similarity is most commonly measured using the notion of tree width [23]. For example, every fixed graph property definable in the monadic second order logic with quantification over sets of vertices and edges (M SO 2 ) can be checked in linear time on graphs of fixed tree width [8]. Hyperbolic metrics are very tree-like -however, tree width might be not the best measure of this, as the tree width of a neighborhood of radius r in our grids is linear in r rather than constant; while this is small (logarithmic in the size of the graph), it is not a constant. Other metrics, such as the Gromov hyperbolicity [1], which is constant, or the tree length [7], which is provably O(δ log n) on graphs with n vertices and Gromov hyperbolicity δ [7], might be more appropriate.
In the next section we present the general definition of the hyperbolic triangular grid we will be working with, and some basic facts about such grids. In section 3 we focus on grids whose structure is regular. In Section 4 we introduce our algorithms calculating distances in the grid. In Section 5 we study how the distances in our grids are related to distances in the underlying hyperbolic plane. In Section 6 we recall the definition of the HRG model, and define our own DHRG model, based on the intuitions from Section 5. We analyze the DHRG model in Section 7, then show how to apply our algorithms to work with DHRGs efficiently in Section 8. We have implemented some of the algorithms presented in Sections 4 and 6; the experimental results regarding the DHRG model are presented in Section 9. We discuss possible directions for further work in Section 10.

Hyperbolic triangular grids
In this paper by δ(v, w) we denote the distance between v and w; in case if v and w are vertices of the graph it is the length of the shortest path between v and w, and if they are points in the hyperbolic plane, it is their hyperbolic distance.
is an infinite planar graph such that every face is a triangle, We assume that all the rings R k (G) are oriented clockwise around v 0 . Thus, the i-th successor of v, denoted v + i, is the vertex obtained by starting from v and going i vertices on the cycle. The i-th predecessor of v, denoted v − i, is obtained by going i vertices backwards on the cycle. A segment is the set S = {v, v + 1, . . . , v + k} R k (G) for some v ∈ V and k ≥ 0; v is called the leftmost element of S, and v + k is called the rightmost element of S. By [v, w] we denote the segment such that v is its leftmost element, and w is its We use tree-like terminology for connecting the rings. A vertex w is a parent of v if {v, w} ∈ E and δ 0 (v) = δ 0 (w) + 1; in this case, v is a child of w. Let P (v) be the set of parents of v ∈ R k (G); it forms a segment of R k−1 (G), and its leftmost and rightmost elements are called the left parent p L (v) and the right parent p R (v) respectively. The set of children C(v), leftmost child c L (v) and rightmost child c R (v) are defined analogously. Figure 2: Grid G 67 with labeled vertices, in two perspectives. Figure 2 presents the grid G 67 with named vertices. Both pictures use the Poincaré disk model, but the left picture is centered roughly at v 0 (labeled with A in the picture), and the right picture is centered at a different location in the hyperbolic plane. Points drawn close to the boundary of the Poincaré disk are further away from each other than they appear -for example, vertices T and U appear very close in the left picture, yet in fact all the edges are roughly of the same length (in fact, there are two lengths -the distance between two vertices of degree 6 is slightly different than the distance between a vertex of degree 6 and a vertex of degree 7).
Vertices X, Y , and Z are the children of T ; its siblings are S and U , and its parents are O and P . The values of P k ([Y ]) for consecutive values of k, i.e., the ancestor segments of Y , are:  • every vertex has at most two parents and at least two children, Both grids G 67 and G 7 are hyperbolic. Probably the simplest, though geometrically less regular, example of a hyperbolic triangular grid is obtained by taking a full infinite binary tree, and additionally connecting each vertex to its cyclic left and right sibling, and additionally the right child of its left sibling.
From the definition of the hyperbolic triangular grid, |C(S i )| ≥ t + 2. The segments C(S i ) need not be disjoint, but the only case when they are not disjoint is that the rightmost element of C(S i ) equals the leftmost element of C(S i+1 ). Hence, | C(S i )| ≥ at + a + 1.
Proof. Should be similar. Not written yet.

Uniform hyperbolic grids
Triangular grids as defined in the previous section did not necessarily have any regular structure. In this section we define uniform triangular grids; their structure allows us both to efficiently handle them algorithmically, and to obtain combinatorial results. By T * we denote the set of all words over an alphabet T . A function c : T → T * can be naturally extended to a homomorphism, which we also denote with c : T * → T * . Let #(w) : T → N be the vector counting the number of occurences of each letter in w ∈ T * . It is easy to see that #(cw) = C#(w) for some matrix C. Since we already Definition 3.1. We say that a triangular grid G is uniform iff there exists a finite set of types T , a function c : T → T * , and an assignment t : V (G) → T of types to vertices, such that for each v ∈ V (G), the sequence of types of all children of v from left to right except the rightmost child is given by c(t(v)). Furthermore, there is a density function g : T → R such that, for each t, u ∈ T , lim n→∞ # u c n (t) = g(u).
For example, in the grid G 7 , we take T = {0, 1, 2}, where t(v) is the number of parents of v. The root has no parents, and has seven children of type 1. A vertex of type 1 has the leftmost child of type 2, followed by two children of type 1. A vertex of type 2 has the leftmost child of type 2, followed by a child of type 1.
The situation is more complicated in the grid G 67 . We have 7 types, with t(v) depending on: the degree of v, the number of parents of v, and the degree of the left sibling of v. Given that each vertex of degree 7 has 7 neighbors of degree 6, and the neighbors of vertices of degree 6 alternate between degree 6 and 7, we can compute the sequence of types of children for each of the 7 types. Proposition 3.2. In a uniform hyperbolic triangular grid G, for each v ∈ G, |C k (v)| = Θ(γ k ) for some γ, where γ depends only on G.
Proof. It is easy to see that |C k (G)| = |c k (t(v))| + 1, and #(cw) = C#(w) for some matrix C. Since we already have an exponential lower bound from 2.5, our result now can be obtained easily using well known properties of matrix exponentiation. The existence of the density function g ensures that γ does not depend on t(v).
We have γ ≈ 2.6180339 for G 7 and γ ≈ 1.72208 for G 67 [14]. It is not feasible to represent all vertices in, say, B 100 (G 67 ) in computer memory -there are more than 10 23 of them! However, we can generate the vertices in our uniform triangular grid lazily. that is, represent our vertices with pointers, start from the root, and generate other vertices when asked for them. In particular, each vertex v is represented with a pointer to a structure which contains δ 0 (v), the type of v, the pointers to , and the index of v among the children of p R (v); the last three pointers are NULL if the given neighbor has not yet been computed. Such a structure allows us to compute all the neighbors of the given vertex in amortized time O(1) for a fixed grid. This is similar to the approach used in [18] and [25] for G 7 (though in [25] a different algorithm is used for G 67 , based on subdividing G 7 rather than working with the rings in G 67 directly).

Computing distances in hyperbolic grids
In this section we show how to compute distances in the hyperbolic grid, based on the data structure outlined in the previous section.
for a hyperbolic triangular grid G, and δ(v, w) = d. Then at least one of the following is true: In other words, the shortest path between any pair of two vertices (v, w) can always be obtained by going some number of steps toward v 0 , moving along the ring, and going back away from v 0 . The cases where one of the vertices is an ancestor of the other one had to be listed separatedly because it is possible that |P a (v)| > 2 for a > 1, thus w might be neither the leftmost not the rightmost ancestor.
Such a situation happens in the grid G 67 for the pair of vertices labeled (J, O) in Figure 2, even though |P a (v)| ≤ 3 always holds. Let's analyze the grid G 67 in more detail. Take vertices v and v + k, where k ≥ 0 and δ 0 (v) = d. The distance δ(v, v + k) could be k, or it could be achieved by an inner path, i.e., one that goes through B d−1 ; denote the length of the shortest inner path by g. V and V + 3 are both children of R), but it is also possible that p R (v d ) − p L (v d+2 ) = 2 (as happens for U and W in Figure 2). The situation is similar, though a bit simpler, in the grid G 7 . These observations allow us to create an efficient algorithm computing distances between vertices of our grid, which can be generalized to any uniform hyperbolic triangular grid.
Proof of Proposition 4.1. Not written yet.
Proof. Our algorithm uses five integer variables a, c, d v , d w , d and four vertex variables v L , v R , w L , w R , satisfying the following invariant: • d is the upper bound on δ(v, w), more precisely, the length of the shortest path between v and w among those which are of the form from Proposition 4.1, and such that a and c from δ(v L , v 0 ) = δ(v R , v 0 ) = d v are smaller than our a and c.
While d v > d w , we push v down, i.e., set a := a + 1, v L := p L (v L ) and v R := p R (v R ). While d w > d v , we push w down, i.e., set c := c+1, w L := p L (w L ) and w R := p R (w R ). The invariant is still satisfied.
If a + c > d, we are sure that d is the correct value of δ(v, w), and thus we terminate the algorithm. Otherwise, we can check in , w is between v L and v R , or v is between w L and w R -if yes, this gives us a new upper bound on δ(v, w). However, it is still possible that a better path is to be found on one of the following levels, thus we push down both v and w. The invariant is still satisfied, and we repeat.
The algorithm runs in time O(δ(v, w)), because the values of both a and c in the optimal path are smaller than δ(v, w), and we do at most t 3 extra iterations after finding the optimal path.
Remark: with some preprocessing, we can optimize to O(log δ(v, w)) per query -precompute p a L (v) for each v ∈ V and a ∈ N, or for each a that is a power of two.
A distance tally counter for a graph G = (V, E) represents a function f : V → R with the following operations: • Initialize: f is initialized with the constant 0 function It is also possible to optimize either memory or Add time by a factor of δ 0 (v). In our applications δ 0 (v) is small, and thus could be considered to be logarithmic in the size of the graph.
Note that the algorithm from the proof of Proposition 4.2 can be seen as follows: we start with two segments [v, v] and [w, w], and then apply the operation P to each of them until we obtain good vertex pairs which are close. Our algorithm will optimize this by representing all the good vertex pairs coming from vertices v added to our structure.
A vertex or good segment is called active if it is represented in the memory of our algorithm. For each active vertex v ∈ V we keep two lists of active segments S such that v is respectively the leftmost and rightmost element of S. Each active segment S also has a pointer to P (S), which is also active (and thus, all the ancestors of S are active too), and a dynamic array of integers a(S). Initially, there are no active vertices or good vertex pairs; when we activate a segment S, its a(S) is initially filled with zeros.
The operation Tally(w) activates w and S = [w, w] together with all its ancestors. Then, we look at p a (S) for a = 0, . . . , δ 0 (v), and for each p d (S), we look at close good vertex pairs q on the same level. The intuition here is as follows: Algorithm 4.2, on reaching (v L , v R ) = S and (w L , w R ) = S , would find out that these two pairs are close enough and return a + b + c; in our case, for each c such that a(S ) = 0, we will instead add a(S )[c] to A[a + b + c]. Since Algorithm 4.2 stops in that situation and our a goes all the way down to δ 0 (v), we also have to make sure that we do not count vertices which have been already counted.
Remark. It easily follows from Proposition 4.1 that the uniform hyperbolic triangular grids are hyperbolic graphs in the sense of Gromov [1]. (Should follow -not formally checked yet.) Our algorithms could be seen as an algorithmic application of Gromov hyperbolicity.

Grid distances versus hyperbolic distances
We assume that our grid is mapped to the hyperbolic plane H 2 via a function j : V (G) → H 2 ; in case of G 67 and G 7 this mapping corresponds to the regular tesselation that these grids are based on; furthermore, j(v) is obtained by applying d = δ 0 (v) isometries to j(v 0 ), with i-th isometry depending only on the type of p d−i+1 R (v) and the index of p d−i R (v) among its children. Intuition 5.1. For v, w ∈ V (G), let d = δ(v, w), and r = δ(j(v), j(w)). Then d and r are approximately proportional.
Stating and proving this intuition formally appears to be challenging, as we have to deal both with the discrete structure of the triangular grid, and the continuous hyperbolic geometry. From the regularity of our tesselation we get that d = Θ(r); we cannot give a better estimate (e.g., d = αr + Θ(1)) because the density of rings depends on the direction. However, we can guess that, on average, r ≈ d log γ. This is because, in the hyperbolic plane, the area and circumference f a circle of radius r given in absolute units is given by cosh(r) − 1 and sinh(r) respectively, which are Θ(e r ); from Proposition 3.2 we know that this corresponds to Θ(γ d ) elements of the grid, yielding r ≈ d log γ after taking the logarithm of both sides.
We can also expect this approximation to be better than the corresponding Euclidean one. Consider the regular triangular grid G 6 on the Euclidean plane, in the standard embedding wher every edge has length 1. Let v = v 0 and W be a random vertex in R d (G 6 ). From basic geometry we obtain that r ∈ [ √ 3+1 2 d, d]. The standard deviation of r will be linear in d, because the ratio r/d depends on the angle between the line (v 0 , W ) and the grid lines. However, because of the exponential expansion in the hyperbolic plane, this angle constantly changes as the line (v 0 , W ) traverses the grid, leading to the following conjecture: Conjecture 5.2. Let G = G 67 or G 7 , and W ∈ R d (G) be randomly chosen. Then δ(j(v 0 ), j(W )) = c 1 d + c 0 + X, where EX = o(1), Var X = Θ(d), and the limit distribution of X/ √ d is normal.
The results of experimental verification agree with the conjecture both for G 67 and G 7 , although it appears that c 1 is slightly larger than log γ in both cases.

Hyperbolic random graphs
We start by presenting the hyperbolic random graph (HRG) model [2,12,15]. Then, we will use our intuitions from the previous section to define the discrete hyperbolic random graph model (DHRG).
Fix a radial coordinate system in the hyperbolic plane H 2 , where every point is represented by two coordinates (r, φ), where r is the distance from some fixed center, and φ is the angle. The hyperbolic random graph model has four parameters: n, R, T , and α. Each vertex v ∈ V (H) = {1, . . . , n} is independently randomly assigned a point µ(v) = (r v , φ v ), where the distribution of φ v is uniform in [0, 2π], and the density of the distribution of r v ∈ [0, R] is given by f (r) = α sinh(αr) cosh(αR)−1 . Then, for each pair of vertices v 1 , v 2 ∈ V (H), they are connected with probability p(δ(µ(v 1 ), µ(v 2 ))), where p(d) = 1 1+e (d−R)/2T . It is known that, for correctly chosen values of n, R, T and α, the parameters of hyperbolic random graph, such as its degree distribution and clustering coefficient, are similar to those of real world scale-free networks [12]. We can also embed real world scale-free networks into the hyperbolic plane using the maximum likelihood (MLE) method, that is, for a graph H representing a real world scale-free network we can find a mapping µ : V (H) → H 2 which predicts the edges as accurately as possible.
DHRG model. In our model, we map vertices v ∈ V (H) not to points in the continuous hyperbolic plane, but to the vertices of our uniform hyperbolic triangular grid G, i.e., µ : V (H) → V (G). The density function f (r) from the HRG model cannot be reproduced exactly, but we can use f (r) = αe αr /(e αr −1), which is a very good approximation (it only slightly changes the low probability of placing a vertex very close to the center). To approximate this in our grid, we choose m(v) such that δ 0 (m(v)) = d with probability proportional to e dα . The exact vertex µ(v) is then chosen uniformly from R d (G). The formula for edge probability remains the same, except that we are using the grid distance now.
DHRG mappings can be converted to HRG by composing µ with j, and the other conversion can be done by finding the nearest grid point to µ(v) for each v ∈ V (G). From Conjecture 5.2 we expect tha DHRG parameters α, R, T , and n to be related to the HRG parameters by the factor of log γ.

Properties of DHRGs
This section is not yet completed.
Conjecture 5.2 suggests that, if we take matching values of parameters, the DHRG and HRG should have similar properties; in particular, for DHRGs, the power law degree distribution, average degree, and clustering coefficient should behave similarly as for HRGs [12]. In this section we are going to prove this formally. We work with a DHRG with fixed parameters, over a fixed uniform hyperbolic triangular grid G.
(Should be relatively easy for regular trees. Our grids are more difficult for two reasons: first, vertices of different types have different number of children, and second, we can take shortcuts as stated in 4.1. However, these complications should not affect the results qualitatively. Experimental results on G 67 and G 7 should be helpful too.)

Algorithms for DHRG
We show how the algorithms from Section 4 allows us to deal with the DHRG model efficiently.
Computing the likelihood. Let H = (V (H), E(H)) be a network. The quality of an embedding m : V (H) → V (G) is measured with its likelihood, which describes how good the given embedding is at predicting whether two vertices are connected by an edge. The likelihood L(m) is the probability that, if we connect vertices with edges according to the model outlined above, we exactly obtain E(H); since this number is usually very small, we usually compute its logarithm, or log-likelihood. The log-likelihood can be computed with log Computing the log-likelihood in the continuous model is difficult, because we need to compute the sum over O(n 2 ) pairs; a better algorithm was crucial for efficient embedding of large real world scale-free networks [2]. The algorithms from the previous section allows us to compute it quite easily in the DHRG model. To compute the log-likelihood of our embedding of a network H with n vertices and m edges, such that δ 0 (v) ≤ D for each v ∈ V (H), we: • for each d, compute Tally[d], which is the number of pairs (v, w) such that δ(v, w) = d -the distance tally counter allows doing this in a straightforward way (simply by doing Add(µ(v), 1) for each v ∈ V (H)), in time O(nD 2 ).
• for each d, compute Edgetally[d], which is the number of pairs (v, w) connected by an edge such that δ(v, w) = d -this can be done in time O(mD) simply using the distance algorithm for each edge.
After computing these two values for each d, computing the log-likelihood is straightforward. One of the advantages over [2] is that we can then easily compute the log-likelihood obtained from other values of R and T , or from a function p(d) which is not necessarily logistic.
Improving the embedding. A continuous embedding can be improved by a spring embedder [13]. Imagine that there are attractive forces between connected pairs of vertices, and repulsive forces between unconnected pairs. The embedding m will change in time as the forces push the vertices towards locations in such a way that the quality of the embedding, measured by loglikelihood, is improved. However, computationally, spring embedders are very expensive -there are O(n 2 ) forces, and potentially, many steps of our simulation could be necessary.
A similar effect can be obtained quite easily in our grid-based model, and our algorithms allow us to do it efficiently. We use a local search algorithm. Suppose we have computed the log-likelihood, and on the way we have computed the vectors Tally and Edgetally, as well as the distance tally counter where every µ(v) has been added. Now, let v ∈ V (H) be a vertex of our embedding, and w ∈ V (G). Let µ be the new embedding given by µ (v ) = w and µ (v) = µ(v) for v = v . Our auxiliary data allows us then to compute the log-likelihood of µ in time O(D 2 + D deg(w)).
This allows us to try to improve the embedding in the following way: in each step, for each v ∈ V (G), consider all neighbors of µ(v), compute the log-likelihood for all of them, and if for some µ we have log L(µ ) > log L(µ), replace µ with µ . Assuming the bounded degree of G, this can be done in time O(D 2 n + Dm).
Our experiments have shown that the locally optimal mapping is achieved after a small number of steps.
Generating a random graph. Generating large HRGs is not trivial -a naive algorithm works in Θ(n 2 ); algorithms working in O((n 3/2 + m) log n) and O(n) [3,24] are known. Our algorithms allow to generate DHRGs quite easily in O(nD 2 + mD).
The first step is to generate the vertices. For each vertex v of the generated graph H, we choose d = δ 0 (v) (according to the given distribution), and then we have to randomly choose v from the |R d (v)| possibilities. This can be done iteratively: we create a sequence of vertices v 0 , . . . , v d , where v 0 is the root, and v k+1 is a non-rightmost child of v k . The probability of choosing the particular v as v k should be proportional to

Experimental results
We have implemented the log-likelihood and local search algorithms outlined in the previous section, and conducted experiments on real world network data. The implementation is based on the routines implemented for HyperRogue [25]. The source code, data, and experimental results are available at http://www. mimuw.edu.pl/~erykk/dhrg-v2.zip;here, we present a short summary of the results.
Facebook social circle network. First, we test our model on a relatively small network. We have chosen the Facebook social circle network, coming from the SNAP database [17] and included with the hyperbolic embedder implementing the algorithm by Bläsius et al [2], which we will refer to as BFKL. This network has N = 4039 nodes and M = 88234 edges. BFKL has mapped this graph to the hyperbolic plane, using parameters R = 12.576, α = 0.755, T = 0.1. We have computed the log-likelihood as L 1 = −516534. This looks extremely bad at first, as it is worse than the log-likelihood of the trivial model where each edge exists with probability M/ N 2 , which is L 0 = −487133; however, this is because the influence of the parameter T on the quality of the embedding is small [21], and thus BFKL uses a small value of T = 0.1, which does not necessarily correspond to the network. The best log-likelihood of L 2 = −176132 is obtained for R 2 = 11.09358 and T 2 = 0.54336. Now, we convert this embedding into the DHRG model, by finding the nearest vertex of G 67 for each v ∈ V (H). The best log-likelihood L 3 = 179125 is obtained for R 3 = 20.393945 and T 3 = 1.012944; As predicted in the previous section, T 2 /T 3 ≈ R 2 /R 3 ≈ log γ. Our log-likelihood L 3 is slightly worse than L 2 , but this is not surprising -first, our edge predictor has lost some precision in the input because of the discrete nature of our grid, and second, the original prediction was based on r while our prediction is based on d, and the ratio of r and d depends on the direction. We also compute the log-likelihood obtained by a model where the edge probability is p(d) = Edgetally[d]/Tally [d], which corresponds to using the best possible function p(d) (not necessarily logistic); we obtain L 4 = −177033, which is only slightly better than L 3 . This shows that the logistic function is close to the optimum. Now, we try our local search algorithm. The points stopped moving in the k-th iteration, for k = 24. This allows us to improve the log-likelihood of L 5 = −167808, again for the best values of R 5 = 20.837295 and T 5 = 0.966040, and the optimal log-likelihood to L 6 = −165154. Now, we convert our mapping back to the HRG model, obtaining the loglikelihood of L 7 = −168298 for the optimal values of R 7 = 11.25917 and T 7 = 0.52659. Note that L 7 is significantly better than L 2 ; hence, despite converting from HRG to DHRG and back, our method was successful at finding a better continuous embedding.
The running time of parts of our algorithm were: t 1 =0.24 s (converting), t 2 =0.3 s (computing Edgetally), t 3 =0.03 ms (computing Tally), t 4 =35 s (local search). The BFKL embedder computes the log-likelihood in 0.3 seconds, which is comparable. However, their spring embedder working in quadratic time is much slower than our local search. 1 We have also computed the log-likelihood of our vertex placement, assuming that a vertex is an element of R d (G) with probability q(d) = |r d (G) ∩ m(V (H))|/N , and that each element of R d (G) is equally probable. We obtain L 8 = −63787 for the placement after the local search. (Since our local search did not place an upper limit on δ 0 , we have decided to not compare against the probability function q(d) used by the DHRG model.) This is interesting from the information theoretic perspective: using arithmetic encoding, an event with probability p could be encoded with − log 2 p bits, and thus (L 6 +L 8 )/L 0 = 0.475 could be interpreted as the compression ratio achieved by representing the graph in our model; thus, our algorithm could be applied as a method of compression of scale-free networks. This has no direct analog in the continuous HRG model, since we have to choose the precision reported for the coordinates. Note that our implementation optimizes L 5 rather than L 6 + L 8 , so a better compression should be achievable.
The respective values obtained by the grid G 7 were: t 1 = 0.23s, t 2 = 0.2s, t 3 = 0.02s, k = 18, t 4 = 15s, L 3 = −181919, L 4 = −180201, L 5 = −169205, L 6 = −167048, L 7 = −170473, L 8 = −59147. G 7 is coarser than G 67 , hence it is 1 For T = 0.54336 and seed 123456789 the BFKL spring embedder reported the loglikelihood of -131634, which is better than ours; however, our implementation reports L 1 = −211454 and L 2 = −174465, which our local search still manages to improve to L 7 = −157026. This appears to to be a problem in their approximation (which also affects the fast embedder, and smaller values of T ). Indeed, replacing their optimized log-likelihood function with a Θ(n 2 ) one from hyperbolic.cpp reports log-likelihood equal to ours. [Actually, it reports double our result, but this seems to be caused by counting each pair of vertices twice, which is easy to fix and irrelevant for the optimized embedder.] not surprising that its results are slightly worse; also the smaller size and greater simplicity of the grid improves the running time. Yet, the general qualitative effects are similar. The compression ratio is slightly better at 0.469, suggesting that the coarser grid G 7 is slightly more efficient at compression.
GitHub following graph. To benchmark our algorithm on a large network, we study the embedding of a social network observed in GitHub repository hosting service. In GitHub convention following means that a registered user agreed to be sent notifications about other user's activity within the service. This relationship can be represented by the means of the graph of following G f . There is an edge in G f between A and B if and only if A follows B. Decision about following a particular user can be simultaneously driven by their popularity within the network and the similarity to the interested user, which suggests hyperbolic geometry can be intrinsic in development of G f . G f was also proved to show power-law-like scale behavior [5], that is why we believe it is a sound benchmark for our analysis. Since the complete download of GitHub data is impossible, our dataset is combined from two sources: GHTorrent project [10] and GitHubArchive project [11]. The analyzed network contains information about the following relationships that occurred in the service from 2008 to 2009. The graph has n=74946 vertices and m=537952 edges (since we are working with an undirected graph, an edge appears between A and B if either A follows B or B follows A). The BFKL embedder has chosen parameters R = 20.9037 and α = 0.855, and computes the log-likelihood in 5 seconds. The results for G 7 grid are as follows: t 1 = 6 s, t 2 = 12 s, t 3 = 2s, L 0 = −4364526, L 3 = −3972006, T 3 = 1.390037, R 3 = 9.180628, L 4 = −3855721. After 6 iterations of local search (27 minutes) the results have been improved to L 5 = −3542063, L 6 = −3520703, L 8 = −1997284. The time t 2 + t 3 is still comparable to BFKL. 2 The results are generally worse than in the previous graph, which is probably caused by less order in data (not all accounts correspond to real people, avoiding direction in a directed graph, non-random missing data patterns).
Unfortunately, parts of the current implementation of our algorithm were not designed for representing that large graphs, and thus are not memory efficient for our use -this prevents us from running more iterations of local search, or analyzing later years in GitHub. Some of the structures essential for the game are irrelevant for us. Possible further improvements include: freeing memory which is no longer used, or avoid allocating memory just for temporary use; representing (some) dynamic arrays a as lists since most of them are sparse; path compression to avoid using extra memory and time on long paths which lead to a single vertex. Additionally, since the hyperbolic distances between vertices are large, a grid coarser than G 7 should be more efficient. This is going to be improved in future work.

Conclusion
We have shown efficient algorithms for computing the distances between points in hyperbolic triangular grids, and distances between a given point and a set of points. We have shown how to apply these algorithms to work with the DHRG model efficiently, and how our DHRG model can be used to improve the results of the BFKL embedder.
The results in Sections 2 and 4 have been phrased for arbitrary hyperbolic triangular grids, even though in our applications and implementation we currently only use grids G 67 and G 7 . It is interesting to what extend these algorithms can be generalized to wider classes of hyperbolic graphs, such as graphs with Gromov hyperbolic constant of at most δ [1].
We believe that an efficient embedder which embeds real world scale-free networks in the DHRG model could be created; however, such embedder would be probably based on ideas similar to those that BFKL is based on, and for this reason we have decided to simply convert the results of BFKL in this paper. Creating an efficient direct DHRG embedder is an area of further research.
Finally, a combined approach could be used for HRGs, where each vertex is mapped both to a point in H 2 and the nearest vertex of our grid. Our algorithms for computing log-likelihood and generating random graphs produce all pairs of vertices which are close enough that their contribution to log-likelihood is significant, or they have a good chance of being connected. This potentially allows to use the grid to efficiently compute log-likelihood and generate HRGs in the continuous case.
We are very grateful to the anonymous referees for their careful reading of an earlier version of this work. Many parts of the paper have been greatly improved as a result of their insightful and constructive comments. This work was supported by the National Science Centre, Poland, grant DEC-2016/21/N/HS4/02100.