A graphon is a symmetric, Lebesgue-measurable function . Graphons are the limiting objects for sequences of finite simple graphs with respect to the cut metric , where the infimum is taken over all pairs of invertible, measure-preserving transformations of , and the supremum is taken over all pairs of measurable subsets of . In this notebook, we explore the subject of graphons using the

W:[0,1][0,1]

2

δ(W,U)=infsup∫∫(W(ϕ(x),ϕ(y))-U(ψ(x),ψ(y)))xy

□

ϕ,ψ

S,T

ST

[0,1]

[0,1]

Wolfram Language

. For a more thorough introduction to graphons, including further exposition on some of the examples presented here, see “What Is a Graphon?”

by Daniel Glasscock.Clickinthecode,thenholdandpresstorunit.

We start by defining two graphons that we’ll use throughout the notebook.

graphon1[x_,y_]:=√(x*y)graphon2[x_,y_]:=1-Max[x,y]

In[1]:=

Graphons are graphically represented by shading the unit square. The point , located units down and units to the right of the upper-left corner, is shaded based on where lies between 0 (white) and 1 (black). The DensityPlot function follows the normal Cartesian coordinate system of the plane and also sets 0 as black and 1 as white, so a simple transformation is needed inside the function.

(x,y)

x

y

W(x,y)

plot[graphon_]:=DensityPlot[Abs[1-graphon[1-y,x]],{x,0,1},{y,0,1},ColorFunction->GrayLevel,FrameTicksFalse]

In[3]:=

Map[plot,{graphon1,graphon2}]

In[4]:=

Out[4]=

Every -vertex graph can be represented as the graphon that is drawn by dividing the unit square into an grid of equally sized blocks and shading the blocks pure black if the corresponding entry in the adjacency matrix is 1 and white if the entry is 0. We call this the “pixel picture” of the graph.

n

nn

graph=Graph[{1,2,3,4,5},{12,23,31,45},VertexLabels->"Name"];am=AdjacencyMatrix[graph];{graph,MatrixForm[am],ArrayPlot[am]}

In[5]:=

Out[7]=

Hence the following code formally converts a graph to a graphon.

graphToGraphon[graph_]:=With[{am=Normal[AdjacencyMatrix[graph]],n=VertexCount[graph]},Function[{x,y},Indexed[am,{Max[⌈n*x⌉,1],Max[⌈n*y⌉,1]}]]]

In[8]:=

We apply it to our graph and then plot it.

plot[graphToGraphon[graph]]

In[9]:=

We now create the graph and its pixel picture.

We put everything together in the following function.

Associate each vertex of our graph with a variable of integration.

We put everything together in the following function.

Recover the vertices from the partition.

Associate each vertex with the index of its subset in the partition.

Convert these vertex pairs into edges and create the graph.

Put everything together into a single function.