Geodesic
Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism
Simões, Jefferson Elbert1 ; Figueiredo, Daniel R.2 ; Barbosa, Valmir C.2
1 Department of Applied Informatics, Federal University of the State of Rio de Janeiro, Rio de Janeiro, Brazil
2 Systems Engineering and Computer Science Program, COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil
ESAIM: Probability and Statistics, Tome 21 (2017), pp. 235-250

Voir la notice de l'article provenant de la source Numdam

We consider events over the probability space generated by the degree sequences of multiple independent Erdős-Rényi random graphs, and consider an approximation probability space where such degree sequences are deemed to be sequences of i.i.d. random variables. We show that, for any sequence of events with probabilities asymptotically smaller than some power law in the approximation model, the same upper bound also holds in the original model. We accomplish this by extending an approximation framework proposed in a seminal paper by McKay and Wormald. Finally, as an example, we apply the developed framework to bound the probability of isomorphism-related events over multiple independent random graphs.

Reçu le :
Accepté le :
DOI : 10.1051/ps/2017016
Classification : 05C80
Keywords: Random graphs, degree sequences, power laws, asymptotic approximations, graph isomorphism

Simões, Jefferson Elbert 1 ; Figueiredo, Daniel R. 2 ; Barbosa, Valmir C. 2

1 Department of Applied Informatics, Federal University of the State of Rio de Janeiro, Rio de Janeiro, Brazil
2 Systems Engineering and Computer Science Program, COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil 
@article{PS_2017__21__235_0,
     author = {Sim\~oes, Jefferson Elbert and Figueiredo, Daniel R. and Barbosa, Valmir C.},
     title = {Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism},
     journal = {ESAIM: Probability and Statistics},
     pages = {235--250},
     publisher = {EDP-Sciences},
     volume = {21},
     year = {2017},
     doi = {10.1051/ps/2017016},
     mrnumber = {3743913},
     zbl = {1393.05243},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ps/2017016/}
}
TY  - JOUR
AU  - Simões, Jefferson Elbert
AU  - Figueiredo, Daniel R.
AU  - Barbosa, Valmir C.
TI  - Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism
JO  - ESAIM: Probability and Statistics
PY  - 2017
SP  - 235
EP  - 250
VL  - 21
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ps/2017016/
DO  - 10.1051/ps/2017016
LA  - en
ID  - PS_2017__21__235_0
ER  - 
%0 Journal Article
%A Simões, Jefferson Elbert
%A Figueiredo, Daniel R.
%A Barbosa, Valmir C.
%T Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism
%J ESAIM: Probability and Statistics
%D 2017
%P 235-250
%V 21
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ps/2017016/
%R 10.1051/ps/2017016
%G en
%F PS_2017__21__235_0
Simões, Jefferson Elbert; Figueiredo, Daniel R.; Barbosa, Valmir C. Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism. ESAIM: Probability and Statistics, Tome 21 (2017), pp. 235-250. doi: 10.1051/ps/2017016

Cité par Sources :