---
title: "Introduction"
output: rmarkdown::html_vignette
vignette: >
%\VignetteIndexEntry{Introduction}
%\VignetteEngine{knitr::rmarkdown}
%\VignetteEncoding{UTF-8}
bibliography: bibliography.bib
---
```{r, include = FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
comment = "#>"
)
```
```{r setup}
library(igraph)
library(graphonmix)
library(ggplot2)
```
# (U,W)-mixture graphs
The $(U,W)$-mixture graphs are graphs generated from two graphons $U$ and $W$. Graphon $W$ generates dense graphs and graphon $U$ generates sparse graphs. The vignette at *Articles/Sparse Graphs from Line Graphons* explains how graphon $U$ generates sparse graphs. Once the dense and sparse graphs are generated, nodes are joined randomly. This gives the mixture graph. The methodology is explained in [@SKCS2025graphon].
## The two graphons W and U
Let's plot the two graphons $W$ and $U$ first.
```{r}
# create the dense graphon W(x,y) = exp(-(x+y)/40) where x and y ranges from 1 to 100
W <- create_exp_matrix(100, 40)
# plot this graphon
plot_graphon(W) +
coord_fixed(ratio = 1) +
ggtitle("Dense graphon W")
```
The graphon $W$ above generates the dense part of the graph. The graphon $U$, which we show below generates the sparse part of the graph.
```{r}
# weights for the sparse part
seq <- 2:5
wts <- (1/1.2^seq)
wts <- wts/sum(wts)
wts
U <- line_graphon(wts)
plot_graphon(U) +
coord_fixed(ratio = 1) +
ggtitle("Line graphon U")
```
## Generating the mixture graph in one step
Graphon $U$ is generated from weights *wts* in the above piece of code. Given *wts* and $W$ we can generate a mixture graph using the function *sample_mixed_graph*. We need to specify the number of nodes in the dense part *nd* and the number of nodes in the sparse part *ns*. The parameter *p* gives the proportion of the number of edges added in the joining process. The joining process adds $p \times$ *number of edges in dense part* to the graph. These edges connect nodes in the dense part to those in the sparse part randomly.
```{r}
# single function to generate a graph mixture
gr1 <- sample_mixed_graph(W, wts, nd = 100, ns = 300, p = 0.5)
# plot(gr1, vertex.label = NA, vertex.size = 1, main = "(U,W) Graph mixture")
plot(gr1,
edge.curved = 0.3,
vertex.size = degree(gr1)*0.1,
edge.color = "lightgray", # Light colored edges
vertex.label = NA,
vertex.color = "lightblue",
main = "(U,W) Graph mixture"
)
```
## Generating a dense and sparse graph and joining to get the mixture
Or we can generate the dense part and sparse part separately and join them.
```{r}
# sample dense part and plot it
grdense <- sample_graphon(W, n = 100)
plot(grdense,
edge.curved = 0.3,
vertex.size = degree(grdense) * 0.1,
edge.color = "lightgray", # Light colored edges
vertex.label = NA,
vertex.color = "lightblue",
main = "Dense Part"
)
# sample sparse part and plot it
grsparse <- generate_star_union(wts, n = 300)
plot(grsparse,
edge.curved = 0.3,
vertex.size = degree(grsparse) * 0.1,
edge.color = "lightgray", # Light colored edges
vertex.label = NA,
vertex.color = "lightblue",
main = "Sparse Part"
)
# join the two graphs and plot it
gr2 <- graph_join(grdense, grsparse, p = 0.5)
plot(gr2,
edge.curved = 0.3,
vertex.size = degree(gr2) * 0.1,
edge.color = "lightgray", # Light colored edges
vertex.label = NA,
vertex.color = "lightblue",
main = "(U,W) Graph mixture"
)
```
# Estimating graphon U
If the graph sequence is sparse, then the high degrees of the graph are generated by graphon $U$. These are different from the low degrees. We can see it when we plot the sorted log degrees of the observed graph.
## Observing the elbow point in unique log degrees
The graph below plots the sorted unique log degrees of the mixture graph. Notice the elbow point around indices 4 and 5.
```{r}
degu <- sort(unique(degree(gr2)), decreasing = TRUE)
# we only take the top 1/2 of the unique degree values here to see the effect of the hub nodes clearly
degu <- degu[degu >= median(degu)]
df <- data.frame(
index = 1:length(degu),
log_degree = log(degu)
)
ggplot(df, aes(index, log_degree)) +
geom_point() +
xlab("Index") +
ylab("Log Degree")
```
Let us check the degrees of the dense part and the sparse part and compare it with the degrees of the mixture graph
```{r}
deg_dense <- sort(unique(degree(grdense)), decreasing = TRUE)
deg_dense
deg_sparse <- sort(unique(degree(grsparse)), decreasing = TRUE)
deg_sparse
deg_mix <- sort(unique(degree(gr2)), decreasing = TRUE)
deg_mix
```
Of course the graph joining process increases the degrees of some nodes because nodes are joined by the additional edges.
```{r}
which(deg_sparse > max(deg_dense))
```
## Detecting the elbow point and estimating $U$
From the mixture graph we can identify the sparse part. We do this by finding the elbow point of the log degree graph shown above. The function *extract_sparse* does the job.
```{r}
out <- extract_sparse(gr2)
out$num_hubs
# Estimate of the mass-partition
out$phat
# Actual mass partition
wts
```
The estimated mass-partition is given in *out$phat* in the above code. The estimate is close to the actual mass partition given by *wts*.
We can see the elbow point of the unique log degree graph with *autoplot*.
```{r}
autoplot(out)
```
Now that we have estimated the weights (mass-partition) we can plot the estimated graphon $\hat{U}$.
```{r}
Uhat <- line_graphon(out$phat)
plot_graphon(Uhat) +
coord_fixed(ratio = 1) +
ggtitle("Estimate of U")
```
## References