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.
Accepté le :
DOI : 10.1051/ps/2017016
Mots clés : Random graphs, degree sequences, power laws, asymptotic approximations, graph isomorphism
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ps/2017016/
N. Alon and J.H. Spencer, The Probabilistic Method. Wiley, New York, 2nd edition (2000). | MR | Zbl
, and , Random graph isomorphism. SIAM J. Comput. 9 (1980) 628–635. | DOI | MR | Zbl
L. Babai and L. Kučera, Canonical labelling of graphs in linear average time. In Proc. of FOCS’79, the 20th Ann. Sympos. Foundations Comput. Sci. (1979) 39–46.
L. Babai and E.M. Luks, Canonical labeling of graphs. In Proc. of STOC’83, the Fifteenth Annual ACM Symposium on Theory of Computing (1983) 171–183.
B. Bollobás, Random Graphs. Cambridge University Press, Cambridge, UK, 2nd edition (2001). | MR | Zbl
and , Improved random graph isomorphism. J. Discrete Algorithms 6 (2008) 85–92. | DOI | MR | Zbl
and , On random graphs I. Publ. Math. (Debrecen) 6 (1959) 290–297. | DOI | MR | Zbl
, Random graphs. Ann. Math. Statist. 30 (1959) 1141–1144. | DOI | MR | Zbl
R.M. Karp, Probabilistic analysis of a canonical numbering algorithm for graphs. In Relations Between Combinatorics and Other Parts of Mathematics, edited by D.K. Ray-Chaudhuri. Vol. 34 of Proc. of Symposia in Pure Mathematics. Providence, RI. AMS (1979) 365–378. | MR | Zbl
and , Chvàtal’s condition cannot hold for both a graph and its complement. Discuss. Math. Graph Theory 26 (2006) 73–76. | DOI | MR | Zbl
R.J. Lipton, The beacon set approach to graph isomorphism. Technical Report 135, Department of Computer Science, Yale University, New Haven, CT (1978).
and , The degree sequence of a random graph. I. The models. Random Struct. Algorithms 11 (1997) 97–117. | DOI | MR | Zbl
P. Pedarsani and M. Grossglauser, On the privacy of anonymized networks. In Proc. of KDD’11, the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2011) 1235–1243.
, Mean field frozen percolation. J. Statist. Phys. 137 (2009) 459–499. | DOI | MR | Zbl
F. Skerman, Degree sequences of random bipartite graphs. Ph.D. thesis, The Australian National University, Canberra (2010).
M. Vento and P. Foggia, Graph matching techniques for computer vision. In Graph-Based Methods in Computer Vision: Developments and Applications, edited by X. Bai, J. Cheng, and Edwin Hancock. Information Science Reference, Hershey, PA (2013) 1–41.
Cité par Sources :
