Threshold graphs are built by adding vertices one at a time, each either connected to all existing vertices or to none. The construction is deterministic and sequential — the graph's structure is entirely encoded in a binary string of “join” and “isolate” decisions.
This paper replaces the deterministic decisions with a Pólya urn. Each new vertex is a join with probability determined by the current urn composition, and the urn updates based on the outcome — success reinforces success. The resulting random graph model inherits the sequential structure of threshold graphs but acquires the rich-get-richer dynamics of Pólya processes.
The exact degree distribution for any vertex is computable in closed form. So is the Laplacian spectrum. The algebraic structure of threshold graphs — which makes their spectra unusually tractable — survives the randomization because the Pólya dynamics preserve the sequential ordering.
The practical consequence appears in consensus dynamics: how quickly a network of agents converges to agreement. Because the spectral gap of a threshold graph depends predictably on the join/isolate sequence, and the Pólya model provides distributional control over that sequence, the convergence rate becomes analytically accessible rather than merely simulatable.
The deeper point: reinforcement and threshold structure are compatible. A network that grows by preferential attachment can still have the clean algebraic properties of one built by deterministic rules, provided the randomness enters through the right channel — the decision sequence, not the adjacency structure.