Asymmetry and structural information in preferential attachment graphs

DOI10.1002/RSA.20842zbMATH Open1440.05071arXiv1607.04102OpenAlexW2922346813WikidataQ128229414 ScholiaQ128229414MaRDI QIDQ4973642FDOQ4973642

Authors: Tomasz Łuczak, Abram Magner, Wojciech Szpankowski 

Publication date: 28 November 2019

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: Graph symmetries intervene in diverse applications, from enumeration, to graph structure compression, to the discovery of graph dynamics (e.g., node arrival order inference). Whereas ErdH{o}s-R'enyi graphs are typically asymmetric, real networks are highly symmetric. So a natural question is whether preferential attachment graphs, where in each step a new node with $m$ edges is added, exhibit any symmetry. In recent work it was proved that preferential attachment graphs are symmetric for $m=1$, and there is some non-negligible probability of symmetry for $m=2$. It was conjectured that these graphs are asymmetric when $mgeq3$. We settle this conjecture in the affirmative, then use it to estimate the structural entropy of the model. To do this, we also give bounds on the number of ways that the given graph structure could have arisen by preferential attachment. These results have further implications for information theoretic problems of interest on preferential attachment graphs.

Full work available at URL: https://arxiv.org/abs/1607.04102

Recommendations

• On symmetry of uniform and preferential attachment graphs
• On symmetry of uniform and preferential attachment graphs
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Compression and symmetry of small-world graphs and structures
• Isomorphism and embedding problems for infinite limits of scale-free graphs

zbMATH Keywords

entropysymmetrydegree distributiongraph automorphismpreferential attachment graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07)

Cited In (7)

• Towards degree distribution of a duplication-divergence graph model
• On symmetry of uniform and preferential attachment graphs
• Asymmetric Distribution of Nodes in the Spatial Preferred Attachment Model
• On symmetry of uniform and preferential attachment graphs
• Compression and symmetry of small-world graphs and structures
• The concentration of the maximum degree in the duplication-divergence models
• Compression of dynamic graphs generated by a duplication model

This page was built for publication: Asymmetry and structural information in preferential attachment graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4973642)