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 Erdős-Renyi 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 $m \geq 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.
Introduction
In graph theory, symmetry (or automorphism) occurs when you can swap two or more nodes without changing the graph's structure. While simple random graphs (Erdős-Rényi) are almost always asymmetric, real-world networks—such as social or biological networks—often exhibit significant symmetry. This paper addresses a long-standing conjecture in network science regarding the symmetry of Preferential Attachment (PA) graphs, the standard model for "scale-free" real-world networks.
In the PA model, nodes arrive sequentially and "prefer" to connect to existing nodes that already have many connections (the "rich-get-richer" effect). Previous research established that PA graphs are symmetric when $m=1$ (forming trees) and have a non-negligible chance of symmetry when $m=2$. This work formally proves that for $m \geq 3$, the probability of finding any non-trivial symmetry vanishes as the graph size $n$ approaches infinity.
Empirical Motivation
While the core of the paper is a theoretical proof, numerical simulations provide strong empirical support for the transition from symmetry to asymmetry. Figure 1 illustrates the "numerical defect" across different values of $m$ for a Uniform Attachment model, which serves as a baseline for understanding structural uniqueness.
As shown, for $m=1$, the defect remains at zero, consistent with the known symmetry of these structures. However, for $m \geq 2$, the defect increases with graph size, with $m=3$ and $m=4$ showing significantly higher values, supporting the conjecture that these graphs become almost certainly asymmetric as they grow.
Theoretical Framework
The authors employ a rigorous probabilistic proof relying on two primary mathematical properties:
- Property $\mathfrak{A}$ (Neighborhood Uniqueness): For "younger" nodes (those arriving later), it is highly unlikely that any two nodes will choose the exact same set of $m$ neighbors among the "older" nodes.
- Property $\mathfrak{B}$ (Degree Uniqueness): The "oldest" nodes (the first $k$ nodes to arrive) develop unique degrees. Because their degrees are distinct, these nodes cannot be swapped with one another in any symmetry-preserving mapping.
To unify these properties, the Method of Bounded Variances is used. This concentration inequality technique demonstrates that the degree of a node stays very close to its expected value, ensuring the "gap" between the degrees of the oldest nodes is large enough to keep them unique and "fixed" in place.
Key Insights
- The $m=3$ Threshold: The most striking insight is that $m=3$ is the "tipping point." While $m=1$ and $m=2$ allow for structural "twins" (nodes that look identical to the rest of the graph), adding just one more edge per node provides enough structural information to uniquely identify almost every node.
- Old Nodes as Anchors: The oldest nodes in a PA graph act as structural anchors. Because they arrive early, they accumulate the most edges and their degrees become highly differentiated. Once these "hubs" are fixed, the rest of the graph's symmetry collapses.
- Information Theory Link: Asymmetry is directly linked to structural entropy. If a graph is asymmetric, its unlabeled version contains nearly as much information as its labeled version, which is crucial for designing optimal graph compression algorithms.
Results
The main theorem states that for a preferential attachment graph $G$ with $m \geq 3$, the size of the automorphism group $|Aut(G)|$ is 1 with high probability. The authors provide a specific bound on the probability of symmetry: $P(|Aut(G)| > 1) = O(n^{-0.004})$. While the exponent is small, it proves that symmetry becomes impossible in the limit.
Furthermore, the proof suggests that because the graph is asymmetric and the oldest nodes are so distinct, one could potentially reconstruct the exact order in which nodes arrived just by looking at an unlabeled "snapshot" of the network.
Limitations and Future Work
The current proof assumes a linear preferential attachment model ($\alpha = 1$). In "non-linear" models (where attachment probability is proportional to $degree^\alpha$), the problem is more complex because connection probabilities depend on the entire degree sequence. Additionally, the $O(n^{-0.004})$ bound is likely conservative; future work could aim for a tighter decay rate. Extensions to other models, such as the Cooper-Frieze model or models allowing node deletion, also remain open.
Summary updated