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:\Omega \times \Omega \to [0,1]$ where $\Omega$ is a sample space with some probability measure $f$. We can always map $\Omega$ 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 $\Omega$ to the interval $[0,1]$ with a measure-preserving map.

Note

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

Example

From left to right:

1. block model with same community sizes
2. different community sizes, and
3. $w(u,v)=\exp \left(\frac{(u-v{)}^2}{{\sigma }^2}\right)$

• 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

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

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