Sec. \[sec:spectral\].

Finally, we remark that the algebraic Laplacian should not be confused with the normalized Laplacian ${\mathcal{L}} = \Delta^{ -\frac{1}{2}}L\Delta^{-\frac{1}{2}}$, which is frequently seen in the network theory literature. The algebraic properties discussed in the next section (such as associativity of the hierarchical product) apply to the adjacency matrix as well as the algebraic Laplacian, but not to the normalized Laplacian.

Hierarchical Product {#sec:hpdef}
--------------------

Here, we will define the hierarchical product and illustrate it with simple examples. For a fuller exposition, see Ref. [@Barriere2009], where the hierarchical product of graphs was introduced. Note that, in some contexts, the hierarchical product is also known as the rooted product [@Godsil1978].

Given a graph $G$, let ${\mathbbm{1}}_G$ denote the identity matrix on $n=|V|$ vertices. We will denote by $D_G$ an $n\times n$ diagonal matrix with 1 as the first entry and zero everywhere else. Note that there is no natural notion of order to graph vertices, so the choice of “first” vertex must be specified explicitly. Graphs with such a specified first vertex are called *rooted graphs* [@Harary1955]. We write these matrices as $$\begin{aligned}
{\mathbbm{1}}= \begin{pmatrix}1 & & & & \\ & 1 & & & \\ & & 1 & 