Expectation and Variance of the Degree of a Node in Random Spanning Trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917806818197504 |
|---|---|
| author | Sanmartín, Enrique Fita Schnörr, Christoph Hamprecht, Fred A. |
| author_facet | Sanmartín, Enrique Fita Schnörr, Christoph Hamprecht, Fred A. |
| contents | We consider a Gibbs distribution over all spanning trees of an undirected, edge weighted finite graph, where, up to normalization, the probability of each tree is given by the product of its edge weights. Defining the weighted degree of a node as the sum of the weights of its incident edges, we present analytical expressions for the expectation, variance and covariance of the weighted degree of a node across the Gibbs distribution. To generalize our approach, we distinguish between two types of weight: probability weights, which regulate the distribution of spanning trees, and degree weights, which define the weighted degree of nodes. This distinction allows us to define the weighted degree of nodes independently of the probability weights. By leveraging the Matrix Tree Theorem, we show that these degree moments ultimately depend on the inverse of a submatrix of the graph Laplacian. While our focus is on undirected graphs, we demonstrate that our results can be extended to the directed setting by considering incoming directed trees instead. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_13472 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Expectation and Variance of the Degree of a Node in Random Spanning Trees Sanmartín, Enrique Fita Schnörr, Christoph Hamprecht, Fred A. Discrete Mathematics Combinatorics 05C05, 05C07 (Primary) 05C20, 05C22, 05C30, 05C80 (Secondary) We consider a Gibbs distribution over all spanning trees of an undirected, edge weighted finite graph, where, up to normalization, the probability of each tree is given by the product of its edge weights. Defining the weighted degree of a node as the sum of the weights of its incident edges, we present analytical expressions for the expectation, variance and covariance of the weighted degree of a node across the Gibbs distribution. To generalize our approach, we distinguish between two types of weight: probability weights, which regulate the distribution of spanning trees, and degree weights, which define the weighted degree of nodes. This distinction allows us to define the weighted degree of nodes independently of the probability weights. By leveraging the Matrix Tree Theorem, we show that these degree moments ultimately depend on the inverse of a submatrix of the graph Laplacian. While our focus is on undirected graphs, we demonstrate that our results can be extended to the directed setting by considering incoming directed trees instead. |
| title | Expectation and Variance of the Degree of a Node in Random Spanning Trees |
| topic | Discrete Mathematics Combinatorics 05C05, 05C07 (Primary) 05C20, 05C22, 05C30, 05C80 (Secondary) |
| url | https://arxiv.org/abs/2409.13472 |