4 May 11:00 George Giakkoupis: Search in small-world networks

George Giakkoupis from Paris 7 will give a talk on Tuesday 4.5. at 11:00 in Spektri 3rd floor meeting room. All are welcome to attend. 

Title: Search in small-world networks

Abstract:

In his seminal work on search in social networks, Kleinberg proposed the following simple model. Individuals are the nodes of a base graph, the square grid, capturing the underlying structure of the social network. The grid is augmented with additional edges from each node to a few long-range contacts, chosen according to some natural distance-based distribution. In this augmented graph, a simple greedy search algorithm takes only a polylogarithmic number of steps in the graph size.

Following Kleinberg's work, several papers investigated the
> correlations between underlying structure and long-range connections
> that yield efficient decentralized search. I will focus on two
> problems in this context. The first is about the role of the
> underlying structure. A great effort has been made to identify the
> most general families of underlying structures that can yield
> efficiently searchable small-world network. We show that for a
> simple augmenting distribution consistent with empirical
> observations on social networks, reasonably fast (almost) greedy
> search is possibly for any base graph. This result could be seen as
> a possible explanation for the searchability of social networks.
>
> The second problem is about the role of the augmenting distribution,
> more specifically, the role of high-degree nodes, a.k.a. hubs. Past
> work has focused almost exclusively on augmentations that result on
> roughly the same degree over all nodes. Motivated by the observed
> degree distributions on real networks, we consider a variant of
> Kleinberg's grid-based model with power-law degrees, and we study
> the performance of greedy search as a function of the power-law
> exponent. We show that search is faster for a very specific range of
> this exponent, which, interestingly, matches the range measured for
> many real networks. Further, we explore distributions that result in
> optimal search performance.
>
> The results presented are joint work with Vassos Hadzilacos
> (PODC'07), Pierre Fraigniaud (PODC'09, STOC'10), and Enoch Peserico
> (in preparation).
>
> Bio:
>
> I was born in Greece. I did my undergraduate studies in the National
> Technical Univ. of Athens, and my PhD in the Univ. of Toronto. My
> PhD was on load balancing and routing algorithms for p2p systems,
> under the supervision of Vassos Hadzilacos. Since the end of 2008, I
> am a post-doc student in Paris, Univ. 7, supervised by Pierre
> Fraigniaud. My research interests are in the area of randomized
> algorithms. So far, I have focused on probabilistic models and
> algorithms for large networks, such as p2p and social networks.
> Besides the work on my PhD thesis, I have also worked on the
> problems of search in small worlds, randomized rumor spreading, and
> network immunization.