Exponential Random Graphs as Models of Overlay Networks

DOI10.1239/JAP/1238592125MaRDI QIDQ3621156zbMATH OpenOpenAlexFDO

Authors Moez Draief, Ayalvadi J. Ganesh, Laurent Massoulié

Publication date 14 April 2009

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.3173

zbMATH Keywords

conductancedegree distributionexpansionexponential random graphfailure resiliencegraph cutload balancingoverlay optimisationpeer-to-peer network

Mathematics Subject Classification ID

Vertex degrees (05C07) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graph theory (including graph drawing) in computer science (68R10) Communication networks in operations research (90B18)

Abstract: In this paper, we give an analytic solution for graphs with n nodes and E edges for which the probability of obtaining a given graph G is specified in terms of the degree sequence of G. We describe how this model naturally 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 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.

Recommendations

• Random growth networks with exponential degree distribution
• Topological properties of the one dimensional exponential random geometric graph
• Estimating and understanding exponential random graph models
• Exchangeable random networks
• On the asymptotics of constrained exponential random graphs

Cites work

• A local limit theorem for large deviations of sums of independent, nonidentically distributed random variables
• An Exponential Family of Probability Distributions for Directed Graphs
• Asymptotic enumeration by degree sequence of graphs of high degree
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3513115 (Why is no real title available?)
• scientific article; zbMATH DE number 1054729 (Why is no real title available?)
• scientific article; zbMATH DE number 878889 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• Markov Chains
• Markov Graphs
• Poisson approximation for some epidemic models
• Random graph dynamics
• Random graphs.
• The probability that a random multigraph is simple
• Thresholds for virus spread on networks

Cited in

(4)

• Exponential random graph models for networks resilient to targeted attacks
• Exponential-family random graph models for multi-layer networks
• Random growth networks with exponential degree distribution
• Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms

This page was built for publication: Exponential Random Graphs as Models of Overlay Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3621156)