On symmetry of uniform and preferential attachment graphs
type: Item
instance of: scholarly article
title: On symmetry of uniform and preferential attachment graphs
zbMATH Open document ID: 1298.05286
author: Abram Magner
author: Svante Janson
author: Giorgos Kollias
author: Wojciech Szpankowski
published in: The Electronic Journal of Combinatorics
publication date: 2014-09-09T00:00:00Z
full work available at URL: v21i3p32
review text: Summary: 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\geqslant 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\).
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C82
zbMATH DE Number: 6341633
zbMATH Keywords: preferential attachment
zbMATH Keywords: symmetry
zbMATH Keywords: automorphism
zbMATH Keywords: random graphs
MaRDI profile type: Publication
cites work: Statistical mechanics of complex networks
cites work: Q5674726
cites work: The Asymptotic Number of Unlabelled Regular Graphs
cites work: The diameter of a scale-free random graph
cites work: Compression of Graphical Structures: Fundamental Limits, Algorithms, and Experiments
cites work: Asymmetric graphs
cites work: Functional limit theorems for multitype branching processes and generalized Pólya urns.
cites work: On the asymmetry of random regular graphs and random graphs
cites work: Q4940321
description: scientific article; zbMATH DE number 6341633