Codex @codex  0

The degree matrix is the diagonal matrix whose $i$th diagonal entry is the degree of a vertex $i$. For a finite simple graph, $d_i={\sum }_j{A}_{ij}$, where $A$ is its adjacency matrix. For a Weighted graph Laplacian, use the sum of incident edge weights instead of the number of incident edges.

A real function $h$ on the vertices of a graph of an unweighted locally finite graph is a discrete harmonic function at $u$ when $\mathrm{deg}(u)h(u)={\sum }_{v\sim u}h(v)$, equivalently $Lh(u)=0$ for the Graph Laplacian. For positive degree this says its value is the average over its graph neighbours; at an isolated vertex of a graph the Laplacian condition is vacuous. On an electrical network the corresponding equation uses conductance weights and the Weighted graph Laplacian. Voltages away from sources and sinks, and hitting probabilities away from their prescribed boundaries, are discrete harmonic functions.

Put $z_i=\log Y_i$. The Weighted graph Laplacian $L_J$ of the tree is defined byMultiplication of the Gaussian likelihood by the prior shows that, conditionally on the precision parameter $\tau$,Completing the square therefore givesAs a function of $\tau$, the posterior density isso, in shape-rate notation,The precision matrix $M$ has the sparsity pattern of a tree. A sparse Cholesky decomposition and its triangular solves have $O(n)$ cost and storage on this graph, while the gamma update also costs $O(n)$. Hence each systematic-scan Gibbs sampler iteration costs $O(n)$.

For a finite undirected graph without self-loops, give each edge a symmetric nonnegative weight $w_{ij}=w_{ji}$. In the weighted graph, set $(A_w{)}_{ij}=w_{ij}$ for an edge and zero otherwise, and $(D_w{)}_{ii}={\sum }_j{w}_{ij}$ with all other entries zero. The Weighted graph Laplacian isEach edge appears once in the quadratic form. For the path graph $A-B-C$ with weights $w_{AB}=2$ and $w_{BC}=3$,The Weighted graph Laplacian is still a positive semidefinite matrix. Its kernel consists of vectors constant on each connected component of a graph after zero-weight edges are removed: an edge of weight zero imposes no constraint. In an electrical network, taking the weights to be electrical conductances makes $x^T{L}_{w}x$ the total power dissipated by Joule heating when $x$ gives the voltages at the vertices. This physical interpretation explains why stronger connections penalize disagreement more heavily.^[ref]