template graph

[[concept]]

template graph

A template graph $G_{n}$ is a way to sample a graph from a graphon. The nodes are defined by partitioning $[0, 1]$ in a grid (regular partition) in the same way we partitioned for induced graphons:

I_{k} = {\begin{cases} [\frac{k - 1}{n}, \frac{k}{n} [1 \leq k \leq n - 1 \\ [\frac{n - 1}{n}, 1] k = n \end{cases}

So that $I_{1} \cup I_{2} \cup \dots \cup I_{n} = [0, 1]$ and the node labels are $u_{j} = \frac{j - 1}{n}$ for each $j$ .

The adjacency matrix is then given as

[A_{n}]_{i j} = W (u_{i}, u_{j})

Where $W$ is the graphon that we sample from.

This is a complete, weighted graph with edge weights coming from the graphon evaluated at each node pair $(u_{i}, u_{j}) \in [0, 1]^{2}$ .

This is the simplest way to sample a graph. We can think of it as the graph sampling counterpart to inducing a graphon.

Review

#flashcards/math/dsg

Q: How do we define the nodes in a template graph?
-?-
A: We partition $[0, 1]$ in a grid (regular partition) in the same way we partitioned for induced graphons $I_{k} = {\begin{cases} [\frac{k - 1}{n}, \frac{k}{n} [1 \leq k \leq n - 1 \\ [\frac{n - 1}{n}, 1] k = n \end{cases}$

We define a template graph's adjacency matrix as {-as||$$[A_{n}]{ij} = W(u,u_{j})$$-}
which results in a {ha||complete, weighted graph.||characteristics}

We can think of a template graph as the {a||graph sampling} counterpart to {a||inducing a graphon}.

Mentions

File
template graphs converge to the graphon
ways to sample graphs from graphons
weighted graph (sample)
2025-03-26 lecture 15

Created 2025-03-26 Last Modified 2025-05-30