uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
On Symmetry of Uniform and Preferential Attachment Graphs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2014 (English)In: The Electronic Journal of Combinatorics, ISSN 1077-8926, Vol. 21, no 3, UNSP P3.32- p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2014. Vol. 21, no 3, UNSP P3.32- p.
National Category
URN: urn:nbn:se:uu:diva-233012ISI: 000341119300003OAI: oai:DiVA.org:uu-233012DiVA: diva2:754184
Available from: 2014-10-09 Created: 2014-09-29 Last updated: 2014-10-09Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Janson, Svante
By organisation
Department of Mathematics
In the same journal
The Electronic Journal of Combinatorics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 164 hits
ReferencesLink to record
Permanent link

Direct link