fastRG quickly samples a broad class of network models known as
generalized random dot product graphs (GRDPGs). In particular, for
matrices fastRG samples a matrix
fastRG has two primary use cases:
- Sampling enormous sparse graphs that cannot feasibly be sampled with existing samplers, and
- validating new methods for random dot product graphs (and variants).
fastRG makes the latent parameters of random dot product graphs
readily available to users, such that simulation studies for community
detection, subspace recovery, etc, are straightforward.
You can install the released version of fastRG from CRAN with:
install.packages("fastRG")And the development version from GitHub with:
# install.packages("devtools")
devtools::install_github("RoheLab/fastRG")There are two stages to sampling from generalized random dot product
graphs. First, we sample the latent factors fastRG mimics this two-stage
sample structure. For example, to sample from a stochastic blockmodel,
we first create the latent factors.
library(fastRG)
#> Loading required package: Matrix
set.seed(27)
sbm <- sbm(n = 1000, k = 5, expected_density = 0.01)
#> Generating random mixing matrix `B` with independent Uniform(0, 1) entries. This distribution may change in the future. Explicitly set `B` for reproducible results.You can specify the latent factors and the mixing matrix Uniform[0, 1] entries and nodes were assigned
randomly to communities with equal probability of falling in all
communities. Printing the result object gives us some additional
information:
sbm
#> Undirected Stochastic Blockmodel
#> --------------------------------
#>
#> Nodes (n): 1000 (arranged by block)
#> Blocks (k): 5
#>
#> Traditional SBM parameterization:
#>
#> Block memberships (z): 1000 [factor]
#> Block probabilities (pi): 5 [numeric]
#> Factor model parameterization:
#>
#> X: 1000 x 5 [dgCMatrix]
#> S: 5 x 5 [dgeMatrix]
#>
#> Poisson edges: TRUE
#> Allow self loops: TRUE
#>
#> Expected edges: 4995
#> Expected degree: 5
#> Expected density: 0.01Now, conditional on this latent representation, we can sample graphs.
fastRG supports several different output types, each of which is
specified by the suffix to sample_*() functions. For example, we can
obtain an edgelist in a tibble with:
sample_edgelist(sbm)
#> # A tibble: 2,488 × 2
#> from to
#> <int> <int>
#> 1 4 155
#> 2 46 141
#> 3 42 56
#> 4 42 55
#> 5 72 167
#> 6 32 68
#> 7 67 75
#> 8 10 164
#> 9 30 154
#> 10 74 182
#> # ℹ 2,478 more rowsbut we can just as easily obtain the graph as a sparse matrix
A <- sample_sparse(sbm)
A[1:10, 1:10]
#> 10 x 10 sparse Matrix of class "dsCMatrix"
#>
#> [1,] . . . . . . . . . .
#> [2,] . . . . . . . . . 1
#> [3,] . . . . . . . . . .
#> [4,] . . . . . . . . . .
#> [5,] . . . . . . . . . .
#> [6,] . . . . . . . . . .
#> [7,] . . . . . . . . . .
#> [8,] . . . . . . . . . .
#> [9,] . . . . . . . . . .
#> [10,] . 1 . . . . . . . .or an igraph object
sample_igraph(sbm)
#> IGRAPH efee0ad UN-- 1000 2476 --
#> + attr: name (v/c)
#> + edges from efee0ad (vertex names):
#> [1] 7 --19 32 --33 57 --194 56 --178 119--172 47 --90 47 --117 118--182
#> [9] 73 --100 54 --82 122--143 94 --177 55 --199 70 --186 9 --134 66 --173
#> [17] 1 --174 121--159 21 --41 75 --142 139--142 78 --108 97 --140 120--163
#> [25] 88 --132 18 --189 6 --69 37 --128 42 --184 5 --30 16 --77 106--130
#> [33] 83 --116 25 --179 7 --187 55 --84 127--197 161--174 54 --61 120--192
#> [41] 103--164 66 --147 37 --185 80 --113 94 --144 83 --173 90 --186 65 --118
#> [49] 3 --124 153--160 93 --161 58 --122 155--167 115--200 48 --61 138--141
#> [57] 29 --173 71 --197 14 --79 21 --176 61 --65 117--200 138--153 99 --194
#> + ... omitted several edgesNote that every time we call sample_*() we draw a new sample.
A <- sample_sparse(sbm)
B <- sample_sparse(sbm)
all(A == B) # random realizations from the SBM don't match!
#> [1] FALSEIf you would like to obtain the singular value decomposition of the population adjacency matrix conditional on latent factors, that is straightforward:
s <- eigs_sym(sbm)
s$values
#> [1] 5.0838486 1.8176036 0.6987030 -0.5157282 -0.8208442Note that eigendecompositions and SVDS (for directed graphs) use
RSpectra and do not require explicitly forming large dense population
adjacency matrices; the population decompositions should be efficient in
both time and space for even large graphs.
There are several essential tools to modify graph sampling that you should know about. First there are options that affect the latent factor sampling:
-
expected_degree: Set the expected average degree of the graph by scaling sampling probabilities. We strongly, strongly recommend that you always set this option. If you do not, it is easy accidentally sample from large and dense graphs. -
expected_density: Set the expected density of the graph by scaling sampling probabilities. You cannot specify bothexpected_degreeandexpected_densityat the same time.
In the second stage of graph sampling, the options are:
-
poisson_edges: EitherTRUEorFALSEdepending on whether you would like a Bernoulli graph or a Poisson multi-graph. Scaling viaexpected_degreeassumes a Poisson multi-graph, with some limited exceptions. -
allow_self_edges: Whether nodes should be allowed to connect to themselves. EitherTRUEorFALSE.
igraph allows users to sample SBMs (in
You can find the original research code associated with fastRG
here. There is also a Python
translation of the original code in Python
here.
Both of these implementations are bare bones.
[1] Rohe, Karl, Jun Tao, Xintian Han, and Norbert Binkiewicz. 2017. “A Note on Quickly Sampling a Sparse Matrix with Low Rank Expectation.” Journal of Machine Learning Research; 19(77):1-13, 2018. https://www.jmlr.org/papers/v19/17-128.html