fastRG

Major changes

• This release fixes a long-standing inconsistency in how degrees are counted, which resulted in sampling twice as many edges as desired in undirected_factor_model(). See below for details (#19). This also caused population singular values for undirected factors models to be off by a factor of 2 (#31).

Breaking changes

• Specifying both k and B in dcsbm() and sbm() now results in an error. You should only specify one of these arguments.
• It is now possible to specify the precise number of nodes in each block of a dcsbm() (and subclasses sbm() and planted_partition()) via the block_sizes argument. This makes it easier to construct blockmodels with exactly repeated eigenvalues. Additionally, the default behavior is now to use this argument and to balance block sizes as evenly as possible. Previously, the default behavior was to sample blocks memberships with equal probability.

Non-breaking changes

• Added vignette("consistency") demonstrating how to check consistency of spectral estimators using fastRG for sampling and population spectra computations (#33, #43)

Details about degree over-sampling bug and the fix

The fastRG sampling algorithm, as implemented in sample_edgelist.matrix(), is fundamentally a sampler for asymmetric, directed networks with conditional expectation $\mathbb E[A \mid X, S, Y] = X S Y^\top \in \mathbb R^{n_1 \times n_2}$. That is, you can think of the sampler as a very efficient procedure for iterating through $i = 1, ..., n_1$ and $j = 1, ..., n_2$ and sampling from a Poisson with rate $(X S Y^\top)_{ij}$.

However, we would also like to use this same sampler to sample from undirected networks. In an undirected networks, the conditional expectation $\mathbb E[A \mid X, S] = X S X^\top \in \mathbb R^{n \times n}$ is a square matrix with $(X S X^\top)_{ij} = (X S X^\top)_{ji}$. To sample from this matrix, it's typical to sample the upper triangle of $A$ from a Poisson with rate $(X S X^\top)_{ij}$ for all $1 \le i \le j \le n$, and then fill the lower triangle of $A$ to make $A$ symmetric.

Since the fastRG algorithm samples $A_{ij}$ for all $i, j$, not just the upper triangle of $A$, we use a trick to sample from undirected networks. First, we force the conditional expectation to be symmetric by symmetrizing $S$. Then, we still sample for all $i, j$. That is, to set $A_{ij}$ we sample once from a Poisson with rate $(X S X^\top)_{ij}$ and once from a Poisson with rate $(X S X^\top)_{ji}$ (these rates are equal by symmetry!). Then we set $A_{ij} = A_{ji}$ to the sum of these Poisson random variables. The issue is that this doubles the expected value of $A_{ij} = A_{ji}$ and so we sample twice as many edges as we should. Up until this release of fastRG, we've unfortunately been doing this double sampling in undirected networks (#19).

In this release, we fix this over-sampling. The key is that we divide $S$ by two at sampling time. We do not modify $S$ at all in the undirected_factor_model()! You can always use $X S X^\top$ to compute the expected value of $A$. This new change *only affects sampling*.