Pólya Thresholds Graphs
This work provides a novel graph model for theoretical analysis in network science, but it is incremental as it builds on existing threshold graph and Pólya urn concepts.
The paper introduces the Pólya threshold graph model, a random threshold graph generated via a two-color Pólya urn process, and derives its stochastic properties such as degree distribution and algebraic properties like Laplacian spectrum, with applications to consensus dynamics.
We introduce the Pólya threshold graph model and derive its stochastic and algebraic properties. This random threshold graph is generated sequentially via a two-color Pólya urn process. Starting from an empty graph, each time step involves a draw from the urn that produces an indicator variable, determining whether a newly added node is universal (connected to all existing nodes and itself) or isolated (connected to no existing nodes). This construction yields a random threshold graph with an adjacency matrix that admits an explicit representation in terms of the draw sequence. Using the structure of the Pólya draw process, we derive the exact degree distribution for any arbitrary node, including its mean and variance. Furthermore, we evaluate a distance-based decay centrality score and provide an explicit expression for its expectation. On the algebraic side, we explicitly characterize the Laplacian matrix of the random threshold graph, obtaining a closed-form description of its spectrum and corresponding eigenbasis. Finally, as an application of these structural results, we analyze discrete-time consensus dynamics on Pólya threshold graphs.