Two graphons are better than one! Graph generation with graphon mixtures

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.

1. University of Melbourne, Applied Probability Group Seminar, 15 September 2025
Sevvandi Kandanaarachchi, Cheng Soon Ong
CSIRO’s Data61
Two graphons are better than one!
Graph generation with graphon mixtures
1

2. Graphons
2

3. What are graphons?
•Graph limits
•Scale the adjacency matrix to the unit square (empirical graphons) and take a limit
Erdos-Renyi graphs
Growing uniform attachment graphs
Bi-partite graphs
Glasscock, D. (2015). What is... a graphon.  Notices of the AMS, 62(1), 46-48.
3

4. Convergence
•Homomorphism density convergence: A graph sequence is convergent if the
homomorphism densities converge for any simple graph
•Cut metric: Given two graphons and , the cut metric is defined as
where is a measure preserving bijection from to
and cut norm is defined as
•Why ? To account for graph isomorphisms
•Convergence in homomorphism density is equivalent to convergence in cut-metric (Borgs et al
2011)
{G
n
}
n
t(F,G
n
) F
W
1
W
2
δ
□
(W
1
,W
2
)=inf
φ
W
1
−W
φ
2
□
φ [0,1][0,1]
∥W∥
□
=sup
S,T
∫
S×T
W(x,y)dxdy
φ
Borgs, C., Chayes, J., Lovász, L., Sós, V., & Vesztergombi, K. (2011). Limits of randomly grown graph sequences. European Journal of Combinatorics, 32(7), 985-999
4

5. How can we use graphons?
•To generate new graphs (sample graphs)
•Sample unseen graphs at future time points
•Then compute graph properties
•Sampling - a graph with nodes labeled
•Sample random points from the interval -
•For every the value is the edge probability
•Toss a coin with probability , and connect the edge between and if you get heads
n {1,2,…,n}
n [0,1]{r
1
,r
2
,…,r
n
}
(r
i
,r
j
) W(r
i
,r
j
)=p
p ij
r
i
r
j
5

6. Dense and sparse graphs
•Consider a graph sequence , where has nodes and edges.
•
Dense graphs:
•Edges grow quadratically with nodes
•Graph sequences with strictly positive edge-density limits
•
Sparse graphs:
•Graph sequences with edge-density going to zero
•Edges grow subquadratically with nodes
{G
n}
n G
nn m
lim inf
n→∞
m
n
2
=c>0
lim
n→∞
m
n
2
=0
Dense
Sparse
6

7. A bit on
exchangeability
Discrete Continuous
1D (Sequences/
Point processes)
de Finetti (1931)Bühlmann (1960)
2D (Arrays Joint/
separate)
Aldous (1981) and
Hoover (1979)
Kallenberg (1990)
de Finetti, B. (1931) Funzione caratteristica di un fenomeno aleatorio. Atti R. Acad. Nazn. Lino, Ser. 6, 4, 251- 299.

Bühlmann, H. (1960). Austauschbare stochastische Variabeln und ihre Grenzwertsätze (Doctoral dissertation, ETH Zurich)
Aldous, D. J. (1981). Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 11(4), 581-598.
Hoover, D. N. (1979). Relations on Probability Spaces and Arrays of. Preprint, Institute for Advanced Study, Princeton
Kallenberg, O. (1990). Exchangeable random measures in the plane. Journal of Theoretical Probability, 3(1), 81-136.
7
Exchangeability: order of the variables
does not matter

8. Exchangeable binary matrices
•Aldous-Hoover representation theorem



with , and a random function
•Infinite exchangeable binary matrices imply a mixture model representation exist
•For undirected graphs, this mixture is specified by the graphon (Borgs et al 2008, Lovász et al 2006)
•For graphs the connection to Aldous-Hoover made by Diaconis & Janson
X
ij
|U
i,U
j,W∼Ber(W(U
i,U
j))
U
i
iid
∼Unif(0,1)W:[0,1]
2
→[0,1]
Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T., & Vesztergombi, K. (2008). Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Advances in Mathematics, 219(6),
1801-1851.
Janson, S., & Diaconis, P. (2008). Graph limits and exchangeable random graphs. Rendiconti di Matematica e delle sue Applicazioni. Serie VII, 33-61.
Lovász, L., & Szegedy, B. (2006). Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6), 933-957.
Lovász, L. (2012). Large networks and graph limits (Vol. 60). American Mathematical Soc..
8

9. Limitations of traditional graphons
•A corollary of Aldous-Hoover theorem
Graphs represented by an exchangeable matrix are either trivially empty or dense
•These graphons can model dense graphs but not sparse graphs
•Why?
•
The volume from converges to
•
For sparse graphs
(x,y,W(x,y)) lim
n→∞
2m
n
2
lim
n→∞
m
n
2
=0⟺W=0
9

10. What happens when ?W=0
•Sample random points from the interval -
•For every the value is the edge probability
•You have a graph with nodes, but no edges — not representative of sparse graphs


This is the fundamental problem of modeling sparse graphs using graphons!
n [0,1]{r
1,r
2,…,r
n}
(r
i,r
j) W(r
i,r
j)=0
n
10
W=0

11. Example - Star graphs K1,n
•Star graphs
•Adjacency matrix pixel pictures
ones - black
zeros - white
(Empirical graphons)
11

12. For sparse graphs …
•Pixel pictures (empirical graphons) converge to zero
Empirical graphons Graphon
12

13. What about other non-graphon methods?
•Yes, other generative methods exist
•Eg. Preferential attachment graphs
•But graphons are very flexible
•Modeling the full adjacency matrix
•Interest in pursing graphons for sparse graphs
13

14. Current
approaches for
sparse graphs
14

15. Sparse graphs via graphons - approaches
•Kallenberg exchangeable graphs - Caron & Fox 2014 and others later
•Model graphs as exchangeable point processes
•Rescaled graphons, stretched graphons - Borgs & Chayes group and others
•Using analytical/measure theoretic approaches
•Edge exchangeable graphs - Crane & Dempsey, Broderick, Janson and others
•Graphexes - Veitch & Roy and others
•Considers a triple for isolated edges and stars
•Sparsification of graphons
(I,S,W)
15

16. Kallenberg
Exchangeable
Graphs
•Introduced by Caron
and Fox (2017) and later
used by many others
•
defined on the positive
quadrant
W:ℝ
2
+→[0,1]
Caron, F., & Fox, E. B. (2017). Sparse graphs using exchangeable random measures. Journal of the Royal Statistical Society Series B: Statistical Methodology, 79(5), 1295-1366.
Caron, F., Panero, F., & Rousseau, J. (2023). On sparsity, power-law, and clustering properties of graphex processes. Advances in Applied Probability, 55(4), 1211-1253.
16

17. Rescaled and
stretched
graphons
•Many methods proposed by Borgs &
Chayes research group
•Rescaled
•Stretched graphon defined on .


ℝ
2
+
˜W(x,y)=W(∥W∥
0.5
1
x,∥W∥
0.5
1
y)
Borgs, C., Chayes, J. T., Cohn, H., & Holden, N. (2018). Sparse exchangeable graphs and their limits via graphon processes. Journal of Machine Learning Research, 18(210), 1-71.
˜W=
W
∥W∥
1
17

18. Edge
exchangeability
•Crane and Dempsey, Cai et al,
Janson and others
Crane, H., & Dempsey, W. (2015). A framework for statistical network modeling. arXiv preprint arXiv:1509.08185.
Crane, H., & Dempsey, W. (2016). Edge exchangeable models for network data. arXiv preprint arXiv:1603.04571.
Cai, D., Campbell, T., & Broderick, T. (2016). Edge-exchangeable graphs and sparsity. Advances in Neural Information Processing Systems, 29.
Janson, S. (2018). On edge exchangeable random graphs. Journal of statistical physics, 173(3), 448-484.
18

19. Graphexes
•Originally introduced by Veitch & Roy
•A triple where models isolated
edges, integrable, models
infinite stars and is the
standard graphon. But they consider

•Borgs and Chayes group - high degree hubs
give the skeleton with low degree vertices
forming the body
(I,S,W) I∈ℝ
S:ℝ
+→ℝ
+
W:ℝ
2
+
→[0,1]
I=0 and S=0
Veitch, V., & Roy, D. M. (2015). The class of random graphs arising from exchangeable random measures. arXiv preprint arXiv:1512.03099.
Veitch, V., & Roy, D. M. (2019). Sampling and estimation for (sparse) exchangeable graphs.
Borgs, C., Chayes, J. T., Dhara, S., & Sen, S. (2021). Limits of sparse configuration models and beyond. The Annals of Probability, 49(6), 2830-2873.
19

20. Sparsification of the graphon
•Very popular in machine learning
• where
•Diluting a dense graphon over time. Cannot generate large hubs. Not projective.
W
n=ρ
nW(x,y) ρ
n→0
Klopp, O., Tsybakov, A. B., & Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation.
20

21. Sparse graphs -> (compact)W=0
•Common themes of solutions provided
•Extending the graphon on - non compact
•Graphs modeled as point processes using Kallenberg exchangeablity - sampling from the
reals instead of integers
•More rigorous measure theoretic approaches (because what you’re trying to measure
goes to zero)
•All these methods work directly with the observed graph
ℝ
2
+
21

22. Proposed
method
22

23. Model as it is
— use KEGs/Measure theoretic
methods/Define on
{G
n}
n
ℝ
2
+
{G
n
}
n
Transform such that
— the transformed graphs are dense
{G
n
}
n
— Works for a subset of sparse graphs
23

24. The transformation - line graphs
•Edges Mapped to vertices
•Vertices are connected, if they share an edge
•The name line graphs - term came from Frank
Harary (motivated by Harary calling “vertices"
and “edges”, “points” and “lines”)
•Work originated by Hassler Whitney in 1932
•Other names used, interchange graphs,
edge-to-vertex dual, covering graph,
derivative, derived graph, adjoint, conjugate
Graph G Line graph H=L(G)
Kandanaarachchi, S., & Ong, C. S. (2024). Graphons of line graphs. arXiv preprint arXiv:2409.01656.
24

25. Star graphs K1,n
•Star graphs
•Line graphs of star graphs
are complete (and dense)

•Empirical graphons of line graphs
are not zero
G
n+1=K
1,n
H
m=L(G
n)
25

26. Multiple stars
•Star graphs
•Line graphs of stars (complete subgraphs)

•Empirical graphons of line graphs
G
n
H
m=L(G
n)
Kandanaarachchi, S., & Ong, C. S. (2024). Graphons of line graphs. arXiv preprint arXiv:2409.01656.
26

27. Max-degree condition
•Let denote a sequence of graphs where has nodes and edges. Let the
maximum degree of be denoted by . We say that satisfies the max-degree
condition if there exists some such that



We denote the set of graph sequences satisfying the max-degree condition by
•If , then their line graphs are dense.
Let and . Suppose . Then .
{G
n}
n G
nn m
G
n d
max,n {G
n}
n
c
1
>0
lim inf
n,m→∞
d
max,n
m
=c>0.
S
x
{G
n}
n∈S
x
{G
n}
n∈S
xH
m=L(G
n) {H
m}
m→U U≠0
27

28. Are all sparse graphs max-degree?
•No! Paths, Cycles, r-regular graph sequences.
•If is dense, then {G
n
}
n
{G
n
}
n
∉S
x
Dense
graphs D
Sparse
graphs S\S
x
Max-
degree S
x
28

29. {G
n
}
n
Dense
W≠0
{G
n
}
n
∉S
x
U=0
Eg: Erdos Renyi
graphs
{G
n
}
n
∉S
x
U=0
e.g. Paths,
Cycles
e.g. Superlinear pref
attachment graphs,
Stars
Sparse
W=0
{G
n
}
n
∈S
x
U≠0
•
, line graph of

and graphons
, the set of dense graph sequences,
sparse graph sequences,
max-degree property
{G
n}
n→W
H
m=L(G
n) G
n
{H
m}
m→U
W U
D
S
S
x
For graphs satisfying the max degree property, we’re good
Kandanaarachchi, S., & Ong, C. S. (2024). Graphons of line graphs. arXiv preprint arXiv:2409.01656.
D
Sparse
S\S
x
S
x
29

30. Map between and {G
n}
n{H
m}
m
•Say and where and and are graphons. , the
set of dense graph sequences, sparse graph sequences, graphs satisfying the max-
degree condition
{G
n
}
n
→W {H
m
}
m
→U H
m
=L(G
n
)W U D
S S
x


{G
n
}
n
∈D≡W≠0
{G
n}
n∈S\S
x⟹W=0
{G
n
}
n
∈S
x
⟹W=0


{H
m}
m∈S≡U=0
{H
m
}
m
∈D≡U≠0
Kandanaarachchi, S., & Ong, C. S. (2024). Graphons of line graphs. arXiv preprint arXiv:2409.01656.
D
Sparse
S\S
x
S
x
30

31. Erdos-Renyi graphs G(n,p)
•
Recall: dense graphs:
•For , this limit equals
•The graphon of line graphs is zero for Erdos-Renyi
graphs.
•Theorem: Let be an Erdős–Rényi graph sampled from
a model and suppose has nodes and
edges. Let where denotes the line
graph. As and go to infinity, the edge density of
satisfies
lim inf
n→∞
m
n
2
=c>0
G(n,p) p
U
G
n
G(n,p) G
n
n m
H
m
=L(G
n
) L(⋅)
nm H
m
lim
m→∞
P[density(H
m
)=0]=1
Erdos-Renyi pixel pictures
and graphon
Line graphs of Erdos-Renyi graphs
31

32. Line graph limits
and mixtures
32

33. A note on line graph inverses (root)
•All graphs are not line graphs.
•There are 9 line forbidden graphs that cannot be an induced subgraph.
•If two line graphs are isomorphic, their roots (inverse line graph) are also isomorphic with one
exception. That is when the line graph is a triangle, the root can be either a triangle or a
star (Whitney 1932)
•If a graph is a line graph, then algorithms exist to find the root with complexity.
K
3
K
1,3
O(n)
Beineke, L. W., & Bagga, J. S. (2021). Line graphs and line digraphs. Switzerland: Springer.
33

34. Line graph limits
•For a subset of sparse graphs , the line graphs give a non-zero graphon .

What is this limit like? What is the limit of line graphs?
•Janson (2016): A graph limit is a line graph limit if and only if it is a disjoint clique graph
limit.

S
x U
Janson, S. (2016). Graph limits and hereditary properties. European Journal of Combinatorics, 52, 321-337.
Examples of line graphons
34

35. Graphs sampled from line graph limits
•They are disjoint cliques
•The inverse line graphs of disjoint cliques are
stars
•The inverse line graph exists when you sample from a line graph limit; and they are disjoint stars.
35

36. Sampling from graphon W
•Sampling - a graph with nodes labeled

•Sample random points from the interval
-
•For every the value is
the edge probability
•Toss a coin with probability , and
connect the edge between and if you
get heads
n
{1,2,…,n}
n
[0,1]{r
1
,r
2
,…,r
n
}
(r
i
,r
j
) W(r
i
,r
j
)=p
p
ij
36
r
i
r
j
n=10
n=20

37. Graphon mixture
•Parameters: dense nodes sparse edges , the number of edges when joining n
d, m
s m
new
Sample dense graph
G
n
d
Sample sparse graph

First sample disjoint cliques
Then compute the
inverse line graph
G
n
s
=L
−1
(H
m
s
)
Randomly join the two graphs
Kandanaarachchi, S., & Ong, C. S. (2025). Graphon Mixtures. arXiv preprint arXiv:2505.13864.
37

38. A sample from a dense mixture
• n
d
i
=50,n
s
i
=20
Sample dense
graph
G
n
d
Sample sparse graph

First sample disjoint cliques
Then compute the
inverse line graph
G
n
s
=L
−1
(H
m
s
)
Mixture graph after joined
38

39. A sample from a sparse mixture
• n
d
i
=50,n
s
i
=100
Sample dense
graph
G
n
d
Sample sparse graph

First sample disjoint cliques
Then compute the
inverse line graph
G
n
s
=L
−1
(H
m
s
)Mixture graph after joined
39

40. graph mixtures(U,W)
• - node num. sequence for dense part, - node number sequence for sparse part


{n
d
i
}
i
{n
s
i
}
i
lim
i→∞
n
s
i
n
d
i
lim
i→∞
n
s
i
n
d
i
=c<∞
lim
i→∞
n
s
i
n
d
i
=∞
is dense{G
n
i
}
i
is sparse{G
n
i
}
i
40

41. Dense and sparse mixtures
•Different limits n
s
i
/n
d
i 41

42. Inference
42

43. Inference and prediction
•Given a -mixture graph, can we estimate
•Many methods to estimate . The new part is , that’s our interest.
•We can estimate , if the graph sequence is sparse.
•The degree distribution has the clue
(U,W) U?
W U
U
43

44. Degree distribution - sparse mixtures
Unique degree values 44

45. Degree distribution - sparse mixtures
Unique degree values 45

46. Estimating for sparse graphsU
•By finding the elbow point we can estimate
• given by such that
•
, where is the degree of the th
largest degree
• is found from the elbow point

and
U
U p=(p
1
,p
2
,…)
∑
p
i
=1
̂p
j=
q
j
∑
̂
k
i=1
q
i
q
i
i
̂
k
??????(̂p
j
)−p
j
≤
c
m
s
i
Var(̂p
j
)≤
c
m
s
i
46

47. Finite and infinite partitions of U
• or gives the big players influence
•Eg - electricity network, if such a node is attacked, large negative impact
Up=(p
1,p
2,…)
U
p=(p
1
,…p
k
) p=(p
1,p
2,…)
when graphs are large
̂
k=k increases as graphs grow in size
̂
k
47

48. Top-k degrees of sparse mixtures(U,W)
•
As , the number of nodes in the sparse part grows faster than the dense
part
•Hubs grow linearly with the total number of nodes
•Say you observe graph and you want to predict the hubs in with
•
The degree of the th hub =>

lim
i→∞
n
s
i
n
d
i
=∞ n
s
i
n
i
G
n
i
G
n
j
n
j
>n
i
k q
k,i≈p
km
s
i
̂q
k,j≈q
k,i
m
s
j
m
s
i
≈q
k,i
n
s
j
n
s
i
48

49. Validation
•For real datasets this method can predict top-k degrees better
49
Kandanaarachchi, S., & Ong, C. S. (2025). Graphon Mixtures. arXiv preprint arXiv:2505.13864.

50. graphon mixtures(U,W)
•Simpler method to generate sparse graphs using inverse line graphs
•Generate dense and sparse graphs from and and join them
•Typical real networks have high degree hubs forming the skeleton
with low degree vertices constituting the body of the network
•Sparse mixture graphs have this property
•Flexibility: depending on how increase, we can get dense or sparse graphs
•We can infer and predict the top- degrees of unseen sparse graphs with some
guarantees
W U
(U,W)
n
s
i
/n
d
i
U k
50

51. Future work
•The current mixture scales hubs linearly with - incorporating other rates
•What about other types of joins? (We’ve used random joining)
•Other sparse graphs - paths, rings, isolated edges . . . (not the driving force of real sparse
graphs but . . .)
•R package - graphonmix - https://github.com/sevvandi/graphonmix
•Will be on CRAN soon.
•Link to examples and documentation.
(U,W) n
i
51

52. Thank you!
Questions?
52

53. Extra slides
53

54. Intuition behind Erdos-Renyi line graphs
•Edge density for a graph with nodes and
edges is
•
Non-zero area of empirical graphon is
•Line graph edge densities go to zero for

•The graphon of line graphs
n
m
2m
n(n−1)
2m
n
2
G(n,p)
U=0
0.00
0.05
0.10
0.15
0.20
0 250 500 750 1000
Number of nodes in graph
Edge Density
Type
Graph
Line Graph
54

55. Square-degree property
•Let denote a sequence of graphs. We say that exhibits the square-degree
property if there exists some and such that for all we have

•We denote the set of graph sequences satisfying the square-degree property by
{G
n}
n {G
n}
n
c
1>0N
0∈ℕ n>N
0
∑
degv
2
i,n
≥c
1(∑
degv
i,n)
2
S
q
55

56. Where does square-degree come from?
•Let the line graph of graph be denoted by , and has nodes and edges
•
Then edge density of line graph density
•

•Square-degree property <=> line graph edge density is non-zero
<=> graphon of line graphs have non-zero area
G L(G)Gn m
(L(G))=
#edges
Allpossibleedges
=
1
2
∑
i
degv
2
i−m
1
2
m(m−1)
∑
degv
2
i,n
≥c
1(∑
degv
i,n)
2
=c
1
m
2
56

57. Graph homomorphism - convergence
•A graph homomorphism from to is a map such that if then
(Maps edges to edges). Let be the set of all such homomorphisms
and let . Then homomorphism density is defined as
•

•

•A graph sequence is said to be convergent if converges as goes to infinity for
any simple graph .
FG f:V(F)→V(G) uv∈E(F)
f(u)f(v)∈E(G) Hom(F,G)
hom(F,G)=|Hom(F,G)|
t(F,G)=
hom(F,G)
|V(G)|
|V(F)|
,note that  t(F,G)∈ℝ
t(F,W)=
∫
[0,1]
|V(F)|
∏
ij∈E(F)
W(x
i
,x
j
)dx
{G
n
}
n
t(F,G
n
) n
F
57

58. How does the graphon come in?
•Theorem (Borgs et al. 2008)
• converges iff there is a such that .
•And for every there is a convergent sequence of graphs like above.
{G
n
}
n
W t(F,G
n
)→t(F,W)
W
Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T., & Vesztergombi, K. (2008). Convergent sequences of dense graphs I:
Subgraph frequencies, metric properties and testing. Advances in Mathematics, 219(6), 1801–1851. https://doi.org/
10.1016/j.aim.2008.07.008
58

59. Sparse graphs
•Sparse graphs give graphon
•The ultimate sparse graph - the Star graph
•As we have
W=0
K
1,n
n→∞ W→0
n = 10 n = 20 n = 40 n = 80
Empirical Graphons of Star Graphs
59

60. Why do sparse graphs give zero graphon?
•Area of the graphon and edge density are closely related.
•Non-zero area of the graphon edge density of graph
•For sparse graphs, edge density -> 0
≈
0.05
0.10
0.15
0.20
25 50 75 100
Number of Nodes in Star Graph
Edge Density
60

61. What happens when we use line graphs
•Certain sparse graphs give dense line graphs
•Then the graphon of line graphs is not zero for these types of sparse graphs
Sparse Dense
61

62. In one figure
62

63. Examples of deterministic graphs
• , graph with nodes and edges
•Maybe show pictures of these
G
n
n m
Graph Edge-density
Graph belongs
to
Line graph
edge density
Line graph
belongs to
Complete
Graphs
1 Dense graphs 4/(n+1) Sparse graphs
r-regular
graphs
r/(n-1) Sparse 4(r-1)/(rn-2) Sparse
Path 2/n Sparse 2/(n-2) Sparse
Cycles 2/(n-1) Sparse 2/(n-1) Sparse
Stars 2/n Sparse 1 Dense
63

64. Stars - Results
• , a star, and
•We can show that converges to a graphon , with for all
•And similarly, if we have multiple stars, converges to , where is a block diagonal
matrix.
G
n=K
1,n−1 H
m=L(K
1,n−1)
{H
m}
m U U(x,y)=1 x,y
{H
m}
m U U
1 star 2 stars 3 stars 4 stars
64

65. graphon mixture(U,W)
• is a disjoint clique graphon, is a graphon
• and are increasing positive integer valued sequences
• - graph sampled from with nodes
• - graph sampled from with nodes => is a collection of stars
•New edges for joining for some small
•Join (the dense part) with (the sparse part) with edges
•Call the joined graph . We get a mixture graph sequence
U W
{n
d
i
}
i{m
s
i
}
i
G
d
i
W n
d
i
H
s
i
U m
s
i
G
s
i
=L
−1
(H
s
i
)
m
new
i
=cm
d
i
c
G
d
i
G
s
i
m
new
i
G
n
i
{G
n
i
}
i
Kandanaarachchi, S., & Ong, C. S. (2025). Graphon Mixtures. arXiv preprint arXiv:2505.13864.
65

66. Preferential Attachment Graphs
•New nodes connect to more connected nodes
•The probability that a new node connects to node , which has degree is given by
•

•Maximum degree
•Three regimes of : sublinear , linear , and superlinear
•
Sethuraman & Venkataramani (2019) show that for ,
Π(i) i k
i
Π(i)=
k
α
i
∑
i
k
α
i
k
max
α α<1 α=1 α>1
α>1P
[
lim
n→∞
1
n
k
max
=1
]
=1
Sethuraman, S., & Venkataramani, S. C. (2019). On the Growth of a Superlinear Preferential Attachment Scheme. Springer Proceedings in Mathematics and Statistics, 283,
243–265. https://doi.org/10.1007/978-3-030-15338-0_9
66

67. Superlinear pref. attachment
•Using this result we show
•Lemma: Let denote a sequence of graphs growing by superlinear preferential
attachment with . Then almost surely.
•Say and where and and are graphons.
•If is a superlinear pref. attachment graph sequence, then
{G
n}
n
α>1 {G
n}
n∈S
q
{G
n
}
n
→W {H
m
}
m
→U H
m
=L(G
n
)W U
{G
n}
n U≠0
67