Geodesic
On symmetry of uniform and preferential attachment graphs
Abram Magner1 ; Svante Janson2 ; Giorgos Kollias3 ; Wojciech Szpankowski1
1Purdue University
2Uppsala University
3Thomas J. Watson Research Center
The electronic journal of combinatorics, Tome 21 (2014) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Motivated by the problem of graph structure compression under realistic source models, we study the symmetry behavior of preferential and uniform attachment graphs. These are two dynamic models of network growth in which new nodes attach to a constant number $m$ of existing ones according to some attachment scheme. We prove symmetry results for $m=1$ and $2$, and we conjecture that for $m\geq 3$, both models yield asymmetry with high probability. We provide new empirical evidence in terms of graph defect. We also prove that vertex defects in the uniform attachment model grow at most logarithmically with graph size, then use this to prove a weak asymmetry result for all values of $m$ in the uniform attachment model. Finally, we introduce a natural variation of the two models that incorporates preference of new nodes for nodes of a similar age, and we show that the change introduces symmetry for all values of $m$.
DOI : 10.37236/4415
Classification : 05C80, 05C82
Mots-clés : preferential attachment, symmetry, automorphism, random graphs

Abram Magner  1   ; Svante Janson  2   ; Giorgos Kollias  3   ; Wojciech Szpankowski  1

1 Purdue University
2 Uppsala University
3 Thomas J. Watson Research Center 
@article{10_37236_4415,
     author = {Abram Magner and Svante Janson and Giorgos Kollias and Wojciech Szpankowski},
     title = {On symmetry of uniform and preferential attachment graphs},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {3},
     doi = {10.37236/4415},
     zbl = {1298.05286},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4415/}
}
TY  - JOUR
AU  - Abram Magner
AU  - Svante Janson
AU  - Giorgos Kollias
AU  - Wojciech Szpankowski
TI  - On symmetry of uniform and preferential attachment graphs
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4415/
DO  - 10.37236/4415
ID  - 10_37236_4415
ER  - 
%0 Journal Article
%A Abram Magner
%A Svante Janson
%A Giorgos Kollias
%A Wojciech Szpankowski
%T On symmetry of uniform and preferential attachment graphs
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4415/
%R 10.37236/4415
%F 10_37236_4415
Abram Magner; Svante Janson; Giorgos Kollias; Wojciech Szpankowski. On symmetry of uniform and preferential attachment graphs. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/4415

Cité par Sources :