A note on perfect simulation for Exponential Random Graph Models
ESAIM: Probability and Statistics, Tome 24 (2020), pp. 138-147.

In this paper, we propose a perfect simulation algorithm for the Exponential Random Graph Model, based on the Coupling from the past method of Propp and Wilson (1996). We use a Glauber dynamics to construct the Markov Chain and we prove the monotonicity of the ERGM for a subset of the parametric space. We also obtain an upper bound on the running time of the algorithm that depends on the mixing time of the Markov chain.

DOI : 10.1051/ps/2019024
Classification : 60K35, 60J22
Mots-clés : Exponential Random Graph, perfect simulation, coupling from the past, MCMC, Glauber dynamics 
@article{PS_2020__24_1_138_0,
     author = {Cerqueira, Andressa and Garivier, Aur\'elien and Leonardi, Florencia},
     title = {A note on perfect simulation for {Exponential} {Random} {Graph} {Models}},
     journal = {ESAIM: Probability and Statistics},
     pages = {138--147},
     publisher = {EDP-Sciences},
     volume = {24},
     year = {2020},
     doi = {10.1051/ps/2019024},
     mrnumber = {4071317},
     zbl = {1434.60277},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ps/2019024/}
}
TY  - JOUR
AU  - Cerqueira, Andressa
AU  - Garivier, Aurélien
AU  - Leonardi, Florencia
TI  - A note on perfect simulation for Exponential Random Graph Models
JO  - ESAIM: Probability and Statistics
PY  - 2020
SP  - 138
EP  - 147
VL  - 24
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ps/2019024/
DO  - 10.1051/ps/2019024
LA  - en
ID  - PS_2020__24_1_138_0
ER  - 
%0 Journal Article
%A Cerqueira, Andressa
%A Garivier, Aurélien
%A Leonardi, Florencia
%T A note on perfect simulation for Exponential Random Graph Models
%J ESAIM: Probability and Statistics
%D 2020
%P 138-147
%V 24
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ps/2019024/
%R 10.1051/ps/2019024
%G en
%F PS_2020__24_1_138_0
Cerqueira, Andressa; Garivier, Aurélien; Leonardi, Florencia. A note on perfect simulation for Exponential Random Graph Models. ESAIM: Probability and Statistics, Tome 24 (2020), pp. 138-147. doi : 10.1051/ps/2019024. http://www.numdam.org/articles/10.1051/ps/2019024/

[1] S. Bhamidi, G. Bresler and A. Sly, Mixing time of exponential random graphs. Ann. Appl. Probab. 21 (2011) 2146–2170. | MR | Zbl

[2] C.T. Butts, A perfect sampling method for exponential family random graph models. J. Math. Sociol. 42 (2018) 17–36. | MR | Zbl

[3] A. Cerqueira, D. Fraiman, C.D. Vargas and F. Leonardi, A test of hypotheses for random graph distributions built from EEG data. IEEE Trans. Netw. Sci. Eng. (2017). | MR

[4] S. Chatterjee, P. Diaconis et al., Estimating and understanding exponential random graph models. Ann. Stat. 41 (2013) 2428–2461. | MR | Zbl

[5] C.J. Geyer and E.A. Thompson, Constrained Monte–Carlo maximum likelihood for dependent data. J. Roy. Stat. Soc. Ser. B (Methodological) 54, (1992) 657–699. | MR

[6] D.A. Levin, Y. Peres and E.L. Wilmer, Markov chains and mixing times. American Mathematical Soc. (2009). | MR | Zbl

[7] M.E. Newman, D.J. Watts and S.H. Strogatz, Random graph models of social networks. Proc. Natl. Acad. Sci. 99 (2002) 2566–2572. | Zbl

[8] J.G. Propp and D.B. Wilson, Exact sampling with coupled markov chains and applications to statistical mechanics. Random Struct. Algor. 9 (1996) 223–252. | MR | Zbl

[9] G. Robins, P. Pattison, Y. Kalish and D. Lusher, An introduction to exponential random graph (p*) models for social networks. Social Netw. 29 (2007) 173–191.

[10] T.A. Snijders, Markov chain Monte Carlo estimation of exponential random graph models. J. Soc. Struct. 3 (2002) 1–40.

[11] D. Strauss and M. Ikeda, Pseudolikelihood estimation for social networks. J. Am. Stat. Assoc. 85 (1990) 204–212. | DOI | MR

Cité par Sources :