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 (W,U)=∫(W(ϕ(x),ϕ(y))-U(ψ(x),ψ(y)))xy, 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 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.

W:[0,1]

2

[0,1]

δ

□

inf

ϕ,ψ

sup

S,T

∫

ST

[0,1]

[0,1]

Clickinthecode,thenholdandpresstorunit.

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

In[1]:=

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

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)

In[3]:=

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

In[4]:=

Map[plot,{graphon1,graphon2}]

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

In[5]:=

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

Out[7]=

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

In[8]:=

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

We apply it to our graph and then plot it.

In[9]:=

plot[graphToGraphon[graph]]

Out[9]=

For any graphon , we can construct a sequence of finite labeled graphs that converges to W almost surely. Our vertex set will be a set of real numbers chosen randomly from , which we sort into ascending order so that the pixel picture of the graph resembles the shading of the graphon.

W

n

[0,1]

In[10]:=

vxs=Sort[RandomReal[{0,1},15]]

Out[10]=

{0.0948346,0.11277,0.212622,0.322393,0.351514,0.401797,0.451647,0.509284,0.517305,0.560901,0.5662,0.652029,0.728365,0.938261,0.960071}

We let a pair of vertices be adjacent with probability , which can be implemented by comparing to a random real from . Here we set .

(x,y)

W(x,y)

W(x,y)

[0,1]

W=graphon1

In[11]:=

pairs=Select[Subsets[vxs,{2}],Function[pair,Apply[graphon1,pair]>RandomReal[{0,1}]]]

Out[11]=

{{0.11277,0.517305},{0.11277,0.5662},{0.11277,0.960071},{0.212622,0.322393},{0.212622,0.401797},{0.322393,0.560901},{0.322393,0.5662},{0.322393,0.938261},{0.351514,0.517305},{0.351514,0.938261},{0.351514,0.960071},{0.401797,0.451647},{0.401797,0.560901},{0.401797,0.5662},{0.401797,0.652029},{0.401797,0.728365},{0.401797,0.938261},{0.451647,0.517305},{0.451647,0.560901},{0.451647,0.5662},{0.451647,0.960071},{0.509284,0.517305},{0.509284,0.560901},{0.509284,0.5662},{0.509284,0.728365},{0.509284,0.938261},{0.509284,0.960071},{0.517305,0.5662},{0.517305,0.652029},{0.517305,0.728365},{0.517305,0.938261},{0.517305,0.960071},{0.560901,0.652029},{0.560901,0.728365},{0.560901,0.938261},{0.560901,0.960071},{0.5662,0.728365},{0.5662,0.938261},{0.652029,0.728365},{0.652029,0.938261},{0.652029,0.960071},{0.728365,0.938261},{0.728365,0.960071},{0.938261,0.960071}}

We now create the graph and its pixel picture.

In[12]:=

edges=Apply[UndirectedEdge,pairs,{1}];With[{graph=Graph[vxs,edges]},{graph,ArrayPlot[AdjacencyMatrix[graph]]}]

Out[13]=

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.