convergent graph sequence

[[concept]]

Sequence of Convergent Graphs

Let $\{G_n{\}}_n$ be a graph sequence such that ${\lim }_{n\to \infty }t(F,G_n)=\tilde{t}(F,W)$ for all motifs $F$ where

• $t(\cdot )$ is the graph homomorphism density
• $\tilde{t}(\cdot )$ is the graphon homomorphism density and
• $W$ is a graphon

Then $\{G_n\}$ is a convergent graph sequence with limit $W$.

Note on Initial Idea of Convergent Graph Sequence

This is a {“local”} idea of convergence since it checks to see if {sampled subgraphs converge "in distribution" up to the limiting object}. This is called {==left convergence since it deals with left homomorphism densities==} $t(F,G_n)$ and $\tilde{t}(F,W)$.

• (we count the occurrences of the motif within the graph/graphon) ^note-1

Note

This is not the only way to identify a (dense) convergent graph sequence. Another definition is based on the convergence of {==min-cuts or right homomorphisms==} $t(G_n,F)$ and $\tilde{t}(W,F)$.

• This is a {more “global”} notion of convergence that is used sometimes by graph theorists or in physics (micro-canonical ground state energy) ^note-2

Note

For dense graphs, left and right convergence are equivalent (for the metric we like) without proof.

Review

dsg

Mentions

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source

const { dateTime } = await cJS()
 
return function View() {
	const file = dc.useCurrentFile();
	return <p class="dv-modified">Created {dateTime.getCreated(file)}     ֍     Last Modified {dateTime.getLastMod(file)}</p>
}