Package 'nett'

Description

The adjusted spectral goodness-of-fit test based on Poisson DCSBM.

The test is a natural extension on Lei's work of testing goodness-of-fit for SBM. The residual matrix $\tilde{A}$ is computed from the DCSBM estimation expectation of A. To speed up computation, the residual matrix uses Poisson variance instead. Specifically,

$\tilde{A}_{ij} = (A_{ij} - \hat P_{ij}) / ( n \hat P_{ij})^{1/2}, \quad \hat P_{ij} = \hat \theta_i \hat \theta_j \hat B_{\hat{z}_i, \hat{z}_j} \cdot 1\{i \neq j\}$

where $\hat{\theta}$ and $\hat{B}$ are computed using estim_dcsbm if not provided.

Adjusted spectral test

Usage

adj_spec_test(
  A,
  K,
  z = NULL,
  DC = TRUE,
  theta = NULL,
  B = NULL,
  cluster_fct = spec_clust,
  ...
)

Arguments

Value

Adjusted spectral test statistics.

References

Details of modification can be seen at Adjusted chi-square test for degree-corrected block models, Linfan Zhang, Arash A. Amini, arXiv preprint arXiv:2012.15047, 2020.

The original spectral test is from A goodness-of-fit test for stochastic block models Lei, Jing, Ann. Statist. 44 (2016), no. 1, 401–424. doi:10.1214/15-AOS1370.

Description

Estimate the number of communities under block models by using the spectral properties of network Beth-Hessian matrix with moment correction.

Usage

bethe_hessian_select(A, Kmax)

Arguments

Value

A list of result

References

Estimating the number of communities in networks by spectral methods, Can M. Le, Elizaveta Levina, arXiv preprint arXiv:1507.00827, 2015

Description

Compute the block sum of an adjacency matrix given a label vector.

Usage

compute_block_sums(A, z)

Arguments

Value

A K x L matrix with (k,l)-th element as $sum_{i,j} A_{i,j} 1{z_i = k, z_j = l}$

Description

Compute confusion matrix

Usage

compute_confusion_matrix(z, y, K = NULL)

Arguments

Value

A KxK confusion matrix between z and y

Description

Compute the NMI between two label vectors with the same cluster number

Usage

compute_mutual_info(z, y)

Arguments

Value

NMI between z and y

Description

Compute the block sum of an adjacency matrix given a label vector.

Usage

estim_dcsbm(A, z)

Arguments

Details

$\hat B_{k\ell} = \frac{N_{k\ell}(\hat z)}{m_{k\ell} (\hat z)}, \quad \hat \theta_i = \frac{n_{\hat z_i}(\hat z) d_i}{\sum_{j : \hat z_j = \hat z_i} d_i}$

where $N_{k\ell}(\hat{z})$ is the sum of the elements of A in block $(k,\ell)$ specified by labels $\hat z$, $n_k(\hat z)$ is the number of nodes in community $k$ according to $\hat z$ and $m_{k\ell}(\hat z) = n_k(\hat z) (n_\ell(\hat z) - 1\{k = \ell\})$

Value

A list of result

Description

compute BIC score when fitting a DCSBM to network data

Usage

eval_dcsbm_bic(A, z, K, poi)

Arguments

Details

the BIC score is calculated by -2*log likelihood minus $K\times(K + 1)\times log(n)$

Value

BIC score

References

BIC score is originally proposed in Likelihood-based model selection for stochastic block models Wang, YX Rachel, Peter J. Bickel, The Annals of Statistics 45, no. 2 (2017): 500-528.

The details of modified implementation can be found in Adjusted chi-square test for degree-corrected block models, Linfan Zhang, Arash A. Amini, arXiv preprint arXiv:2012.15047, 2020.

See Also

eval_dcsbm_like, eval_dcsbm_loglr

Description

Compute the log likelihood of a DCSBM, using estimated parameters B, theta based on the given label vector

Usage

eval_dcsbm_like(A, z, poi = TRUE, eps = 1e-06)

Arguments

Details

The log likelihood is calculated by

$\ell(\hat B,\hat \theta, \hat \pi, \hat z \mid A) = \sum_i \log \hat \pi_{z_i} + \sum_{i < j} \phi(A_{ij};\hat \theta_i \hat \theta_j \hat B_{\hat{z}_i \hat{z}_j} )$

where $\hat B$, $\hat \theta$ is calculated by estim_dcsbm, $\hat{\pi}_k$ is the proportion of nodes in community k.

Value

log likelihood of a DCSBM

See Also

eval_dcsbm_loglr, eval_dcsbm_bic

Description

Computes the log-likelihood ratio of one DCSBM relative to another, using estimated parameters B and theta based on the given label vectors.

Usage

eval_dcsbm_loglr(A, labels, poi = TRUE, eps = 1e-06)

Arguments

Details

The log-likehood ratio is computed between two DCSBMs specified by the columns of labels. The function computes the log-likelihood ratio of the model with labels[ , 2] w.r.t. the model with labels[ , 1]. This is often used with two label vectors fitted using different number of communities (say K and K+1).

When poi is set to TRUE, the function uses fast sparse matrix computations and is scalable to large sparse networks.

Value

log-likelihood ratio

See Also

eval_dcsbm_like, eval_dcsbm_bic

Description

Extract the largest connected component of a network

Usage

extract_largest_cc(gr, mode = "weak")

Arguments

Value

An igraph object

Description

Extract a low-degree connected component of a network

Usage

extract_low_deg_comp(g, deg_prec = 0.75, verb = FALSE)

Arguments

Value

An igraph object

Description

The Conditional Pseudo-Likelihood (CPL) algorithm for fitting degree-corrected block models

Usage

fast_cpl(Amat, K, ilabels = NULL, niter = 10)

Arguments

Details

The function implements the CPL algorithm as described in the paper below. It relies on the mixtools package for fitting a mixture of multinomials to a block compression of the adjacency matrix based on the estimated labels and then reiterates.

Technically, fast_cpl fits a stochastic block model (SBM) conditional on the observed node degrees,to account for the degree heterogeneity within communities that is not modeled well in SBM. CPL can also be used to effectively estimate the parameters of the degree-corrected block model (DCSBM).

The code is an adaptation of the original R code by Aiyou Chen with slight simplifications.

Value

Estimated community label vector.

References

For more details, see Pseudo-likelihood methods for community detection in large sparse networks, A. A. Amini, A. Chen, P. J. Bickel, E. Levina, Annals of Statistics 2013, Vol. 41 (4), 2097—2122.

Examples

head(fast_cpl(igraph::as_adj(polblogs), 2), 50)

Description

Samples an adjacency matrix from a stochastic block model (SBM)

Usage

fast_sbm(z, B)

Arguments

Details

The function implements a fast algorithm for sampling sparse SBMs, by only sampling the necessary nonzero entries. This function is adapted almost verbatim from the original code by Aiyou Chen.

Value

An adjacency matrix following SBM

Examples

B = pp_conn(n = 10^4, oir = 0.1, lambda = 7, pri = rep(1,3))$B
head(fast_sbm(sample(1:3, 10^4, replace = TRUE), B))

Description

Creates a randomly permuted DCPP connectivity matrix with a given average expected degree

Usage

gen_rand_conn(n, K, lambda, gamma = 0.3, pri = rep(1, K)/K, theta = rep(1, n))

Arguments

Details

The connectivity matrix is a convex combination of a random symmetric permutation matrix and the matrix of all ones, with weights gamm and 1-gamma.

Value

connectivity matrix B of the desired DCSBM.

Description

Calculate the expected average degree of a DCSBM

Usage

get_dcsbm_exav_deg(n, pri, B, ex_theta = 1)

Arguments

Value

expected average degree of a DCSBM

Description

Convert label matrix to vector

Usage

label_mat2vec(Z)

Arguments

Value

A label vector that follows the assignment matrix

Description

Convert label vector to matrix

Usage

label_vec2mat(z, K = NULL, sparse = FALSE)

Arguments

Value

A cluster assignment matrix that follows from the label vector z

Description

The NAC test to measure the goodness-of-fit of the DCSBM to network data.

The function computes the NAC+ or NAC statistics in the paper below. Label vectors, if not provided, are estimated using spec_clust by default but one can also use any other community detection algorithms through cluster_fct. Note that the function has to have A and K as its first two arguments, and additional arguments could be provided through ....

Usage

nac_test(A, K, z = NULL, y = NULL, plus = TRUE, cluster_fct = spec_clust, ...)

Arguments

Value

A list of result

References

Adjusted chi-square test for degree-corrected block models, Linfan Zhang, Arash A. Amini, arXiv preprint arXiv:2012.15047, 2020.

See Also

snac_test

Examples

A <- sample_dcpp(500, 10, 4, 0.1)$adj
nac_test(A, K = 4)$stat
nac_test(A, K = 4, cluster_fct = fast_cpl)$stat

Description

Plot the degree distribution of a network on log scale

Usage

plot_deg_dist(gr, logx = TRUE)

Arguments

Value

Histogram of the degree of 'gr'.

Description

Plot a network using degree-modulated node sizes, community colors and other enhancements

Usage

plot_net(
  gr,
  community = NULL,
  color_map = NULL,
  extract_lcc = TRUE,
  heavy_edge_deg_perc = 0.97,
  coord = NULL,
  vsize_func = function(deg) log(deg + 3) * 1,
  vertex_border = FALSE,
  niter = 1000,
  vertex_alpha = 0.4,
  remove_loops = TRUE,
  make_simple = FALSE,
  ...
)

Arguments

Value

A network plot

Description

Plot ROC curves given results from simulate_roc.

Usage

plot_roc(roc_results, method_names = NULL, font_size = 16)

Arguments

Value

Roc plot based on results from simulate_roc

Description

Plot the smooth community profiles based on a resampled statistic

Usage

plot_smooth_profile(
  tstat,
  net_name = "",
  trunc_type = "none",
  spar = 0.3,
  plot_null_spar = TRUE,
  alpha = 0.3,
  base_font_size = 12
)

Arguments

Value

smooth profile plot of a network

Description

This is a directed network of hyperlinks between political blogs about politics in the United States of America.

Usage

data(polblogs)

Format

An igraph data with 1490 nodes and 19090 edges

References

Data source. Original paper:The political blogosphere and the 2004 US election: divided they blog, Adamic, Lada A., and Natalie Glance. "." Proceedings of the 3rd international workshop on Link discovery. 2005.

Description

Create a degree-corrected planted partition connectivity matrix with a given average expected degree.

Usage

pp_conn(
  n,
  oir,
  lambda,
  pri,
  theta = rep(1, n),
  normalize_theta = FALSE,
  d = rep(1, length(pri))
)

Arguments

Value

The connectivity matrix B of the desired DCSBM.

Description

The usual "printf" function

Usage

printf(...)

Arguments

Value

the value of the printing object

Description

Generate a random symmetric permutation matrix (recursively)

Usage

rsymperm(K)

Arguments

Value

A random K x K symmetric permutation matrix

Description

Sample an adjacency matrix from a degree-corrected Erdős–Rényi model (DCER).

Usage

sample_dcer(theta)

Arguments

Value

An adjacency matrix following DCSBM

Description

A DCLVM with $K$ clusters has edges generated as

$E[\,A_{ij} \mid x, \theta\,] \;\propto\; \theta_i \theta_j e^{- \|x_i - x_j\|^2}$

where $x_i = 2 e_{z_i} + w_i$, $e_k$ is the $k$th basis vector of $R^d$, $w_i \sim N(0, I_d)$, and $\{z_i\} \subset [K]^n$. The proportionality constant is chosen such that the overall network has expected average degree $\lambda$. To calculate the scaling constant, we approximate $E[e^{- \|x_i - x_j\|^2}]$ for $i \neq j$ by generating random npairs $\{z_i, z_j\}$ and average over them.

Usage

sample_dclvm(z, lambda, theta, npairs = NULL)

Arguments

Details

Sample form a degree-corrected latent variable model with Gaussian kernel

Value

Adjacency matrix of DCLVM

Description

Sample from a degree-corrected planted partition model

Usage

sample_dcpp(
  n,
  lambda,
  K,
  oir,
  theta = NULL,
  pri = rep(1, K)/K,
  normalize_theta = FALSE
)

Arguments

Value

an adjacency matrix following a degree-corrected planted parition model

See Also

sample_dcsbm, sample_tdcsbm

Description

Sample an adjacency matrix from a degree-corrected block model (DCSBM)

Usage

sample_dcsbm(z, B, theta = 1)

Arguments

Value

An adjacency matrix following DCSBM

See Also

sample_dcpp, fast_sbm, sample_tdcsbm

Examples

B = pp_conn(n = 10^3, oir = 0.1, lambda = 7, pri = rep(1,3))$B
head(sample_dcsbm(sample(1:3, 10^3, replace = TRUE), B, theta = rexp(10^3)))

Description

Sample an adjacency matrix from a truncated degree-corrected block model (DCSBM) using a fast algorithm.

Usage

sample_tdcsbm(z, B, theta = 1)

Arguments

Details

The function samples an adjacency matrix from a truncated DCSBM, with entries having Bernoulli distributions with mean

$E[A_{ij} | z] = B_{z_i, z_j} \min(1, \theta_i \theta_j).$

The approach uses the masking idea of Aiyou Chen, leading to fast sampling for sparse networks. The masking, however, truncates $\theta_i \theta_j$ to at most 1, hence we refer to it as the truncated DCSBM.

Value

An adjacency matrix following DCSBM

Examples

B = pp_conn(n = 10^4, oir = 0.1, lambda = 7, pri = rep(1,3))$B
head(sample_tdcsbm(sample(1:3, 10^4, replace = TRUE), B, theta = rexp(10^4)))

Description

Simulate data from the null and alternative distributions to estimate ROC curves for a collection of methods.

Usage

simulate_roc(
  apply_methods,
  gen_null_data,
  gen_alt_data,
  nruns = 100,
  core_count = parallel::detectCores() - 1,
  seed = NULL
)

Arguments

Value

a list of result

Description

Implements the Sinkhorn–Knopp algorithm for transforming a square matrix with positive entries to a stochastic matrix with given common row and column sums (e.g., a doubly stochastic matrix).

Usage

sinkhorn_knopp(
  A,
  sums = rep(1, nrow(A)),
  niter = 100,
  tol = 1e-08,
  sym = FALSE,
  verb = FALSE
)

Arguments

Details

Computes diagonal matrices D1 and D2 to make D1AD2 into a matrix with given row/column sums. For a symmetric matrix A, one can set sym = TRUE to compute a symmetric scaling DAD.

Value

Diagonal matrices D1 and D2 to make D1AD2 into a matrix with given row/column sums.

Description

Compute SNAC+ with resampling

Usage

snac_resample(
  A,
  nrep = 20,
  Kmin = 1,
  Kmax = 13,
  ncores = parallel::detectCores() - 1,
  seed = 1234
)

Arguments

Value

A data frame with columns specifying repetition cycles, number of community numbers and the value of SNAC+ statistics

Description

Applying SNAC+ test sequentially to estimate community number of a network fit to DCSBM

Usage

snac_select(
  A,
  Kmin = 1,
  Kmax,
  alpha = 1e-05,
  labels = NULL,
  cluster_fct = spec_clust,
  ...
)

Arguments

Value

estimated community number.

See Also

snac_test

Examples

A <- sample_dcpp(500, 10, 3, 0.1)$adj
snac_select(A, Kmax = 6)

Description

The SNAC test to measure the goodness-of-fit of the DCSBM to network data.

The function computes the SNAC+ or SNAC statistics in the paper below. The row label vector of the adjacency matrix could be given through z otherwise will be estimated by cluster_fct. One can specify the ratio of nodes used to estimate column label vector. If plus = TRUE, the column labels will be estimated by spec_clust with (K+1) clusters, i.e. performing SNAC+ test, otherwise with K clusters SNAC test. One can also get multiple test statistics with repeated random subsampling on nodes.

Usage

snac_test(
  A,
  K,
  z = NULL,
  ratio = 0.5,
  fromEachCommunity = TRUE,
  plus = TRUE,
  cluster_fct = spec_clust,
  nrep = 1,
  ...
)

Arguments

Value

A list of result

References

Adjusted chi-square test for degree-corrected block models, Linfan Zhang, Arash A. Amini, arXiv preprint arXiv:2012.15047, 2020.

See Also

nac_test

Examples

A <- sample_dcpp(500, 10, 4, 0.1)$adj
snac_test(A, K = 4, niter = 3)$stat

Description

Perform spectral clustering (with regularization) to estimate communities

Usage

spec_clust(
  A,
  K,
  type = "lap",
  tau = 0.25,
  nstart = 20,
  niter = 10,
  ignore_first_col = FALSE
)

Arguments

Value

A label vector of size n x 1 with elements in 1,2,...,K

Description

Provides a spectral representation of the network (with regularization) based on the adjacency or Laplacian matrices

Usage

spec_repr(A, K, type = "lap", tau = 0.25, ignore_first_col = FALSE)

Arguments

Value

The n x K matrix resulting from a spectral embedding of the network into R^K