pith. sign in

arxiv: 2504.21741 · v1 · submitted 2025-04-30 · 🧮 math.PR · math.CO

Asymptotic diameter of preferential attachment model

Hang Du , Shuyang Gong , Zhangsong Li , Haodong Zhu This is my paper

Pith reviewed 2026-05-22 17:43 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords preferential attachmentrandom graphsdiameterlocal weak limitasymptoticsgraph distanceprobability
0
0 comments X

The pith

The diameter of preferential attachment graphs is (1+o(1)) log_ν n with high probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that in the preferential attachment model with m at least 2 and δ positive, the longest shortest path in the graph G_n grows asymptotically as (1 plus a term going to zero) times the logarithm base ν of n, and this holds with high probability. This matters because it pins down the global scale of distances in these randomly growing networks as n becomes large. A sympathetic reader would care since the result resolves an open conjecture on the precise diameter and completes the picture for all allowed parameter values. The argument rests on linking the diameter to the typical distance via the local structure of the graph.

Core claim

We prove that the diameter of G_n ~ PA_n^(m,δ) is (1+o(1)) log_ν n with high probability, where ν is the exponential growth rate of the local weak limit of G_n. This confirms the conjecture in prior work and closes the remaining gap for general parameters m greater than or equal to 1 and δ greater than -m. The proof follows a general recipe relating diameter to typical distance.

What carries the argument

The general recipe that relates diameter to typical distance, applied to the local weak limit and its exponential growth rate ν in the preferential attachment model.

If this is right

  • The diameter result now holds for the full range of parameters m at least 1 and δ greater than -m.
  • The conjecture on diameter from the work establishing the local weak limit is confirmed.
  • The same recipe is expected to relate diameter and typical distance in a wider class of random graph models.
  • Global distances in these networks are governed by the exponential growth rate of the local structure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The recipe may yield diameter asymptotics in other growing network models whose local weak limits are known.
  • Numerical checks on finite but large instances could confirm the log_ν n scaling for concrete m and δ.
  • The result suggests that navigation or search times across the network scale like log_ν n.
  • Similar techniques could connect diameter to other global functionals such as the size of the largest component.

Load-bearing premise

The local weak limit of the preferential attachment graph exists and possesses a well-defined exponential growth rate ν, so that the general diameter-to-typical-distance relation applies without further restrictions.

What would settle it

A direct computation of the diameter on a sequence of large simulated preferential attachment graphs, with ν known from the local limit, showing systematic deviation from (1+o(1)) log_ν n.

read the original abstract

We study the asymptotic diameter of the preferential attachment model $\operatorname{PA}\!_n^{(m,\delta)}$ with parameters $m \ge 2$ and $\delta > 0$. Building on the recent work \cite{VZ25}, we prove that the diameter of $G_n \sim \operatorname{PA}\!_n^{(m,\delta)}$ is $(1+o(1))\log_\nu n$ with high probability, where $\nu$ is the exponential growth rate of the local weak limit of $G_n$. Our result confirms the conjecture in \cite{VZ25} and closes the remaining gap in understanding the asymptotic diameter of preferential attachment graphs with general parameters $m \ge 1$ and $\delta >-m$. Our proof follows a general recipe that relates the diameter of a random graph to its typical distance, which we expect to have applicability in a broader range of models.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that the diameter of the preferential attachment graph G_n ~ PA_n^(m,δ) with m ≥ 2 and δ > 0 is (1+o(1)) log_ν n with high probability, where ν is the exponential growth rate of the local weak limit of G_n. The proof builds on the local weak limit and growth rate established in the cited prior work VZ25 and applies a general recipe relating diameter to typical distance in the graph.

Significance. If the central claim holds, the result confirms the conjecture stated in VZ25 and completes the asymptotic picture of the diameter for preferential attachment graphs across the full parameter range m ≥ 1, δ > -m. The general recipe for passing from typical distance to diameter is a methodological contribution that may apply to other models with a well-defined local weak limit and growth rate; the paper explicitly credits the independent prior work for the existence of ν.

major comments (2)
  1. [§4] §4 (application of the general recipe): the argument that the o(1) error in the typical-distance result lifts directly to the diameter bound requires an explicit uniform control on the probability of atypical vertices; without a quantitative bound on the exceptional set size, the high-probability claim for the global diameter is not yet fully justified.
  2. [Theorem 1.1] Theorem 1.1 and the reduction in §3: the statement assumes that the local weak limit satisfies the exact conditions of the diameter-to-typical-distance recipe for all δ > 0; a short verification that the branching-process offspring distribution remains supercritical and that the growth rate ν is strictly greater than 1 under the given parameter restrictions would remove any ambiguity about the applicability of the recipe.
minor comments (2)
  1. [Introduction] The notation PA_n^(m,δ) is used throughout without a self-contained definition in the introduction; a one-sentence reminder of the attachment rule and the precise range of δ would improve readability for readers who have not consulted VZ25.
  2. [Theorem 1.1] In the statement of the main theorem, the phrase 'with high probability' should be accompanied by the explicit rate (e.g., 1 - o(1) or 1 - n^{-c}) to match the quantitative statements in the body of the proof.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the constructive comments, which will improve the clarity of the manuscript. We address each major comment below and will revise accordingly.

read point-by-point responses

  1. Referee: [§4] §4 (application of the general recipe): the argument that the o(1) error in the typical-distance result lifts directly to the diameter bound requires an explicit uniform control on the probability of atypical vertices; without a quantitative bound on the exceptional set size, the high-probability claim for the global diameter is not yet fully justified.

    Authors: We agree that the lifting argument benefits from an explicit quantitative bound. The general recipe assumes such controls via the local weak limit, but to make the high-probability diameter statement fully rigorous we will add, in the revised Section 4, a uniform bound on the probability of the exceptional set of atypical vertices. This bound follows from the concentration estimates already established for the local weak limit in VZ25 and will be stated explicitly. revision: yes

  2. Referee: [Theorem 1.1] Theorem 1.1 and the reduction in §3: the statement assumes that the local weak limit satisfies the exact conditions of the diameter-to-typical-distance recipe for all δ > 0; a short verification that the branching-process offspring distribution remains supercritical and that the growth rate ν is strictly greater than 1 under the given parameter restrictions would remove any ambiguity about the applicability of the recipe.

    Authors: We accept the suggestion. For m ≥ 2 and δ > 0 the offspring distribution of the branching-process limit has mean strictly larger than 1 (explicitly m(δ + m)/(δ + m) adjusted by the attachment kernel), ensuring supercriticality, while ν > 1 follows directly from the Malthusian equation solved in VZ25. We will insert a short verification paragraph in Section 3 that checks these two conditions under the stated parameter range. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation builds directly on the existence of the local weak limit and its exponential growth rate ν as established in the independent prior work VZ25, then applies a general recipe relating diameter to typical distance that is presented as broadly applicable rather than derived from the paper's own fitted quantities or self-referential definitions. No step reduces by construction to the paper's inputs, no self-citation chain carries the central claim, and the result is not equivalent to renaming or fitting a parameter from the same data. The argument is self-contained against the external benchmark of VZ25.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the existence and properties of the local weak limit (including its exponential growth rate ν) from prior literature, plus the applicability of a general diameter-to-typical-distance relation. No new free parameters are introduced; the result is an asymptotic statement rather than a fitted model.

axioms (2)
  • domain assumption The preferential attachment graph PA_n^(m,δ) admits a local weak limit whose branching-process offspring distribution yields a well-defined exponential growth rate ν.
    Invoked directly in the statement of the main theorem; taken from the cited work VZ25.
  • domain assumption The general recipe that relates graph diameter to typical distance applies to the preferential attachment model without additional parameter restrictions.
    Used as the proof strategy; presented as a reusable method expected to hold for these parameters.

pith-pipeline@v0.9.0 · 5685 in / 1534 out tokens · 40461 ms · 2026-05-22T17:43:29.395352+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.