The Pólya Threshold

Build a graph one node at a time. At each step, draw from a Pólya urn. If the draw says “universal,” connect the new node to every existing node. If it says “isolated,” connect it to nothing. The Pólya urn has reinforcement: each outcome makes itself more likely next time. So the graph develops momentum — a run of universal nodes breeds more universal nodes, a run of isolated nodes breeds more isolated ones.

The resulting random graph has threshold structure: nodes are either maximally connected or disconnected, with nothing in between. The degree distribution, centrality measures, and spectral properties all follow from the urn dynamics in closed form.

The Laplacian spectrum is especially clean. Because each node is either universal or isolated, the Laplacian matrix has a restricted structure that admits explicit eigenvector computation. This makes the model analytically tractable in a way that most random graph models are not — you can write down the eigenvalues, not just estimate them.

The application to consensus dynamics exploits this tractability. Consensus on networks — the process by which agents with different opinions converge to agreement — depends on the spectral gap of the graph Laplacian. For Pólya threshold graphs, the spectral gap is determined by the urn parameters, which means the rate of consensus formation is directly controlled by the reinforcement strength.

The model captures a specific kind of network formation: rich-get-richer dynamics where influence is all-or-nothing. No partial connections, no intermediate status. The binary structure is extreme but analytically productive — it reveals how preferential attachment interacts with spectral properties in a setting simple enough for exact results.