Line graphs
Suppose\(G\) is a graph. Then theline graph of\(G\), commonly denotedby\(L(G)\) maps edges of\(G\) to vertices of\(L(G)\) and two vertices in\(L(G)\) are connected if the original edgesin\(G\) share a common vertex. Here’san example.
g1<-make_star(4,mode ="undirected")g1<-add_vertices(g1,1)g1<-add_edges(g1,c(4,5))lg1<-make_line_graph(g1)oldpar<-par(mfrow =c(1,2))plot(g1,vertex.label =NA,edge.label =c(1,2,3,4),main ="Graph G")plot(lg1,vertex.label =c(1,2,3,4),vertex.size =20,main ="Line graph L(G)")
Line graphs of star graphs
The key is that line graphs of stars are complete graphs. In theexample below each edge of graph\(G\)is a vertex in\(L(G)\). Two verticesin\(L(G)\) are connected if thecorresponding edges in\(G\) share avertex.
st<-make_star(10,mode ="undirected")lgr_st<-make_line_graph(st)oldpar<-par(mfrow =c(1,2))plot(st,vertex.label =NA,main ="Star graph G")plot(lgr_st,vertex.label =NA,main ="Line graph L(G) of a star")
Sparse graphs
A sequence of graphs is sparse if the edges grow subquadraticallywith the nodes. Star graphs are the ultimate sparse graphs, because astar of\(n\) nodes has\(n-1\) edges. A graph sequence is dense ifthe edges grow quadratically with the nodes. Erdos-Renyi graphs\(G(n,p)\) with a fixed edge probability\(p\) are dense. This can be seen fromthe edge density. Let’s generate a sequence of star graphs and asequence of Erdos-Renyi graphs and see this in action.
stardensity<- gnpdensity<-rep(0,20)for(iin1:20){ n<- i*100 gr1<-sample_gnp(n,p =0.1) gnpdensity[i]<-edge_density(gr1) gr2<-make_star(n,mode ="undirected") stardensity[i]<-edge_density(gr2)}gnpdensity#> [1] 0.10505051 0.10653266 0.10218506 0.10189223 0.09940681 0.10072899#> [7] 0.10013897 0.10083542 0.10009393 0.10003403 0.09964596 0.10057270#> [13] 0.10012080 0.09985500 0.10008984 0.10013290 0.09979573 0.10016799#> [19] 0.09999778 0.09971936stardensity#> [1] 0.020000000 0.010000000 0.006666667 0.005000000 0.004000000 0.003333333#> [7] 0.002857143 0.002500000 0.002222222 0.002000000 0.001818182 0.001666667#> [13] 0.001538462 0.001428571 0.001333333 0.001250000 0.001176471 0.001111111#> [19] 0.001052632 0.001000000
We see that the density of stars goes to zero whereas the density ofGNP graphs hover around 0.1, because we have used the edge probabilityas 0.1.
Graphons
Graphons are graph limits. Suppose we have a graph\(G\). The empirical graphon of\(G\) is when we scale the adjacency matrixto the unit square and color the small squares that correspond to onesin the adjacency matrix in black. Here we plot the empirical graphon ofa star graph with 10 nodes.
gr<-make_star(10,mode ="undirected")emp<-empirical_graphon(gr)plot_graphon(emp)+coord_fixed()
Graphons of sparse graphs
The problem is graphons of sparse graphs are zero. Graphons aregenerally denoted by the letter\(W\).And if the graphs are sparse then\(W =0\). That is, the empirical graphons converge to zero. Here,we’re a bit handwavy about convergence (actually, the convergence iswith respect to the cut metric, but let’s let’s not discuss that).
gr<-make_star(20,mode ="undirected")emp<-empirical_graphon(gr)g1<-plot_graphon(emp)+coord_fixed()+ggtitle('n = 10')gr<-make_star(100,mode ="undirected")emp<-empirical_graphon(gr)g2<-plot_graphon(emp)+coord_fixed()+ggtitle('n = 100')gr<-make_star(200,mode ="undirected")emp<-empirical_graphon(gr)g3<-plot_graphon(emp)+coord_fixed()+ggtitle('n = 200')gridExtra::grid.arrange(g1, g2, g3,nrow =1)
As\(n \to \infty\), there are lessblack parts in the empirical graphon and it converges to zero. When thegraphon is zero, we cannot sample from it; it is not useful anymore. Sowhat do we do?
Graphons of line graphs
For a subset of sparse graphs, such as the star graphs, their linegraphs are dense. We discuss this in detail in(Kandanaarachchi and Ong 2024). The main exampleis star graphs.
gr1<-make_star(10,mode ="undirected")gr<- gr1%du% gr1lgr<-make_line_graph(gr)emp<-empirical_graphon(lgr)g1<-plot_graphon(emp)+coord_fixed()+ggtitle('n = 20')gr1<-make_star(50,mode ="undirected")gr<- gr1%du% gr1lgr<-make_line_graph(gr)emp<-empirical_graphon(lgr)g2<-plot_graphon(emp)+coord_fixed()+ggtitle('n = 100')gr1<-make_star(100,mode ="undirected")gr<- gr1%du% gr1lgr<-make_line_graph(gr)emp<-empirical_graphon(lgr)g3<-plot_graphon(emp)+coord_fixed()+ggtitle('n = 200')gridExtra::grid.arrange(g1, g2, g3,nrow =1)
For the above example of two stars, the line graphs are dense andconverge to a non-zero graphon.
Janson’s theorem
Janson(Janson 2016) proved that allline graph limits are disjoint clique graphs. This is a very importanttheorem for us because it tells us what the structure of line graphlimits are. Janson explains that line graph limits can be written as asequence of numbers\((p_1, p_2,\ldots)\) such that\(\sum_i p_i \leq1\) and\(p_i \geq 0\). The\(p_i\) gives the width of each blackbox in the graphon.
Generating stars as inverse line graphs
From a line graph limit we can generate a disjoint union of cliquegraphs like this.
wts<-c(0.5,0.3,0.2)U<-line_graphon(wts)gr<-sample_graphon(U,n =100)plot(gr,vertex.size =1,edge.color ="lightgray",# Light colored edgesvertex.label =NA,vertex.color ="lightblue")
The inverse line graphs of disjoint clique graphs are star graphs.And star graphs are sparse. We can generate star graphs using theweights or the partition\((p_1, p_2,\ldots)\).
grsp<-generate_star_union(wts,n =100)plot(grsp,edge.curved =0.3,vertex.size =1,edge.color ="lightgray",# Light colored edgesvertex.label =NA,vertex.color ="lightblue")
This is how the sparse part of the\((U,W)\)-mixture graph is generated. Thevignette atArticles/Getting Started explains the mixtureprocedure.
References
Janson, Svante. 2016.“Graph Limits and HereditaryProperties.”European Journal of Combinatorics 52:321–37.
Kandanaarachchi, Sevvandi, and Cheng Soon Ong. 2024.“Graphons ofLine Graphs.”arXiv Preprint arXiv:2409.01656.