Two papers accepted at the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015)
On the diameter of hyperbolic random graphs
Tobias Friedrich and Anton Krohmer
Abstract: Large real-world networks are typically scale-free. Recent re- search 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 performs close to optimal (Boguna, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation 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 β and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573–585, 2012).
For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next ques- tion is bounding the size of the diameter. The only known bound is O((log n)32/((3−β)(5−β))) (Kiwi and Mitsche. ANALCO, pp. 26–39, 2015). We present two much simpler proofs for an improved upper bound of O((log n)2/(3−β)) and a lower bound of Ω(log n). If the average degree is bounded from above by some constant, we show that the latter bound is tight by proving an upper bound of O(log n) for the diameter.
Ultra-Fast Load Balancing on Scale-Free Networks
Karl Bringmann, Tobias Friedrich, Martin Hoefer, Ralf Rothenberger and Thomas Sauerwald
Abstract: The performance of large distributed systems crucially depends on efficiently balancing their load. This has motivated a large amount of theoretical research how an imbalanced load vector can be smoothed with local algorithms. For technical reasons, the vast majority of previous work focuses on regular (or almost regular) graphs including symmetric topologies such as grids and hypercubes, and ignores the fact that large networks are often highly heterogenous.
We model large scale-free networks by Chung-Lu random graphs and analyze a simple local algorithm for iterative load balancing. On n-node graphs our distributed algorithm balances the load
within O((log log n)²) steps. It does not need to know the exponent β∈ (2,3) of the power-law degree distribution or the weights wi of the graph model. To the best of our knowledge, this is the first result which shows that load-balancing can be done in double-logarithmic time on realistic graph classes.