| Title: | Generates Mixture Graphs from Dense and Sparse Graphons |
|---|---|
| Description: | Generates (U,W) mixture graphs where U is a line graph graphon and W is a dense graphon. Graphons are graph limits and graphon U can be written as sequence of positive numbers adding to 1. Graphs are sampled from U and W and joined randomly to obtain the mixture graph. Given a mixture graph, U can be inferred. Kandanaarachchi and Ong (2025) <doi:10.48550/arXiv.2505.13864>. |
| Authors: | Sevvandi Kandanaarachchi [aut, cre] (ORCID: <https://orcid.org/0000-0002-0337-0395>) |
| Maintainer: | Sevvandi Kandanaarachchi <[email protected]> |
| License: | GPL (>= 3) |
| Version: | 0.0.1.0 |
| Built: | 2026-05-15 10:29:08 UTC |
| Source: | https://github.com/sevvandi/graphonmix |
Plots the two lines fitted to the unique, sorted log degrees of the graph.
## S3 method for class 'extract_sparse' autoplot(object, ...)## S3 method for class 'extract_sparse' autoplot(object, ...)
object |
The output of the function 'extract_sparse' |
... |
Other arguments currently ignored |
A ggplot object.
library(igraph) gr <- sample_pa(10000, power = 1.2, directed = FALSE) sparse <- extract_sparse(gr) autoplot(sparse)library(igraph) gr <- sample_pa(10000, power = 1.2, directed = FALSE) sparse <- extract_sparse(gr) autoplot(sparse)
Creates an nxn matrix where the (i,j)th entry is exp(-(i+j)/scalar)
create_exp_matrix(nrow, scalar)create_exp_matrix(nrow, scalar)
nrow |
The dimension of the matrix |
scalar |
The scalar in exp(-(i+j)/scalar) |
An nxn matrix
W <- create_exp_matrix(100, 100)W <- create_exp_matrix(100, 100)
Computes empirical graphon given a graph
empirical_graphon(gr, n = NULL)empirical_graphon(gr, n = NULL)
gr |
A graph |
n |
Dimension of the graphon matrix |
The empirical graphon
library(igraph) gr <- sample_gnp(1000, p=0.2) emp <- empirical_graphon(gr, n = 100)library(igraph) gr <- sample_gnp(1000, p=0.2) emp <- empirical_graphon(gr, n = 100)
This function extracts the sparse component from a (U,W) mixture graph by fitting two lines to the unique sorted log degree values. The first line gives the number of hubs in the sparse part and the remaining line fits the degrees of the dense part.
extract_sparse(gr)extract_sparse(gr)
gr |
The input graph |
a list with the following components:
num_hubs |
The number of hubs in the sparse component. |
phat |
The probability vector of the sparse component. This is also known as the mass partition. |
segment_sizes |
The sizes of the two line segments. |
line_equations |
The two equations of the lines. |
cutoff |
The best cut off for the two lines. |
models |
The models of the fitted lines. |
mse |
The mean squared error |
data |
The degree data. |
library(igraph) gr <- sample_pa(10000, power = 1.2, directed = FALSE) sparse <- extract_sparse(gr) sparse$phatlibrary(igraph) gr <- sample_pa(10000, power = 1.2, directed = FALSE) sparse <- extract_sparse(gr) sparse$phat
Generates a union of star graphs given the weights
generate_star_union(wts, n)generate_star_union(wts, n)
wts |
The proportion of the hub degrees |
n |
The number of nodes in the new graph |
A disjoint union of star graphs
library(igraph) wts <- c(0.5, 0.3, 0.2) gr <- generate_star_union(wts, n = 100) grlibrary(igraph) wts <- c(0.5, 0.3, 0.2) gr <- generate_star_union(wts, n = 100) gr
Joins two graphs randomly connecting vertices
graph_join(gr1, gr2, p = 0.5, option = 2)graph_join(gr1, gr2, p = 0.5, option = 2)
gr1 |
The first graph to join |
gr2 |
The second graph to join |
p |
The proportion of edges in |
option |
Two options. 1 does the disjoint union, 2 does the random edges union. |
The joined graph
W <- create_exp_matrix(100, 100) # create the sparse part - a disjoint set of stars wts <- c(0.5, 0.3, 0.2) grdense <- sample_graphon(W, 100) grsparse <- generate_star_union(wts, 200) gr <- graph_join(grdense, grsparse, opt = 2)W <- create_exp_matrix(100, 100) # create the sparse part - a disjoint set of stars wts <- c(0.5, 0.3, 0.2) grdense <- sample_graphon(W, 100) grsparse <- generate_star_union(wts, 200) gr <- graph_join(grdense, grsparse, opt = 2)
Creates a line graphon, which is a disjoint clique graphon from a sequence of probability values
line_graphon(probs)line_graphon(probs)
probs |
The list of probabilities starting from the largest. |
The line graphon
library(ggplot2) wts <- c(0.5, 0.3, 0.2) U <- line_graphon(wts) plot_graphon(U)library(ggplot2) wts <- c(0.5, 0.3, 0.2) U <- line_graphon(wts) plot_graphon(U)
Plots graphon
plot_graphon(W, cols = c("white", "black"))plot_graphon(W, cols = c("white", "black"))
W |
A graphon given by an nxn matrix |
cols |
Colors, by default white and black |
A ggplot object.
W <- create_exp_matrix(100, 100) plot_graphon(W)W <- create_exp_matrix(100, 100) plot_graphon(W)
Predicts the degree of hubs of an unseen graph given a graph generated from the same process.
predict_hubs(gr, n, k = NULL)predict_hubs(gr, n, k = NULL)
gr |
The input graph |
n |
The number of nodes in the new graph |
k |
The number of hubs. Default is |
A vector of hub degrees
library(igraph) gr <- sample_pa(10000, power = 1.2, directed = FALSE) predict_hubs(gr, n = 11000)library(igraph) gr <- sample_pa(10000, power = 1.2, directed = FALSE) predict_hubs(gr, n = 11000)
Generates a graph given a dense graphon W.
sample_graphon(W, n)sample_graphon(W, n)
W |
A graphon given by a matrix |
n |
The number of nodes of the sampled graph |
A graph sampled from the graphon W with n nodes
library(igraph) W <- matrix(0.2, nrow = 100, ncol = 100) gr <- sample_graphon(W, n= 100)library(igraph) W <- matrix(0.2, nrow = 100, ncol = 100) gr <- sample_graphon(W, n= 100)
Generate a (U,W) mixture graph from a dense graphon W and a mass partition corresponding to a line graph graphon U.
sample_mixed_graph(W, wts, nd, ns, p = 0.5, option = 2)sample_mixed_graph(W, wts, nd, ns, p = 0.5, option = 2)
W |
The dense graphon. This is a symmetric matrix with values in [0,1] |
wts |
The degree proportions of the hub degrees. Need to add up to 1. This is the mass partition corresponding to the line graph graphon U. |
nd |
The number of nodes in the dense part of the graph |
ns |
The number of nodes in the sparse part of the graph |
p |
The nodes to be added as a proportion of the edges in the dense part |
option |
Graph joining option. If |
A graph sampled from the (U,W) mixture.
library(igraph) W <- matrix(0.1, nrow = 100, ncol = 100) wts <- c(0.5, 0.3, 0.2) ns <- 200 nd <- 100 p <- 0.5 gr <- sample_mixed_graph(W, wts, nd, ns, p, option = 2) grlibrary(igraph) W <- matrix(0.1, nrow = 100, ncol = 100) wts <- c(0.5, 0.3, 0.2) ns <- 200 nd <- 100 p <- 0.5 gr <- sample_mixed_graph(W, wts, nd, ns, p, option = 2) gr
Scales a graphon to an nxn matrix suitable for large adjacency matrices
scale_graphon(W, n)scale_graphon(W, n)
W |
A graphon given as a symmetric square matrix |
n |
The dimension of the output matrix |
Scaled nxn graphon
library(igraph) gr <- sample_gnp(1000, p=0.2) adj <- as_adjacency_matrix(gr) W <- scale_graphon(adj, 100)library(igraph) gr <- sample_gnp(1000, p=0.2) adj <- as_adjacency_matrix(gr) W <- scale_graphon(adj, 100)
This function breaks a (U,W) mixture graph into a dense and sparse component.
separate_dense_and_sparse(grmix)separate_dense_and_sparse(grmix)
grmix |
The input graph |
a list with the following components:
gr_dense |
The dense component. |
gr_sparse |
The sparse component. |
data |
The original graph. |
library(igraph) W <- matrix(0.1, nrow = 100, ncol = 100) wts <- c(0.5, 0.3, 0.2) ns <- 200 nd <- 100 p <- 0.5 gr <- sample_mixed_graph(W, wts, nd, ns, p = 0.1, option = 2) out <- separate_dense_and_sparse(gr) outlibrary(igraph) W <- matrix(0.1, nrow = 100, ncol = 100) wts <- c(0.5, 0.3, 0.2) ns <- 200 nd <- 100 p <- 0.5 gr <- sample_mixed_graph(W, wts, nd, ns, p = 0.1, option = 2) out <- separate_dense_and_sparse(gr) out