Navigation in Small-World
Graphs with Power-Law Degrees
George Giakkoupis
Laboratoire d'Informatique
Algorithmique
Paris, France
Date: Tuesday, August 18, 2pm
Location: BA 5256
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.
Bio:
Host of the talk
Peter Marbach (marbach@cs.toronto.edu)