Abstract: Graphons are graph limits, and can be used to generate new graphs with desired properties. Intuitively, a graphon can be obtained by scaling the adjacency matrix to the unit square and taking its limit. However, as a result of the Aldous-Hoover theorem, traditional graphons can only represent dense graphs, because sparse graphs converge to the zero graphon.  Notwithstanding this challenge, several approaches have been proposed to model sparse graphs, often relying on sophisticated mathematical machinery.

In this talk we present a simple construction to generate sparse graphs using line graphs. Line graphs map edges to vertices.  We show that a subset of sparse graphs has dense line graphs, allowing them to be modelled via the graphon of their line graphs. Furthermore, we propose a mixture that combines a dense graph sequence generated from a standard graphon W, with a sparse graph sequence generated from a line graph graphon U. This (U,W) mixture can generate both sparse and dense graphs depending on the mixture properties. In addition, sparse graphs generated by the (U,W) mixture matches the structure of many real-world graphs including social networks featuring large hubs alongside tightly knit communities.