Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular our embeddings guarantee that greedy routing always succeeds in reaching the target and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real wold networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph [2], we achieve near-optimal results, i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths. In the case of the Internet graph, they are only 6% longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention.

Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the Internet can be mapped to a hyperbolic space such that geometric greedy routing is close to optimal [M. Bogun͂á, F. Papadopoulos, and D. Krioukov, Nature Commun., 1 (2010), pp. 1--62]. This observation has pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power law degree distribution with controllable exponent $\beta$ and show high clustering [L. Gugelmann, K. Panagiotou, and U. Peter, Proceedings of the 39 th International Colloquium on Automata, Languages and Programming, 2012, pp. 573--585]. For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is $\mathcal{O}((\log n)^{32/((3-\beta)(5-\beta)) + 1})$ [M. Kiwi and D. Mitsche, Proceedings of ANALCO, 2015, pp. 26--39]. We present two much simpler proofs for an improved upper bound of $\mathcal{O}((\log n)^{2/(3-\beta)})$ and a lower bound of $\Omega(\log n)$. If $\beta > 3$, we show that the latter bound is tight by proving an upper bound of $\mathcal{O}(\log n)$ for the diameter.

Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs called the rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave in a remarkably similar way: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer [ Combin. Probab. Comput., 15 (2006), pp. 815--822] showed that on $\mathbb{Z}^d$, the single vertex discrepancy is only a constant $c_d$. Other authors also determined the precise value of $c_d$ for $d=1,2$. All of these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph $\mathbb{Z}^d$. We show that this assumption is crucial by proving that, otherwise, the single vertex discrepancy can become arbitrarily large. For all dimensions $d\geqslant1$ and arbitrary discrepancies $\ell\geqslant0$, we construct configurations that reach a discrepancy of at least $\ell$.

Recently, a number of non-uniform random satisfiability models have been proposed that are closer to practical satisfiability problems in some characteristics. In contrast to uniform random Boolean formulas, scale-free formulas have a variable occurrence distribution that follows a power law. It has been conjectured that such a distribution is a more accurate model for some industrial instances than the uniform random model. Though it seems that there is already an awareness of a threshold phenomenon in such models, there is still a complete picture lacking. In contrast to the uniform model, the critical density threshold does not lie at a single point, but instead exhibits a functional dependency on the power-law exponent. For scale-free formulas with clauses of length k=2, we give a lower bound on the phase transition threshold as a function of the scaling parameter. We also perform computational studies that suggest our bound is tight and investigate the critical density for formulas with higher clause lengths. Similar to the uniform model, on formulas with k>=3, we find that the phase transition regime corresponds to a set of formulas that are difficult to solve by backtracking search.

Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory. The average-case analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scale-free distribution of the variables, which results in distributions closer to industrial SAT instances. We study random k-SAT on n variables, $m=Θ(n)$ clauses, and a power law distribution on the variable occurrences with exponent $β$. We observe a satisfiability threshold at $β=(2k-1)/(k-1)$. This threshold is tight in the sense that instances with $β\le(2k-1)/(k-1)-\varepsilon$ for any constant $\varepsilon>0$ are unsatisfiable with high probability (w.h.p.). For $β\geq(2k-1)/(k-1)+\varepsilon$, the picture is reminiscent of the uniform case: instances are satisfiable w.h.p. for sufficiently small constant clause-variable ratios $m/n$; they are unsatisfiable above a ratio $m/n$ that depends on $β$.

Hyperbolic random graphs share many common properties with complex real-world networks; e.g., small diameter and average distance, large clustering coefficient, and a power-law degree sequence with adjustable exponent beta. Thus, when analyzing algorithms for large networks, potentially more realistic results can be achieved by assuming the input to be a hyperbolic random graph of size n. The worst-case run-time is then replaced by the expected run-time or by bounds that hold with high probability (whp), i.e., with probability 1-O(1/n). Though many structural properties of hyperbolic random graphs have been studied, almost no algorithmic results are known. Divide-and-conquer is an important algorithmic design principle that works particularly well if the instance admits small separators. We show that hyperbolic random graphs in fact have comparatively small separators. More precisely, we show that they can be expected to have balanced separator hierarchies with separators of size O(n^{3/2-beta/2}), O(log n), and O(1) if 2 < beta < 3, beta = 3, and 3 < beta, respectively. We infer that these graphs have whp a treewidth of O(n^{3/2-beta/2}), O(log^2 n), and O(log n), respectively. For 2 < \beta < 3, this matches a known lower bound. To demonstrate the usefulness of our results, we give several algorithmic applications.

Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of Omega(n^2). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.

Most complex real-world networks display scale-free features. This motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Papadopoulos, Krioukov, Boguñá, Vahdat (INFOCOM, pp. 2973-2981, 2010) and has shown theoretically and empirically to fulfill all typical properties of real-world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs G and present new results on the expected number of k-cliques E[Kk] and the size of the largest clique ω(G). We observe that there is a phase transition at power-law exponent γ = 3. More precisely, for γ ε (2,3) we prove E[Kk] = nk(3-γ)/2Θ(k)-kand ω(G) = Θ(n(3-γ)/2) while for γ ≥ 3 we prove E[Kk] = nΘ(k)-kand ω(G) = Θ(log(n)/log log n). We empirically compare the ω(G) value of several scale-free random graph models with real-world networks. Our experiments show that the ω(G)-predictions by hyperbolic random graphs are much closer to the data than other scale-free random graph models.

The integrated analysis of data of different types and with various interdependencies is one of the major challenges in computational biology. Recently, we developed KeyPathwayMiner, a method that combines biological networks modeled as graphs with disease-specific genetic expression data gained from a set of cases (patients, cell lines, tissues, etc.). We aimed for finding all maximal connected sub-graphs where all nodes but $K$ are expressed in all cases but at most $L$, i.e. key pathways. Thereby, we combined biological networks with OMICS data, instead of analyzing these data sets in isolation. Here we present an alternative approach that avoids a certain bias towards hub nodes: We now aim for extracting all maximal connected sub-networks where all but at most $K$ nodes are expressed in all cases but in total (!) at most $L$, i.e. accumulated over all cases and all nodes in a solution. We call this strategy GLONE (global node exceptions); the previous problem we call INES (individual node exceptions). Since finding GLONE-components is computationally hard, we developed an Ant Colony Optimization algorithm and implemented it with the KeyPathwayMiner Cytoscape framework as an alternative to the INES algorithms. KeyPathwayMiner 3.0 now offers both the INES and the GLONE algorithms. It is available as plugin from Cytoscape and online at http://keypathwayminer.mpi-inf.mpg.de.