Pólya Thresholds Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915874290532352 |
|---|---|
| author | Yu, Jinghan Alajaji, Fady Gharesifard, Bahman |
| author_facet | Yu, Jinghan Alajaji, Fady Gharesifard, Bahman |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18452 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Pólya Thresholds Graphs Yu, Jinghan Alajaji, Fady Gharesifard, Bahman Information Theory Social and Information Networks Probability 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. |
| title | Pólya Thresholds Graphs |
| topic | Information Theory Social and Information Networks Probability |
| url | https://arxiv.org/abs/2603.18452 |