Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> AUG 18: Toronto Networking Seminar
About
Undergraduate
Graduate
Research
People
News & Events
AUG 18: Toronto Networking Seminar
Event date: Tuesday, August 18, 2009, at 2:00 PM
Location: Bahen Centre Rm 5256
Title:
Navigation in Small-World Graphs with Power-Law Degrees
Speaker:
George Giakkoupis (Laboratoire d'Informatique Algorithmique; Paris, France)
When:
Tuesday August 18, 2pm
Where:
BA5256
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.