Pólya Threshold Graphs

Jinghan Yu, Fady Alajaji, Bahman Gharesifard · 2026

Read Pólya Threshold Graphs by Jinghan Yu, Fady Alajaji, Bahman Gharesifard (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-18452.txt.

Introduction

Yu, Alajaji, and Gharesifard introduce Polya threshold graphs, a random graph model built from an urn process. Each new node is universal or isolated, set by a draw from a two-color Polya urn. The adjacency matrix has an explicit form in terms of the draw sequence. They derive the exact degree distribution, a decay centrality expectation, and the Laplacian spectrum. Consensus dynamics on these graphs are analyzed as an application.

Catalog record

CREATORJinghan Yu, Fady Alajaji, Bahman Gharesifard
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65228
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.18452

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Pólya Threshold Graphs Thanks: This work was funded in part by the Natural Sciences and Engineering Research Council (NSERC) of Canada. The authors are with the Department of Mathematics and Statistics, Queen’s University, Kingston, ON, Canada (Emails: {19jy98,fa,bahman.gharesifard}@queensu.ca). Jinghan Yu, Fady Alajaji, Bahman Gharesifard Abstract 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. Keywords: Pólya urn, random threshold graphs, Laplacian spectrum, degree distribution, decay centrality, consensus dynamics 1 Introduction In this paper, we define a class of threshold graphs in which nodes and edges are generated randomly and sequentially via a two-color Pólya urn process. At each time step, a draw from the urn determines whether the newly added node is an isolated node or a universal node, and each realization of this process produces a threshold graph. Such a construction yields a random threshold graph that provides a reinforcement-driven dependent extension of sequential threshold graph generation. Threshold graphs have been an important topic in both graph theory and network science. Following [ 11 , 18 , 3 ] , threshold graphs admit several equivalent characterizations, including a weight and threshold inequality and a sequential binary construction formed by repeatedly adding either universal or isolated nodes. They serve as fundamental models for systems exhibiting a nested structure and specific dynamic properties, see [ 14 ] . Furthermore, the rich algebraic structure of deterministic threshold graphs has motivated extensive studies on their Laplacian spectra, including the characterization of Laplacian controllability for multi-agent networks [ 1 ] , spanning trees [ 4 ] , critical groups [ 6 ] , and maximum Laplacian energy [ 9 ] . It is natural to consider random versions of threshold graphs. 23 have introduced natural equivalent models for random threshold graphs and used them to derive a variety of graph-theoretic properties. Diaconis et al. further studied the threshold graph limits and placed several random threshold graph models into a broader probabilistic framework [ 8 ] . Subsequent work has also examined structural questions such as connectivity in random threshold graph models [ 19 ] . Motivated by prior works on random threshold graphs, we introduce the class of Pólya threshold graphs, in which the binary node type construction is generated by a reinforced Pólya urn process rather than by an independent sampling rule. This is a natural choice because the sequential construction of threshold graphs is binary; meanwhile, the Pólya urn process also provides a canonical way to generate dependent sequences through reinforcement. Recent work has also shown that the Pólya urn process can be used to generate other classes of random graphs, such as preferential attachment graphs [ 29 ] . As a result, the model remains analytically tractable while allowing the node types to be generated through the dependent random process. Exploiting this tractability, our work is structured into three main parts, after providing background material on the Pólya urn model and random threshold graphs in Section 2 . First, in Section 3 , we present an explicit adjacency matrix representation and characterize the stochastic properties of the Pólya threshold graph, deriving the exact degree distribution for an arbitrary node V_{i} , together with its mean and variance, as well as an expression for the expected decay centrality score. Second, also in Section 3 , we establish the algebraic properties of the model, including the Laplacian matrix, the Laplacian spectrum and a corresponding eigenbasis. Third, in Section 4 , we study the discrete-time consensus dynamics on connected Pólya threshold graphs, compare the theory with simulations, and explore an extension to the finite-memory Pólya urn setting. Finally, we conclude the paper in Section 5 . 2 Preliminaries 2.1 Pólya urn model We start by recalling the setup for the classical Pólya urn model [ 22 ] . Consider an urn equipped with red and black balls. At the initial time t=0 , the urn has R>0 red balls and B>0 black balls, for a total of T=R+B initial balls. At each discrete time step t\geq 1 , we draw a ball from the urn at random, and place it back along with \Delta>0 extra balls of the same color. We allow the number of balls to be a positive real number, since draws depend only on color proportions; allowing positive real ball counts does not alter the model. We naturally define the draw indicator random variable Z_{t} at time t as follows \displaystyle Z_{t}=\begin{cases}1&\text{if draw at time $t$ is red,}\\ 0&\text{if draw at time $t$ is black.}\end{cases} (1) It is well-known that the stochastic process \{Z_{t}\}_{t=1}^{\infty} is exchangeable (and thus strictly stationary), see [ 22 , 2 ] , where by exchangeability we mean that for any positive integer \ell , the draw variables Z_{1},Z_{2},\ldots,Z_{\ell} have an invariant joint distribution with respect to all permutations of the indices 1,2,\ldots,\ell . Specifically, following [ 2 ] , the joint probability of observing a specific length- n sequence z^{n}=(z_{1},\ldots,z_{n})\in\{0,1\}^{n} with exactly k=\sum_{i=1}^{n}z_{i} red draws is given by \displaystyle P(Z_{1}=z_{1},\cdots,Z_{n}=z_{n})=\frac{\prod_{i=0}^{k-1}(R+i\Delta)\prod_{j=0}^{n-k-1}(B+j\Delta)}{\prod_{m=0}^{n-1}(R+B+m\Delta)}. (2) By defining the urn’s initial red balls proportion \rho=\frac{R}{R+B} and the reinforcement parameter \delta=\frac{\Delta}{R+B} , the joint distribution above can be written as \displaystyle P(Z_{1}=z_{1},\cdots,Z_{n}=z_{n})=\frac{\Gamma(\frac{1}{\delta})\Gamma(\frac{\rho}{\delta}+k)\Gamma(\frac{1-\rho}{\delta}+n-k)}{\Gamma(\frac{\rho}{\delta})\Gamma(\frac{1-\rho}{\delta})\Gamma(\frac{1}{\delta}+n)}, (3) where \Gamma(x)=\int_{0}^{\infty}t^{x-1}e^{-t}dt is the Gamma function . The above distribution exhibits a Beta-Binomial structure, which will be instrumental in deriving the properties of our model in Section 3 . The Pólya urn-based draw process \{Z_{t}\}_{t=1}^{\infty} enjoys many other interesting properties, including the fact that its sample average \frac{1}{n}\sum_{i=1}^{n}Z_{i} for n\in\mathbb{Z}_{>0} converges almost surely as n grows without bound to a random variable governed by the Beta distribution, \text{Beta}\big(\frac{\rho}{\delta},\frac{1-\rho}{\delta}\big) , with parameters \frac{\rho}{\delta} and \frac{1-\rho}{\delta} ; in particular, this implies that the draw process is non-ergodic, see [ 22 ] . 2.2 Random threshold graphs In this section, we introduce threshold graphs , following [ 18 ] . An undirected graph \mathbf{G}_{n} with n nodes is a pair (\mathbf{V}_{n},\mathbf{E}_{n}) , where \mathbf{V}_{n} is the node set of size n , and \mathbf{E}_{n}\subseteq\mathbf{V}_{n}\times\mathbf{V}_{n} is the edge set. Moreover, we assume that a graph can have self-loops, i.e., an edge from a node v to itself so that (v,v)\in\mathbf{E}_{n} . Throughout this paper, all graphs are undirected; when we write (u,v)\in\mathbf{E} , we also mean (v,u)\in\mathbf{E} . Definition 1 . Given a size- n graph \mathbf{G}_{n}=(\mathbf{V}_{n},\mathbf{E}_{n}) , where \mathbf{V}_{n}=\{v_{1},\ldots,v_{n}\} ,

Read the complete text