graphon

[[concept]]

graphon

A graphon is a symmetric, bounded, measurable function

W : [0, 1]^{2} \to [0, 1]

ie, it is a bounded kernel (weighting function).

We can think of a graphon as a graph with an uncountable number of nodes $u \in [0, 1]$ and edges $(u, v)$ with weights $W (u, v)$ . Alternatively, we can think of a graphon as a model that we can use to sample graphs.

Note

A more general definition is

W : Ω \times Ω \to [0, 1]

where $Ω$ is a sample space with some probability measure $f$ . We can always map $Ω$ onto $[0, 1]$ using a measure-preserving map (as long as the CDF of $f$ is strictly monotone), so we can use $[0, 1]^{2}$ WLOG.

Exercise

Show that if the CDF of $f$ is strictly monotone, we can map $Ω$ to the interval $[0, 1]$ with a measure-preserving map.

Note

The codomain of $W$ may be $(0, B]$ where $B \in R < + \infty$ . However, we usually have $B = 1$ since $W (u, v)$ often represents a probability.

^note-2

Example

From left to right:

block model with same community sizes
different community sizes, and
$w (u, v) = \exp (\frac{(u - v)^{2}}{σ^{2}})$
^example

finish note 2 once lecture 14 notes are released ➕ 2025-03-24 📅 2025-03-27 ✅ 2025-03-24
finish examples once lecture 14 notes are released 📅 2025-03-27 ✅ 2025-03-24

Example

Graphon as a limiting object for some sequence of graphs

Graphon as generating object for finite graphs

Review

#flashcards/math/dsg

We can think of a graphon as a graph with {==ass||an uncountable number of nodes $u \in [0, 1]$ ==} and {-has||edges $(u, v)$ -} with {-hha||weights $W (u, v)$ -}.

A graphon is a {symmetric, bounded, measurable||(3 properties)} function

References

Mentions

const modules = await cJS()

const COLUMNS = [  
	{ id: "Name", value: page => page.$link },  
	{ id: "Last Modified", value: page => modules.dateTime.getLastMod(page) },
];  
  
return function View() {  
	const current = dc.useCurrentFile();
// Selecting `#game` pages, for example. 
	let queryString = `@page and linksto(${current.$link})`;
	let pages = dc.useQuery(queryString);
	
	// check types
	pages = pages.filter( (p) => !modules.typeCheck.checkAll(p, current) ).sort()
	
	
	return <dc.Table columns={COLUMNS} rows={pages} paging={20}/>;  
}

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>
}