Wyszukiwarka
Abstrakt
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≥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.
Autorzy (4)
-
Abram Magner
- . .
-
Svante Janson
- . .
-
Giorgos Kollias
- . .
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
ELECTRONIC JOURNAL OF COMBINATORICS
nr 21,
strony 1 - 24,
ISSN: 1077-8926 - Język:
- angielski
- Rok wydania:
- 2014
- Opis bibliograficzny:
- Magner A., Janson S., Kollias G., Szpankowski W.: On Symmetry of Uniform and Preferential Attachment Graphs// ELECTRONIC JOURNAL OF COMBINATORICS. -Vol. 21, iss. 3 (2014), s.1-24
- Źródła finansowania:
-
- COST_FREE
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 86 razy
Publikacje, które mogą cię zainteresować
Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
- R. Klasing,
- A. Kosowski,
- A. Navarra
Bounds on the cover time of parallel rotor walks
- D. Dereniowski,
- A. Kosowski,
- D. Pająk
- + 1 autorów