Centered graph matrices and reference degree

PDF p. 6: Section 1.2

Let $G=(V,E)$ be a finite undirected graph with $n=\mathrm{\mid }V\mathrm{\mid }>0$, adjacency matrix $A$, degree matrix $D$, and graph Laplacian $L=D-A$, using the conventions of Adjacency, degrees, graph Laplacian, and spectral notation. Thus $D_{xx}={\sum }_y{A}_{xy}$ and a self-loop contributes once to this sum. Let $I$ be the identity matrix and $J$ the all-ones matrix. For a real reference parameter $d^{\ast }$, define the centered adjacency matrix ${\mathrm{\Delta }}_A=A-(d^{\ast }\mathrm{/}n)J$, the centered diagonal degree matrix ${\mathrm{\Delta }}_D=D-d^{\ast }I$, and the centered Laplacian matrix ${\mathrm{\Delta }}_L={\mathrm{\Delta }}_D-{\mathrm{\Delta }}_A=L-d^{\ast }I+(d^{\ast }\mathrm{/}n)J$.

The article describes its intended selection of $d^{\ast }$ as an “expected average degree” of $G$. The article chooses $d^{\ast }=d$ when $G$ is $d$-regular, meaning every vertex has degree $d$. For the Erdős–Rényi graph $G(n,p)$, whose distinct possible edges occur independently with probability $p$ and which has no loops, it chooses $d^{\ast }=pn$ (Erdős–Rényi random graph and high probability). This is the reference parameter; under that loop-free convention the exact expected degree is $(n-1)p$.

Given: The graph and real reference parameter in the definition, and the stated random-graph law when the random example is considered.

Goal: Verify that the centered matrices and their displayed identity are well defined, and clarify the reference choices.

1.1 Since $n>0$, the scalar $d^{\ast }\mathrm{/}n$ exists. The matrices in [F1] have matching dimensions, so the three displayed sums and differences define matrices uniquely. Substituting $L=D-A$ gives $(D-d^{\ast }I)-(A-(d^{\ast }\mathrm{/}n)J)=L-d^{\ast }I+(d^{\ast }\mathrm{/}n)J$. By [F2], the term $(d^{\ast }\mathrm{/}n)J$ is $d^{\ast }$ times the projection onto constant vectors. [given, F1, F2, algebra]

1.2 For the random example, take the finite probability space $(\mathrm{\Omega },w)$ of simple graphs on $[n]$ with the law in [F3]. For distinct vertices $x,y$, let $X_{xy}$ be the indicator of the edge $\{x,y\}$. Since it is $1$ on the edge-present event and $0$ elsewhere, [F4] gives $\mathbb{E}[X_{xy}]={\sum }_{\omega :X_{xy}(\omega )=1}w(\omega )=p$ by [F3]. [given, F3, F4, algebra]

2.1 For a $d$-regular graph the common degree $d$ specifies the stated reference value. For $G(n,p)$, the degree of a fixed vertex $x$ is $d(x)={\sum }_{y\mathrm{\ne }x}{X}_{xy}$ by [F1] and the absence of loops. These are $n-1$ real indicators on the same finite probability space, so [F5] and step 1.2 give $\mathbb{E}[d(x)]={\sum }_{y\mathrm{\ne }x}\mathbb{E}[X_{xy}]=(n-1)p$, including the empty sum when $n=1$. Thus $pn$ is the stated reference choice, not an assertion that this exact expectation equals $pn$. Both reference choices are valid real parameters in the preceding construction. [given, F1, F3, F5, step 1.1, step 1.2, algebra] ∎

The notation and the two reference choices are attributed to Expander graphs are globally synchronizing, Section 1.2. The justification uses the stated suppliers and elementary calculation.