Package {nethist}

nethist: Network Histograms

Description

Estimates network histograms, a blockmodel approximation to the graphon underlying a network's connectivity pattern, for both single-layer and multilayer networks. Implements graphon estimation methods including the profile-likelihood method of Olhede and Wolfe (2014) doi:10.1073/pnas.1400374111 and the least-squares method of Gao, Lu, and Zhou (2015) doi:10.1214/15-AOS1354 for single-layer networks, and the multilayer extension of Song and Olhede (2026) doi:10.48550/arXiv.2608.14536.

Author(s)

Maintainer: Youngseok Song youngseok.song@mail.wvu.edu

Authors:

• Youngseok Song youngseok.song@mail.wvu.edu

• Sofia C. Olhede sofia.olhede@epfl.ch

See Also

Useful links:

• https://enigmasong.github.io/nethist/

• Report bugs at https://github.com/EnigmaSong/nethist/issues

Indian Village socioeconomic networks

Description

A processed version of the Indian village dataset from Banerjee et al. (2013), representing socio-economic networks at the individual level for village ID 40.

Format

IndianVil is an array with size of 231 x 231 x 12.

Details

The array represents the socio-economic relationships of individuals from Village ID 40. Vertices with zero degrees across all layers were removed, reducing the total number of vertices from 241 to 231.

Source

https://doi.org/10.7910/DVN/U3BIHX

References

Banerjee, A., Chandrasekhar, A. G., Duflo, E., & Jackson, M. O. (2013). The diffusion of microfinance. Science, 341(6144), 1236498.

Song, Y. & Olhede, S. C. (2026). Joint Estimation of Sparse Multilayer Networks via Graph Limits. https://arxiv.org/abs/2608.14536

Examples

  data(IndianVil)
  
  dim(IndianVil)

Bin summary by covariate

Description

Drawing a bin summary plot of covariates given a multinethist object with a user-specified order.

Usage

covariate_plot(
  object,
  covariate,
  idx_order = 1:max(object$cluster),
  main = NA,
  xlab = NULL,
  ylab = NA,
  legend_title = NA,
  stat = "count",
  position = "stack"
)

summary_plot(object, covariate, ...)

Arguments

Details

When covariate is a factor, a stacked bar chart is drawn with bins ordered by idx_order. When covariate is numeric, a violin plot is drawn.

Value

A ggplot object. Printed as a side effect. Returns the plot invisibly.

Examples

set.seed(42)
data(polblog)
nethist_polblog <- multinethist(polblog)
x <- factor(c(rep("Liberal", 586), rep("Conservative", 638)))
covariate_plot(nethist_polblog, x)

Fitted values for a multinethist model

Description

Returns a subarray of the fitted block-probability or graphon matrix for a multinethist object.

Usage

## S3 method for class 'multinethist'
fitted(
  object,
  set1 = NULL,
  set2 = NULL,
  layer = NULL,
  type = "nethist",
  drop = TRUE,
  ...
)

Arguments

Value

A numeric matrix of dimension ⁠|set1| x |set2|⁠ when a single layer is selected and drop = TRUE, otherwise a 3-dimensional array of dimension ⁠|set1| x |set2| x |layer|⁠.

See Also

multinethist(), nethist()

Examples

data(IndianVil)
fit <- multinethist(IndianVil, h = 20L)
fitted(fit, set1 = 1:10, set2 = 1:10, layer = 1)
fitted(fit, layer = c(1, 2), drop = FALSE)

Fitted values for a nethist model

Description

Returns a submatrix of the fitted block-probability or graphon matrix for a nethist or hnethist object.

Usage

## S3 method for class 'nethist'
fitted(object, set1 = NULL, set2 = NULL, type = "nethist", ...)

Arguments

Value

A numeric matrix of dimension ⁠|set1| x |set2|⁠.

See Also

nethist(), hnethist(), multinethist()

Examples

set.seed(1)
A <- igraph::as_adjacency_matrix(
  igraph::sample_gnp(60, 0.3), sparse = FALSE)
fit <- nethist(A, h = 10L)
fitted(fit, set1 = 1:10, set2 = 1:10)
fitted(fit, type = "prob")

Hybrid Network histogram estimation

Description

Estimating hybrid network histogram for single-layer networks and returning the indices of partitions.

Usage

hnethist(A, h = NA, method = "LSE", control = nethist_control(), ...)

Arguments

Details

Among the outputs, the best model is selected based on the BIC criterion.

The original reference provided theoretical guarantees for LSE, but we also allow PLL for the initial nethist fit. The block clustering and model selection steps are performed on the LSE loss regardless of the initial method, as the theoretical results pertain to LSE.

Value

A list of class c("hnethist", "nethist") with the following fields:

• cluster an integer vector of length n with vertex-level block assignments from the initial nethist fit.

• thetahat a k-by-k probability matrix of the selected hybrid model, where k is the number of nethist blocks.

• rho_hat estimated sparsity parameter from the initial nethist fit.

• normalized_LL normalized log-likelihood from the initial nethist fit.

• MSE mean squared error of the selected model.

• method loss function used ("LSE" or "PLL").

• h bandwidth used for the initial nethist fit.

• blockcluster a kmeans object describing how the k-by-k blocks were merged into s shapes.

• BIC BIC value of the selected model.

• s number of distinct shapes in the selected model.

• details list of all candidate models, one entry per number of shapes from 1 up to the maximum considered, each containing s, blockcluster, thetahat, MSE, normalized_LL, and BIC.

• initial the nethist object used as the starting point for block clustering.

References

Verdeyme, A. & Olhede, S. C. (2024). Hybrid of Node and Link Communities for Graphon Estimation. arXiv:2401.05088

Network histogram estimation

Description

Estimating network histogram for multiplex networks and returning the indices of partitions.

Usage

multinethist(A, h = NA, common_f = FALSE, method = "PLL",
  control = nethist_control(), ...)

Arguments

Details

The lth layer's multi-network histogram is defined by thetahat/rho_hat. The multinetwork histogram can be plotted using plot() and plot3d().

If the number of layers is 1, multinethist() fits a single-layer network histogram, equivalent to nethist().

method is only used for single-layer networks. method = "PLL" is for Olhede and Wolfe (2014), and method = "LSE" is for Gao et al. (2015).

Note that cluster only shows a partition of vertices, and the index labels are not ordered. For example, vertices in cluster 1 do not have to be more similar to vertices in cluster 2 than to vertices in cluster 10. Hence, users may specify a custom order in plot.multinethist().

Value

If the number of layers is greater than 1, it returns an object of class multinethist:

• cluster a vector of partition indices.

• thetahat a probability array from multinetwork histogram ordered by group labels.

• rho_hat a vector of estimated sparsity parameters.

• normalized_LL a normalized likelihood from the algorithm.

• homogeneous a logical variable indicating homogeneous multinetwork histogram.

• h bandwidth used for estimation.

References

Song, Y. & Olhede, S. C. (2026). Joint Estimation of Sparse Multilayer Networks via Graph Limits. https://arxiv.org/abs/2608.14536

Olhede, S. C. & Wolfe, P. J. (2014). Network Histograms and Universality of Blockmodel Approximation. Proceedings of the National Academy of Sciences, 111(41), 14722-14727. doi:10.1073/pnas.1400374111

Gao, C., Lu, Y., & Zhou, H. H. (2015). Rate-Optimal Graphon Estimation. The Annals of Statistics, 43(6), 2624-2652. doi:10.1214/15-AOS1354

See Also

plot.multinethist(), plot.nethist(), nethist_control()

Examples

   #single-layer network histogram
   set.seed(42)
   data(polblog)
   nethist(polblog)
   nethist_polblog <- nethist(polblog)
   nethist_polblog_with_h <- nethist(polblog, h = 72)

   #multi-network histogram
   set.seed(42)
   data(IndianVil)
   IndianVil
   mnethist_Ind_Vil <- multinethist(IndianVil)

Network histogram estimation for single-layer networks

Description

Estimating a network histogram for a single-layer network and returning the indices of partitions.

Usage

nethist(A, h = NA, method = "PLL", control = nethist_control(), ...)

Arguments

Details

method = "PLL" is for Olhede and Wolfe (2014). method = "LSE" is for Gao et al. (2015).

Note that cluster labels are not ordered: vertices in cluster 1 are not necessarily more similar to cluster 2 than to cluster 10. Users may specify a custom display order in plot.nethist.

Value

An object of class "nethist" with the following fields:

• cluster an integer vector of length n with block assignments.

• thetahat a k \times k probability matrix ordered by group labels.

• rho_hat estimated sparsity parameter.

• normalized_LL normalized log-likelihood.

• MSE mean squared error.

• method loss function used ("PLL" or "LSE").

• h bandwidth used for estimation.

References

Olhede, S. C. & Wolfe, P. J. (2014). Network Histograms and Universality of Blockmodel Approximation. PNAS, 111(41), 14722-14727. doi:10.1073/pnas.1400374111

Gao, C., Lu, Y., & Zhou, H. H. (2015). Rate-Optimal Graphon Estimation. The Annals of Statistics, 43(6), 2624-2652. doi:10.1214/15-AOS1354

See Also

multinethist, plot.nethist, nethist_control

Examples

set.seed(42)
data(polblog)
fit <- nethist(polblog)
fit
plot(fit)

fit_h <- nethist(polblog, h = 72)

Control parameters for network histogram algorithms

Description

Constructs a control object for nethist, multinethist, and hnethist.

Usage

nethist_control(
  algorithm = "greedy",
  max_itr = 5e+06,
  greedy_swap_rule = "single_random",
  greedy_stop_threshold = 20000,
  verbose = FALSE,
  ...
)

## S3 method for class 'nethist_control'
print(x, ...)

Arguments

Value

An object of class "nethist_control".

See Also

nethist, multinethist, hnethist

Examples

# default control object
ctrl <- nethist_control()
print(ctrl)

# reduce iteration limit for quick testing
ctrl <- nethist_control(max_itr = 1e4, greedy_stop_threshold = 100)


data(polblog)
fit <- nethist(polblog, control = nethist_control(max_itr = 1e4))

Network summary plots

Description

Draw a network summary plot proposed by Maugis et al. (2017). To count k-cycles, Alon et al. (1997) is used.

Usage

netsummary_plot(
  A,
  subsample_sizes = NA,
  max_cycle_order = 4,
  n_rep = NA,
  n_subsample_sizes = 11,
  alpha = 0.05,
  y_max = NA,
  save_plot = FALSE,
  filename = "myplot.pdf",
  width = 7,
  height = 5,
  max_subsample_size = 250,
  ...
)

violin_netsummary(A, ...)

Arguments

Details

Vertex sampling is done by simple random sampling without replacement.

The automatically selected subsample size is capped at max_subsample_size to limit computation time.

Each violin shows the distribution of the subsampled statistic, and a dot marks the mean.

The following input classes are supported: base::matrix, Matrix::dgCMatrix, igraph::igraph, network::network.

Value

A ggplot object. Printed as a side effect when save_plot = FALSE. Returns the plot invisibly when save_plot = TRUE.

References

Maugis et al. (2017). Topology reveals universal features for network comparison. arXiv: 1705.05677

Alon et al. (1997). Finding and counting given length cycles. Algorithmica 17, 209–223 (1997). https://doi.org/10.1007/BF02523189

Examples

{
set.seed(2022)
#Generating Erdos-Renyi graph
n <- 400
#igraph object
A <- igraph::sample_gnp(n, 0.05)
netsummary_plot(A)
}

#sparse adjacency matrix
A2 <- igraph::as_adjacency_matrix(A)
netsummary_plot(A2)

#dense adjacency matrix
A2 <- igraph::as_adjacency_matrix(A, sparse = FALSE)
netsummary_plot(A2)

#user-specified n_rep and subsample_sizes
netsummary_plot(A, n_rep = 500, subsample_sizes = 150)

#user-specified alpha
netsummary_plot(A, alpha = 0.1)

#network object
A3 <- network::as.network(igraph::as_adjacency_matrix(A, sparse = FALSE))
netsummary_plot(A3)

#user-specified max_subsample_size
netsummary_plot(A, max_subsample_size = 100)

#saving the plot with user-specified file name
netsummary_plot(A, save_plot = TRUE,
                filename = file.path(tempdir(), "myfig.pdf"))

Plot an hnethist object

Description

Plots a heatmap or a BIC curve for an hnethist object.

Usage

## S3 method for class 'hnethist'
plot(x, type = "nethist", at = NULL, ...)

Arguments

Value

Called for its side effects (plotting). Returns NULL invisibly.

See Also

plot.nethist(), hnethist()

Examples

set.seed(2022)
A <- igraph::as_adjacency_matrix(
  igraph::sample_gnp(100, 0.3), sparse = FALSE)
fit <- suppressMessages(hnethist(A))
plot(fit)
plot(fit, type = "BIC")

Network histogram plot

Description

Drawing lattice::levelplot() using a multinethist object.

Usage

## S3 method for class 'multinethist'
plot(
  x,
  y = NA,
  type = "nethist",
  idx_order = 1:max(x$cluster),
  power = 0.25,
  col.regions = function(n) grDevices::hcl.colors(n, palette = "Reds 3", rev = TRUE),
  colorkey = FALSE,
  prob = FALSE,
  digits = 2,
  prob.cex = 0.1 + 0.5/log10(max(x$cluster)),
  prob.col = "white",
  layout = NULL,
  layer_titles = NULL,
  at = NULL,
  ...
)

Arguments

Value

Called for its side effects (plotting). Returns NULL invisibly.

Examples

set.seed(42)
data(IndianVil)
mnhist_Ind_vil <- multinethist(IndianVil)
plot(mnhist_Ind_vil)
plot(mnhist_Ind_vil, power = 0.5)
plot(mnhist_Ind_vil, layout = c(3,4))
plot(mnhist_Ind_vil, layer_titles = paste0("Network ", seq_along(mnhist_Ind_vil$rho_hat)))

Network histogram plot

Description

Drawing lattice::levelplot() using a nethist object.

Usage

## S3 method for class 'nethist'
plot(
  x,
  type = "nethist",
  idx_order = 1:max(x$cluster),
  power = 0.25,
  col.regions = function(n) grDevices::hcl.colors(n, palette = "Reds 3", rev = TRUE),
  colorkey = FALSE,
  prob = FALSE,
  digits = 2,
  prob.cex = 0.1 + 0.5/log10(max(x$cluster)),
  prob.col = "white",
  at = NULL,
  y = NA,
  ...
)

Arguments

Value

Called for its side effects (plotting). Returns NULL invisibly.

Examples

set.seed(2022)
A <- igraph::sample_gnp(200, 0.05)
hist_A <- nethist(A)
plot(hist_A)
plot(hist_A, power = 0.5)
plot(hist_A, type = "prob", prob = TRUE)

3D histogram plot for nethist objects

Description

Drawing plot3D::hist3D() using a nethist, multinethist, or hnethist object with a user-specified order.

Usage

plot3d(x, idx_order = 1:max(x$cluster), type = "nethist", ...)

## S3 method for class 'nethist'
plot3d(x, idx_order = 1:max(x$cluster), type = "nethist", ...)

## S3 method for class 'hnethist'
plot3d(x, idx_order = 1:max(x$cluster), type = "nethist", ...)

## S3 method for class 'multinethist'
plot3d(x, idx_order = 1:max(x$cluster), type = "nethist", ...)

Arguments

Value

Called for its side effects (plotting). Returns NULL invisibly.

Examples

set.seed(42)
data(IndianVil)
mnhist_Ind_vil <- multinethist(IndianVil)
plot3d(mnhist_Ind_vil)

data(polblog)
fit <- nethist(polblog)
plot3d(fit)

Political blog

Description

A pre-processed version of the Political Blog dataset from Olhede and Wolfe (2014), based on the original data by Adamic and Glance (2005). The provided igraph object represents the graph after removing zero-degree nodes and simplifying the graph structure. The graph is derived from the edge list polblog_edgelist.

Usage

data(polblog)

Format

polblog is an igraph object, which is pre-processed data symmetrize and simplified without self-loops.

Details

The adjancency matrix from polblog_edgelist is sparse, assymetric, so it needs to be symmetrized if a method requires a symmetric matrix. Nodes with zero degree need to be removed. All edges are considered as undirected edges. Then, we get the undirected version of dataset as polblog.

First 586 blogs are liberal; remaining 638 are conservative.

Source

http://www-personal.umich.edu/~mejn/netdata/

https://github.com/p-wolfe/network-histogram-code

References

Adamic, L. A., & Glance, N. (2005). The political blogosphere and the 2004 US election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery (pp. 36-43)

Examples

data(polblog_edgelist)
data(polblog)

#From polblog_edgelist to polblog
G<- igraph::graph_from_edgelist(as.matrix(polblog_edgelist), directed = FALSE)
G<- igraph::delete.vertices(G, igraph::degree(G) == 0)
G<- igraph::simplify(G)

polblog

Political blog (edgelist)

Description

Political blog data set from Olhede and Wolfe (2014), which is part of the original data set from Adamic and Glance (2005). The provided edgelist is from GitHub repository of Prof. Patrick Wolfe.

Usage

data("polblog_edgelist")

Format

polblog_edgelist is a matrix for the edge list from https://github.com/p-wolfe/network-histogram-code.

V1

a numeric vector of tail vertices.

V2

a numeric vector of head vertices.

Details

First 586 blogs are liberal; remaining 638 are conservative. Nodes with zero degree need to be removed.

Source

http://www-personal.umich.edu/~mejn/netdata/

https://github.com/p-wolfe/network-histogram-code

References

Adamic, L. A., & Glance, N. (2005). The political blogosphere and the 2004 US election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery (pp. 36-43)

Examples

data(polblog_edgelist)
data(polblog)

#From polblog_edgelist to polblog
G<- igraph::graph_from_edgelist(as.matrix(polblog_edgelist), directed = FALSE)
G<- igraph::delete.vertices(G, igraph::degree(G) == 0)
G<- igraph::simplify(G)

polblog

Print nethist objects

Description

Prints the estimated probability matrix and model summary for nethist, multinethist, and hnethist objects.

Usage

## S3 method for class 'nethist'
print(x, ...)

## S3 method for class 'multinethist'
print(x, ...)

## S3 method for class 'hnethist'
print(x, ...)

Arguments

Value

The input object, invisibly.

Examples

set.seed(42)
data(polblog)
fit <- suppressMessages(nethist(polblog))
print(fit)