Premium
Asymmetry and structural information in preferential attachment graphs
Author(s) -
Łuczak Tomasz,
Magner Abram,
Szpankowski Wojciech
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20842
Subject(s) - preferential attachment , combinatorics , conjecture , mathematics , graph , asymmetry , discrete mathematics , computer science , complex network , physics , quantum mechanics
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 Erdős‐Rényi 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 nonnegligible probability of symmetry for m = 2. It was conjectured that these graphs are asymmetric when m ≥ 3. 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.