Exponential random graphs as models of overlay networks

M Draief, AJ Ganesh, L Massoulie

Research output: Contribution to journalArticle (Academic Journal)peer-review

3 Citations (Scopus)

Abstract

In this paper we give an analytic solution for graphs with n nodes and E=cnlogn edges for which the probability of obtaining a given graph G is µn(G)=exp(-β∑{i=1}ndi2), where di is the degree of node i. We describe how this model appears in the context of load balancing in communication networks, namely peer-to-peer overlays. We then analyse the degree distribution of such graphs and show that the degrees are concentrated around their mean value. Finally, we derive asymptotic results for 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.
Translated title of the contributionExponential random graphs as models of overlay networks
Original languageEnglish
Pages (from-to)199 - 220
Number of pages22
JournalJournal of Applied Probability
Volume46
Issue number1
DOIs
Publication statusPublished - Mar 2009

Fingerprint Dive into the research topics of 'Exponential random graphs as models of overlay networks'. Together they form a unique fingerprint.

Cite this