Draief, Moez M <m.draief@imperial.ac.uk>
to	Arnaud Durand <durand@logique.jussieu.fr>,
Gerard.Duchamp@lipn.univ-paris13.fr
date	21 February 2009 19:06
subject	RE: [gdr-im] session spéciale : "Combinatorics, Physics and Complexity"
mailed-by	lipn.univ-paris13.fr
	
hide details 19:06
	
	
Reply
	
	

Chers Arnaud et Gerard

Voici un titre et un resume sur un travail recent que j'ai fait disponible sur arXiv. http://arxiv.org/PS_cache/arxiv/pdf/0810/0810.3173v1.pdf)

Bien cordialement

Moez

Exponential random graphs as models of overlay networks

Moez Draief (Imperial College London)

In this talk, we describe a Metropolis-Hastings type algorithm to construct optimised overlay networks in the context of Peer-to-Peer systems to provide load balancing and minimise communication costs. We show that the graphs obtained are distributed according to a Gibbs like distribution $?(G) = \frac{1}{Z}e^{-\beta sum_i d_i^2} $ on a subset of of the set of connected graphs with $n$ nodes, $d_i$ being the degree of node i. Using analogies with the configuration model for graph generation we derive a number of asymptotic results for the properties of such graphs. More precisely we show that the degrees are concentrated around their mean value,  derive asymptotic results on the number of edges crossing a graph cut and use these results (i) to compute the graph expansion and conductance, and (ii) to analyse the graph resilience to random failures.

Joint work with Ayalvadi Ganesh and Laurent Massoulie.