# Toronto Networking Seminar

## Navigation in Small-World Graphs with Power-Law Degrees

### Abstract:

We analyzed decentralized search in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we considered a variation of Kleinberg's augmented-lattice model (STOC 2000), where the number of long-range links for each node is drawn from a power-law distribution. This model was motivated by the experimental observation that many `real-world' networks have power-law degrees. We showed that greedy search performs better in this model than in Kleinberg's original model (where the degrees are fixed) if and only if the power-law exponent $\alpha$ is within a very specific range, namely $2 < \alpha < 3$. More precisely, we showed that $\Theta(\log^{\alpha-1} n)$ expected steps are required in the model with power-law degrees when $2 < \alpha < 3$, whereas $\Theta(\log2 n)$ expected steps are required in Kleinberg's model. Interestingly, the power-law exponents that have been measured for most real-world networks are exactly in this range, between $2$ and $3$. To the best of our knowledge, these results are the first to formally quantify the exactly in this range, between $2$ and $3$. To the best of our knowledge, these results are the first to formally quantify the effect of the power-law degrees on the navigability of small worlds.

This is a joint work with Pierre Fraigniaud.

### Host of the talk

Peter Marbach (marbach@cs.toronto.edu)