In RoheLab/gdim: Estimate Graph Dimension using Cross-Validated Eigenvalues

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>",
  fig.path = "man/figures/README-",
  out.width = "100%"
)

gdim

gdim estimates graph dimension using cross-validated eigenvalues, via the graph-splitting technique developed in https://arxiv.org/abs/2108.03336. Theoretically, the method works by computing a special type of cross-validated eigenvalue which follows a simple central limit theorem. This allows users to perform hypothesis tests on the rank of the graph.

Installation

You can install gdim from CRAN with:

install.packages("gdim")

# to get the development version from GitHub:
install.packages("pak")
pak::pak("RoheLab/gdim")

Example

eigcv() is the main function in gdim. The single required parameter for the function is the maximum possible dimension, k_max.

In the following example, we generate a random graph from the stochastic block model (SBM) with 1000 nodes and 5 blocks (as such, we would expect the estimated graph dimension to be 5).

library(fastRG)

B <- matrix(0.1, 5, 5)
diag(B) <- 0.3

model <- sbm(
  n = 1000,
  k = 5,
  B = B,
  expected_degree = 40,
  poisson_edges = FALSE,
  allow_self_loops = FALSE
)

A <- sample_sparse(model)

Here, A is the adjacency matrix.

Now, we call the eigcv() function with k_max=10 to estimate graph dimension.

library(gdim)

eigcv_result <- eigcv(A, k_max = 10)
eigcv_result

In this example, eigcv() suggests k=5.

To visualize the result, use plot() which returns a ggplot object. The function displays the test statistic (z score) for each hypothesized graph dimension.

plot(eigcv_result)

Reference

Chen, Fan, Sebastien Roch, Karl Rohe, and Shuqi Yu. “Estimating Graph Dimension with Cross-Validated Eigenvalues.” ArXiv:2108.03336 [Cs, Math, Stat], August 6, 2021. https://arxiv.org/abs/2108.03336.

RoheLab/gdim documentation built on Sept. 13, 2023, 1:55 a.m.