Package 'fastRG'

Title: Sample Generalized Random Dot Product Graphs in Linear Time
Description: Samples generalized random product graphs, a generalization of a broad class of network models. Given matrices X, S, and Y with with non-negative entries, samples a matrix with expectation X S Y^T and independent Poisson or Bernoulli entries using the fastRG algorithm of Rohe et al. (2017) <https://www.jmlr.org/papers/v19/17-128.html>. The algorithm first samples the number of edges and then puts them down one-by-one. As a result it is O(m) where m is the number of edges, a dramatic improvement over element-wise algorithms that which require O(n^2) operations to sample a random graph, where n is the number of nodes.
Authors: Alex Hayes [aut, cre, cph] (ORCID: <https://orcid.org/0000-0002-4985-5160>), Karl Rohe [aut, cph], Jun Tao [aut], Xintian Han [aut], Norbert Binkiewicz [aut]
Maintainer: Alex Hayes <[email protected]>
License: MIT + file LICENSE
Version: 0.4.0.9000
Built: 2026-11-18 00:09:59 UTC
Source: https://github.com/rohelab/fastrg

Help Index


Create an undirected Chung-Lu object

Description

To specify a Chung-Lu graph, you must specify the degree-heterogeneity parameters (via n or theta). We provide reasonable defaults to enable rapid exploration or you can invest the effort for more control over the model parameters. We strongly recommend setting the expected_degree or expected_density argument to avoid large memory allocations associated with sampling large, dense graphs.

Usage

chung_lu(
  n = NULL,
  theta = NULL,
  ...,
  sort_nodes = TRUE,
  poisson_edges = TRUE,
  allow_self_loops = TRUE,
  force_identifiability = FALSE
)

Arguments

n

(degree heterogeneity) The number of nodes in the graph. Use when you don't want to specify the degree-heterogeneity parameters theta by hand. When n is specified, theta is randomly generated from a LogNormal(2, 1) distribution. This is subject to change, and may not be reproducible. n defaults to NULL. You must specify either n or theta, but not both.

theta

(degree heterogeneity) A numeric vector explicitly specifying the degree heterogeneity parameters. This implicitly determines the number of nodes in the resulting graph, i.e. it will have length(theta) nodes. Must be positive. Setting to a vector of ones recovers an erdos renyi graph. Defaults to NULL. You must specify either n or theta, but not both.

...

Arguments passed on to undirected_factor_model

expected_degree

If specified, the desired expected degree of the graph. Specifying expected_degree simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

expected_density

If specified, the desired expected density of the graph, that is, the expected number of edges between distinct nodes divided by choose(n, 2). See expected_density(). Specifying expected_density simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

sort_nodes

Logical indicating whether or not to sort the nodes so that they are grouped by block and by theta. Useful for plotting. Defaults to TRUE.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

force_identifiability

Logical indicating whether or not to normalize theta such that it sums to one within each block. Defaults to FALSE, since this behavior can be surprise when theta is set to a vector of all ones to recover the SBM case.

Value

An undirected_chung_lu S3 object, a subclass of dcsbm().

See Also

Other undirected graphs: dcsbm(), erdos_renyi(), mmsbm(), overlapping_sbm(), planted_partition(), sbm()

Examples

set.seed(27)

cl <- chung_lu(n = 100, expected_density = 0.01)
cl

theta <- round(stats::rlnorm(100, 2))

cl2 <- chung_lu(
  theta = theta,
  expected_degree = 5
)

cl2

edgelist <- sample_edgelist(cl)
edgelist

Create an undirected degree corrected stochastic blockmodel object

Description

To specify a degree-corrected stochastic blockmodel, you must specify the degree-heterogeneity parameters (via n or theta), the mixing matrix (via k or B), and the relative block probabilities (optional, via pi). We provide defaults for most of these options to enable rapid exploration, or you can invest the effort for more control over the model parameters. We strongly recommend setting the expected_degree or expected_density argument to avoid large memory allocations associated with sampling large, dense graphs.

Usage

dcsbm(
  n = NULL,
  theta = NULL,
  k = NULL,
  B = NULL,
  ...,
  block_sizes = NULL,
  pi = NULL,
  sort_nodes = TRUE,
  force_identifiability = FALSE,
  poisson_edges = TRUE,
  allow_self_loops = TRUE
)

Arguments

n

(degree heterogeneity) The number of nodes in the blockmodel. Use when you don't want to specify the degree-heterogeneity parameters theta by hand. When n is specified, theta is randomly generated from a LogNormal(2, 1) distribution. This is subject to change, and may not be reproducible. n defaults to NULL. You must specify either n or theta, but not both.

theta

(degree heterogeneity) A numeric vector explicitly specifying the degree heterogeneity parameters. This implicitly determines the number of nodes in the resulting graph, i.e. it will have length(theta) nodes. Must be positive. Setting to a vector of ones recovers a stochastic blockmodel without degree correction. Defaults to NULL. You must specify either n or theta, but not both.

k

(mixing matrix) The number of blocks in the blockmodel. Use when you don't want to specify the mixing-matrix by hand. When k is specified, the elements of B are drawn randomly from a Uniform(0, 1) distribution. This is subject to change, and may not be reproducible. k defaults to NULL. You must specify either k or B, but not both.

B

(mixing matrix) A k by k matrix of block connection probabilities. The probability that a node in block i connects to a node in community j is Poisson(B[i, j]). Must be a square matrix. matrix and Matrix objects are both acceptable. If B is not symmetric, it will be symmetrized via the update B := B + t(B) / 2. Defaults to NULL. You must specify either k or B, but not both.

...

Arguments passed on to undirected_factor_model

expected_degree

If specified, the desired expected degree of the graph. Specifying expected_degree simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

expected_density

If specified, the desired expected density of the graph, that is, the expected number of edges between distinct nodes divided by choose(n, 2). See expected_density(). Specifying expected_density simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

block_sizes

(block sizes) Number of nodes in each block, as a vector of integers. Must match the dimensions of B, or k and must sum to n. Defaults to NULL, in which case blocks are made to be as balanced as possible. You can specify either pi or block_sizes, but not both.

pi

(block sizes) Relative block probabilities. Must be positive, but do not need to sum to one, as they will be normalized internally. Must match the dimensions of B or k. Defaults to NULL, in which case the block_sizes argument will take precedence. Note that you can specify either pi or block_sizes, but should not specify both.

sort_nodes

Logical indicating whether or not to sort the nodes so that they are grouped by block and by theta. Useful for plotting. Defaults to TRUE. When TRUE, nodes are first sorted by block membership, and then by degree-correction parameters within each block. Additionally, pi is sorted in increasing order, and the columns of the B matrix are permuted to match the new order of pi.

force_identifiability

Logical indicating whether or not to normalize theta such that it sums to one within each block. Defaults to FALSE, since this behavior can be surprise when theta is set to a vector of all ones to recover the SBM case.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Value

An undirected_dcsbm S3 object, a subclass of the undirected_factor_model() with the following additional fields:

  • theta: A numeric vector of degree-heterogeneity parameters.

  • z: The community memberships of each node, as a factor(). The factor will have k levels, where k is the number of communities in the stochastic blockmodel. There will not always necessarily be observed nodes in each community.

  • pi: Sampling probabilities for each block.

  • sorted: Logical indicating where nodes are arranged by block (and additionally by degree heterogeneity parameter) within each block.

Generative Model

There are two levels of randomness in a degree-corrected stochastic blockmodel. First, we randomly chose a block membership for each node in the blockmodel. This is handled by dcsbm(). Then, given these block memberships, we randomly sample edges between nodes. This second operation is handled by sample_edgelist(), sample_sparse(), sample_igraph() and sample_tidygraph(), depending depending on your desired graph representation.

Block memberships

Let ziz_i represent the block membership of node ii. To generate ziz_i we sample from a categorical distribution (note that this is a special case of a multinomial) with parameter π\pi, such that πi\pi_i represents the probability of ending up in the ith block. Block memberships for each node are independent.

Degree heterogeneity

In addition to block membership, the DCSBM also allows nodes to have different propensities for edge formation. We represent this propensity for node ii by a positive number θi\theta_i. Typically the θi\theta_i are constrained to sum to one for identifiability purposes, but this doesn't really matter during sampling (i.e. without the sum constraint scaling BB and θ\theta has the same effect on edge probabilities, but whether BB or θ\theta is responsible for this change is uncertain).

Edge formulation

Once we know the block memberships zz and the degree heterogeneity parameters θ\theta, we need one more ingredient, which is the baseline intensity of connections between nodes in block i and block j. Then each edge Ai,jA_{i,j} is Poisson distributed with parameter

λi,j=θi⋅Bzi,zj⋅θj.\lambda_{i, j} = \theta_i \cdot B_{z_i, z_j} \cdot \theta_j.

See Also

Other stochastic block models: directed_dcsbm(), directed_planted_partition(), mmsbm(), overlapping_sbm(), planted_partition(), sbm()

Other undirected graphs: chung_lu(), erdos_renyi(), mmsbm(), overlapping_sbm(), planted_partition(), sbm()

Examples

set.seed(27)

lazy_dcsbm <- dcsbm(n = 100, k = 5, expected_density = 0.01)
lazy_dcsbm

# sometimes you gotta let the world burn and
# sample a wildly dense graph

dense_lazy_dcsbm <- dcsbm(n = 50, k = 3, expected_density = 0.8)
dense_lazy_dcsbm

# explicitly setting the degree heterogeneity parameter,
# mixing matrix, and relative community sizes rather
# than using randomly generated defaults

k <- 5
n <- 100
B <- matrix(stats::runif(k * k), nrow = k, ncol = k)

theta <- round(stats::rlnorm(n, 2))

pi <- c(1, 2, 4, 1, 1)

custom_dcsbm <- dcsbm(
  theta = theta,
  B = B,
  pi = pi,
  expected_degree = 50
)

custom_dcsbm

edgelist <- sample_edgelist(custom_dcsbm)
edgelist


dcsbm_explicit_block_sizes <- dcsbm(
  theta = rexp(100, 1 / 3) + 1,
  B = B,
  block_sizes = c(13, 17, 40, 14, 16),
  expected_degree = 5
)

# respects block sizes
summary(dcsbm_explicit_block_sizes$z)

# efficient eigendecompostion that leverages low-rank structure in
# E(A) so that you don't have to form E(A) to find eigenvectors,
# as E(A) is typically dense. computation is
# handled via RSpectra

population_eigs <- eigs_sym(custom_dcsbm)

Create a directed degree corrected stochastic blockmodel object

Description

To specify a degree-corrected stochastic blockmodel, you must specify the degree-heterogeneity parameters (via n or theta_out and theta_in), the mixing matrix (via k_out and k_in, or B), and the block sizes (optional, either as relative block probabilities via pi_out and pi_in, or as exact block counts via block_sizes_out and block_sizes_in). By default, outgoing and incoming block memberships and degree parameters are unrelated (a co-factor model); use shared_blocks and shared_theta to tie them together. We provide defaults for most of these options to enable rapid exploration, or you can invest the effort for more control over the model parameters. We strongly recommend setting the expected_out_degree, expected_in_degree, or expected_density argument to avoid large memory allocations associated with sampling large, dense graphs.

Usage

directed_dcsbm(
  n = NULL,
  theta_out = NULL,
  theta_in = NULL,
  k_out = NULL,
  k_in = NULL,
  B = NULL,
  ...,
  block_sizes_out = NULL,
  block_sizes_in = NULL,
  pi_out = NULL,
  pi_in = NULL,
  shared_blocks = FALSE,
  shared_theta = FALSE,
  sort_nodes = TRUE,
  force_identifiability = TRUE,
  poisson_edges = TRUE,
  allow_self_loops = TRUE
)

Arguments

n

(degree heterogeneity) The number of nodes in the blockmodel. Use when you don't want to specify the degree-heterogeneity parameters theta_out and theta_in by hand. When n is specified, theta_out and theta_in are randomly generated from a LogNormal(2, 1) distribution. This is subject to change, and may not be reproducible. n defaults to NULL. You must specify either n or theta_out and theta_in together, but not both. When shared_theta = TRUE, a single vector is generated and used for both theta_out and theta_in.

theta_out

(degree heterogeneity) A numeric vector explicitly specifying the degree heterogeneity parameters. This implicitly determines the number of nodes in the resulting graph, i.e. it will have length(theta_out) nodes. Must be positive. Setting to a vector of ones recovers a stochastic blockmodel without degree correction. Defaults to NULL. You must specify either n or theta_out and theta_in together, but not both. theta_out controls outgoing degree propensity, or, equivalently, row sums of the adjacency matrix.

theta_in

(degree heterogeneity) A numeric vector explicitly specifying the degree heterogeneity parameters. This implicitly determines the number of nodes in the resulting graph, i.e. it will have length(theta) nodes. Must be positive. Setting to a vector of ones recovers a stochastic blockmodel without degree correction. Defaults to NULL. You must specify either n or theta_out and theta_in together, but not both. theta_in controls incoming degree propensity, or, equivalently, column sums of the adjacency matrix.

k_out

(mixing matrix) The number of outgoing blocks in the blockmodel. Use when you don't want to specify the mixing-matrix by hand. When k_out is specified, the elements of B are drawn randomly from a Uniform(0, 1) distribution. This is subject to change, and may not be reproducible. k_out defaults to NULL. You must specify either k_out and k_in together, or B. You may specify all three at once, in which case the number of outgoing blocks is taken from B.

k_in

(mixing matrix) The number of incoming blocks in the blockmodel. Use when you don't want to specify the mixing-matrix by hand. When k_in is specified, the elements of B are drawn randomly from a Uniform(0, 1) distribution. This is subject to change, and may not be reproducible. k_in defaults to NULL. You may specify all three at once, in which case the number of incoming blocks is taken from B.

B

(mixing matrix) A k_out by k_in matrix of block connection probabilities. The probability that a node in block i connects to a node in community j is Poisson(B[i, j]). matrix and Matrix objects are both acceptable. Defaults to NULL. You must specify either k_out and k_in together, or B, but not both.

...

Arguments passed on to directed_factor_model

expected_in_degree

If specified, the desired expected in degree of the graph. Specifying expected_in_degree simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

expected_out_degree

If specified, the desired expected out degree of the graph. Specifying expected_out_degree simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

expected_density

If specified, the desired expected density of the graph. Specifying expected_density simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

block_sizes_out

(block sizes) Number of nodes in each outgoing block, as a vector of non-negative integers. Must match the number of rows of B (or k_out) and must sum to n (or length(theta_out)). When specified, exactly block_sizes_out[j] nodes are assigned to outgoing block j, and which nodes land in which block is uniformly random. Defaults to NULL, in which case outgoing blocks are made to be as balanced as possible, unless pi_out is specified. You can specify either pi_out or block_sizes_out, but not both.

block_sizes_in

(block sizes) Number of nodes in each incoming block, as a vector of non-negative integers. Must match the number of columns of B (or k_in) and must sum to n (or length(theta_in)). When specified, exactly block_sizes_in[j] nodes are assigned to incoming block j, and which nodes land in which block is uniformly random. Defaults to NULL, in which case incoming blocks are made to be as balanced as possible, unless pi_in is specified. You can specify either pi_in or block_sizes_in, but not both.

pi_out

(block sizes) Relative block probabilities for outgoing blocks. Must be positive, but do not need to sum to one, as they will be normalized internally. Must match the rows of B, or k_out. When specified, outgoing block memberships are sampled independently for each node with these probabilities. Defaults to NULL, in which case the block_sizes_out argument (or its balanced default) takes precedence. You can specify either pi_out or block_sizes_out, but not both.

pi_in

(block sizes) Relative block probabilities for incoming blocks. Must be positive, but do not need to sum to one, as they will be normalized internally. Must match the columns of B, or k_in. When specified, incoming block memberships are sampled independently for each node with these probabilities. Defaults to NULL, in which case the block_sizes_in argument (or its balanced default) takes precedence. You can specify either pi_in or block_sizes_in, but not both.

shared_blocks

(block memberships) Logical indicating whether each node should belong to the same outgoing and incoming block. Defaults to FALSE, in which case outgoing and incoming block memberships are sampled independently. When TRUE, a single block membership vector is sampled and used for both, so that z_out and z_in are identical. This requires the same number of outgoing and incoming blocks, i.e. B must be square (or k_out must equal k_in; specifying only one of them is enough). It is enough to specify only one of pi_out and pi_in (or of block_sizes_out and block_sizes_in); if both are specified, they must agree.

shared_theta

(degree heterogeneity) Logical indicating whether each node should have the same propensity to form outgoing and incoming edges. Defaults to FALSE, in which case theta_out and theta_in are unrelated. When TRUE, a single degree-heterogeneity vector is used for both theta_out and theta_in: either specify n (one vector is then generated at random), or only one of theta_out and theta_in. If you specify both theta_out and theta_in, they must be identical. Requires shared_blocks = TRUE, so that the stored theta_out and theta_in are identical (also after normalization by force_identifiability).

sort_nodes

Logical indicating whether or not to sort the nodes so that they are grouped by block. Useful for plotting. Defaults to TRUE. When TRUE, rows of the expected adjacency matrix are first sorted by outgoing block membership, and then by outgoing degree-correction parameters within each outgoing block. A similar sorting procedure occurs independently for the columns, according to the incoming blocks. Additionally, pi_out and pi_in are sorted in increasing order, and the rows and columns of the B matrix are permuted to match the new orderings. When block_sizes_out or block_sizes_in are specified, they are permuted in the same way, so each block keeps exactly the requested number of nodes and its row (or column) of B.

Rows and columns index different nodes. In the default co-factor model (shared_blocks = FALSE), the rows and the columns are permuted independently, so after sorting, row i and column i of the adjacency matrix are generally not the same node. In particular, the diagonal of A (self-loops, see allow_self_loops) does not mean "node i to itself", and X[i, ] and Y[i, ] describe different nodes. If you need rows and columns to index the same nodes, use shared_blocks = TRUE or sort_nodes = FALSE.

When shared_blocks = TRUE, rows and columns are instead permuted together, so that row i and column i of the expected adjacency matrix refer to the same node: nodes are sorted by block, and then by decreasing theta_out and theta_in within each block.

force_identifiability

Logical indicating whether or not to normalize theta_out such that it sums to one within each incoming block and theta_in such that it sums to one within each outgoing block. Defaults to TRUE.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Value

A directed_dcsbm S3 object, a subclass of the directed_factor_model() with the following additional fields:

  • theta_out: A numeric vector of outgoing degree-heterogeneity parameters.

  • theta_in: A numeric vector of incoming degree-heterogeneity parameters.

  • z_out: The outgoing community memberships of each node, as a factor(). The factor will have k_out levels, where k_out is the number of outgoing communities in the stochastic blockmodel. There will not always necessarily be observed nodes in each community.

  • z_in: The incoming community memberships of each node, as a factor(). The factor will have k_in levels, where k_in is the number of incoming communities in the stochastic blockmodel. There will not always necessarily be observed nodes in each community.

  • pi_out: Sampling probabilities for each outgoing community.

  • pi_in: Sampling probabilities for each incoming community.

  • sorted: Logical indicating where nodes are arranged by block (and additionally by degree heterogeneity parameter) within each block.

  • shared_blocks: Logical indicating whether outgoing and incoming block memberships are shared, in which case z_out and z_in are identical.

  • shared_theta: Logical indicating whether outgoing and incoming degree-heterogeneity parameters are shared, in which case theta_out and theta_in are identical.

Generative Model

There are two levels of randomness in a directed degree-corrected stochastic blockmodel. First, we randomly chose a incoming block membership and an outgoing block membership for each node in the blockmodel. This is handled by directed_dcsbm(). Then, given these block memberships, we randomly sample edges between nodes. This second operation is handled by sample_edgelist(), sample_sparse(), sample_igraph() and sample_tidygraph(), depending on your desired graph representation.

Block memberships

Let xx represent the incoming block membership of a node and yy represent the outgoing block membership of a node. To generate xx we sample from a categorical distribution with parameter πout\pi_{out}. To generate yy we sample from a categorical distribution with parameter πin\pi_{in}. Block memberships are independent across nodes. Incoming and outgoing block memberships of the same node are also independent.

These categorical draws are used when pi_out (pi_in) is specified. Otherwise, the outgoing (incoming) block memberships are a uniformly random assignment of nodes to blocks with fixed block sizes: either exactly the sizes given in block_sizes_out (block_sizes_in), or, by default, block sizes that are as balanced as possible (every block gets floor(n / k_out) nodes, and the remainder is spread over the first blocks, one node each), as in dcsbm(). Fixed block sizes are useful, for instance, to construct blockmodels with exactly repeated singular values.

Degree heterogeneity

In addition to block membership, the DCSBM also nodes to have different propensities for incoming and outgoing edge formation. We represent the propensity to form incoming edges for a given node by a positive number θout\theta_{out}. We represent the propensity to form outgoing edges for a given node by a positive number θin\theta_{in}. Typically the θout\theta_{out} (and θin\theta_{in}) across all nodes are constrained to sum to one for identifiability purposes, but this doesn't really matter during sampling.

Edge formulation

Once we know the block memberships xx and yy and the degree heterogeneity parameters θin\theta_{in} and θout\theta_{out}, we need one more ingredient, which is the baseline intensity of connections between nodes in block i and block j. Then each edge forms independently according to a Poisson distribution with parameters

λ=θin⋅Bx,y⋅θout.\lambda = \theta_{in} \cdot B_{x, y} \cdot \theta_{out}.

Co-factor models versus shared blocks and degree heterogeneity

By default (shared_blocks = FALSE and shared_theta = FALSE), directed_dcsbm() is a co-factor model: every node has an outgoing block zoutz_{out} and degree parameter θout\theta_{out} that govern the edges it sends (the rows of AA), and a separate incoming block zinz_{in} and degree parameter θin\theta_{in} that govern the edges it receives (the columns of AA). These are drawn independently, so the communities a node sends edges from and receives edges into are unrelated, and the two sets of communities can even have different numbers of blocks. This is the model targeted by co-clustering methods that estimate separate sending and receiving communities.

In the co-factor model, sort_nodes = TRUE (the default) sorts the rows and the columns of AA independently, so row ii and column ii are generally not the same node. Consequently the diagonal of AA, and so the self-loops controlled by allow_self_loops, is not meaningful as "node ii to itself": entry AiiA_{ii} connects the ii-th sender to the ii-th receiver in their respective orderings. If you need rows and columns to index the same nodes (for example, to interpret self-loops or to read the graph as a directed graph on a single set of nodes), use shared_blocks = TRUE or sort_nodes = FALSE.

Often it is more natural to think of each node as belonging to a single community, which shapes both the edges it sends and the edges it receives. Setting shared_blocks = TRUE draws one membership vector zz with zout=zin=zz_{out} = z_{in} = z, so that E[Aij]=θout,iBzi,zjθin,jE[A_{ij}] = \theta_{out, i} B_{z_i, z_j} \theta_{in, j}, where an asymmetric B encodes directed relationships between the communities. With shared blocks you can additionally set shared_theta = TRUE, which uses one degree-heterogeneity vector θ\theta for both θout\theta_{out} and θin\theta_{in}, so nodes that send many edges also tend to receive many edges. (shared_theta = TRUE requires shared_blocks = TRUE.) With shared blocks, sort_nodes = TRUE permutes rows and columns together, so that row i and column i of AA always refer to the same node.

See Also

Other stochastic block models: dcsbm(), directed_planted_partition(), mmsbm(), overlapping_sbm(), planted_partition(), sbm()

Other directed graphs: directed_erdos_renyi(), directed_planted_partition()

Examples

set.seed(27)

B <- matrix(0.2, nrow = 5, ncol = 8)
diag(B) <- 0.9

ddcsbm <- directed_dcsbm(
  n = 100,
  B = B,
  k_out = 5,
  k_in = 8,
  expected_density = 0.01
)

ddcsbm

population_svd <- svds(ddcsbm)

# specify the exact number of nodes in each outgoing and incoming block,
# rather than sampling block memberships

ddcsbm_explicit_block_sizes <- directed_dcsbm(
  theta_out = rexp(100, 1 / 3) + 1,
  theta_in = rexp(100, 1 / 3) + 1,
  B = B,
  block_sizes_out = c(10, 15, 20, 25, 30),
  block_sizes_in = c(5, 5, 10, 10, 15, 15, 20, 20),
  expected_density = 0.01
)

# respects block sizes
table(ddcsbm_explicit_block_sizes$z_out)
table(ddcsbm_explicit_block_sizes$z_in)

# each node belongs to the same outgoing and incoming community, and has
# the same propensity to send and receive edges

B_square <- matrix(0.1, nrow = 4, ncol = 4)
diag(B_square) <- 0.8
B_square[1, 2] <- 0.5 # block 1 sends many edges to block 2

shared_ddcsbm <- directed_dcsbm(
  theta_out = rexp(100, 1 / 3) + 1,
  B = B_square,
  shared_blocks = TRUE,
  shared_theta = TRUE,
  expected_density = 0.05
)

shared_ddcsbm

identical(shared_ddcsbm$z_out, shared_ddcsbm$z_in)

Create an directed erdos renyi object

Description

Create an directed erdos renyi object

Usage

directed_erdos_renyi(
  n,
  ...,
  p = NULL,
  poisson_edges = TRUE,
  allow_self_loops = TRUE
)

Arguments

n

Number of nodes in graph.

...

Arguments passed on to directed_factor_model

expected_in_degree

If specified, the desired expected in degree of the graph. Specifying expected_in_degree simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

expected_out_degree

If specified, the desired expected out degree of the graph. Specifying expected_out_degree simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

p

Probability of an edge between any two nodes. You must specify either p, expected_in_degree, expected_out_degree or expected_density.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Value

A directed_factor_model S3 class based on a list with the following elements:

  • X: The incoming latent positions as a Matrix::Matrix() object.

  • S: The mixing matrix as a Matrix::Matrix() object.

  • Y: The outgoing latent positions as a Matrix::Matrix() object.

  • n: The number of nodes with incoming edges in the network.

  • k1: The dimension of the latent node position vectors encoding incoming latent communities (i.e. in X).

  • d: The number of nodes with outgoing edges in the network. Does not need to match n – rectangular adjacency matrices are supported.

  • k2: The dimension of the latent node position vectors encoding outgoing latent communities (i.e. in Y).

  • poisson_edges: Whether or not the graph is taken to be have Poisson or Bernoulli edges, as indicated by a logical vector of length 1.

  • allow_self_loops: Whether or not self loops are allowed.

See Also

Other erdos renyi: erdos_renyi()

Other directed graphs: directed_dcsbm(), directed_planted_partition()

Examples

set.seed(87)

er <- directed_erdos_renyi(n = 10, p = 0.1)
er

big_er <- directed_erdos_renyi(n = 1000, expected_in_degree = 5)
big_er

A <- sample_sparse(er)
A

Create a directed factor model graph

Description

A directed factor model graph is a directed generalized Poisson random dot product graph. The edges in this graph are assumpted to be independent and Poisson distributed. The graph is parameterized by its expected adjacency matrix, with is ⁠E[A] = X S Y'⁠. We do not recommend that causal users use this function, see instead directed_dcsbm() and related functions, which will formulate common variants of the stochastic blockmodels as undirected factor models with lots of helpful input validation.

Usage

directed_factor_model(
  X,
  S,
  Y,
  ...,
  expected_in_degree = NULL,
  expected_out_degree = NULL,
  expected_density = NULL,
  poisson_edges = TRUE,
  allow_self_loops = TRUE
)

Arguments

X

A matrix() or Matrix::Matrix() representing real-valued latent node positions encoding community structure of incoming edges. Entries must be positive.

S

A matrix() or Matrix::Matrix() mixing matrix. Entries must be positive.

Y

A matrix() or Matrix::Matrix() representing real-valued latent node positions encoding community structure of outgoing edges. Entries must be positive.

...

Ignored. For internal developer use only.

expected_in_degree

If specified, the desired expected in degree of the graph. Specifying expected_in_degree simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

expected_out_degree

If specified, the desired expected out degree of the graph. Specifying expected_out_degree simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

expected_density

If specified, the desired expected density of the graph. Specifying expected_density simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Value

A directed_factor_model S3 class based on a list with the following elements:

  • X: The incoming latent positions as a Matrix::Matrix() object.

  • S: The mixing matrix as a Matrix::Matrix() object.

  • Y: The outgoing latent positions as a Matrix::Matrix() object.

  • n: The number of nodes with incoming edges in the network.

  • k1: The dimension of the latent node position vectors encoding incoming latent communities (i.e. in X).

  • d: The number of nodes with outgoing edges in the network. Does not need to match n – rectangular adjacency matrices are supported.

  • k2: The dimension of the latent node position vectors encoding outgoing latent communities (i.e. in Y).

  • poisson_edges: Whether or not the graph is taken to be have Poisson or Bernoulli edges, as indicated by a logical vector of length 1.

  • allow_self_loops: Whether or not self loops are allowed.

Examples

n <- 1000

k1 <- 5
k2 <- 3

d <- 500

X <- matrix(rpois(n = n * k1, 1), nrow = n)
S <- matrix(runif(n = k1 * k2, 0, .1), nrow = k1, ncol = k2)
Y <- matrix(rexp(n = k2 * d, 1), nrow = d)

fm <- directed_factor_model(X, S, Y)
fm

fm2 <- directed_factor_model(X, S, Y, expected_in_degree = 50)
fm2

Create a directed planted partition object

Description

To specify a directed planted partition model, you must specify the number of nodes (via n), the number of blocks (via k), the edge probabilities (either via within_block and between_block, or via a and b), and the block sizes (optional, via pi or block_sizes). By default, the communities a node sends edges from and receives edges into are sampled independently; set shared_blocks = TRUE to give each node a single community. We strongly recommend setting the expected_out_degree, expected_in_degree, or expected_density argument to avoid large memory allocations associated with sampling large, dense graphs.

Usage

directed_planted_partition(
  n,
  k,
  ...,
  within_block = NULL,
  between_block = NULL,
  a = NULL,
  b = NULL,
  block_sizes = NULL,
  pi = NULL,
  shared_blocks = FALSE,
  sort_nodes = TRUE,
  poisson_edges = TRUE,
  allow_self_loops = TRUE
)

Arguments

n

The number of nodes in the network. Must be a positive integer. This argument is required.

k

Number of planted partitions, as a positive integer. There are k outgoing blocks and k incoming blocks. Must be less than or equal to n. This argument is required.

...

Arguments passed on to directed_factor_model

expected_in_degree

If specified, the desired expected in degree of the graph. Specifying expected_in_degree simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

expected_out_degree

If specified, the desired expected out degree of the graph. Specifying expected_out_degree simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

expected_density

If specified, the desired expected density of the graph. Specifying expected_density simply rescales S to achieve this. Defaults to NULL. Specify only one of expected_in_degree, expected_out_degree, and expected_density.

within_block

Probability of a directed edge from a node in outgoing block i to a node in incoming block i, i.e. the diagonal of the mixing matrix B. Must be between zero and one. Must specify either within_block and between_block, or a and b to determine edge probabilities.

between_block

Probability of a directed edge from a node in outgoing block i to a node in incoming block j, for i != j, i.e. the off-diagonal of the mixing matrix B. Must be between zero and one. Must specify either within_block and between_block, or a and b to determine edge probabilities.

a

Number such that a / n is the probability of edges within a block. Useful for sparse graphs. Must specify either within_block and between_block, or a and b to determine edge probabilities.

b

Number such that b / n is the probability of edges between blocks. Useful for sparse graphs. Must specify either within_block and between_block, or a and b to determine edge probabilities.

block_sizes

(block sizes) Number of nodes in each block, as a vector of non-negative integers. Must have length k and must sum to n. Used for both the outgoing and the incoming blocks: exactly block_sizes[j] nodes are assigned to outgoing block j, and exactly block_sizes[j] nodes are assigned to incoming block j. Defaults to NULL, in which case blocks are made to be as balanced as possible (unless pi is specified). You can specify either pi or block_sizes, but not both.

pi

(block sizes) Relative block probabilities, used for both the outgoing and the incoming blocks. Must be positive, but do not need to sum to one, as they will be normalized internally. Must have length k. When specified, block memberships are sampled independently for each node with these probabilities. Defaults to NULL, in which case the block_sizes argument (or its balanced default) takes precedence. You can specify either pi or block_sizes, but not both.

shared_blocks

Logical indicating whether each node should belong to the same outgoing and incoming block. Defaults to FALSE, in which case outgoing and incoming block memberships are sampled independently. When TRUE, a single block membership vector is sampled and used for both, so that z_out and z_in are identical. See directed_dcsbm() for details.

sort_nodes

Logical indicating whether or not to sort the nodes so that they are grouped by block. Useful for plotting. Defaults to TRUE. When TRUE, blocks are relabeled in increasing order of pi (or block_sizes), and the rows of the expected adjacency matrix are grouped by outgoing block while the columns are grouped by incoming block. When shared_blocks = TRUE, rows and columns are permuted together, so that row i and column i refer to the same node. When shared_blocks = FALSE (the default), rows and columns are sorted independently, so row i and column i are generally not the same node: the diagonal of A (self-loops) is then not meaningful as "node i to itself", and z_out[i] and z_in[i] describe different nodes. Use shared_blocks = TRUE or sort_nodes = FALSE if you need rows and columns to index the same nodes. See directed_dcsbm() for details.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Details

A directed planted partition model is a directed stochastic blockmodel with k outgoing blocks and k incoming blocks, in which the diagonal and the off-diagonal of the mixing matrix B are both constant. This means that the probability of an edge from node ii to node jj depends only on whether the outgoing block of ii matches the incoming block of jj, but the particular blocks themselves don't have any impact apart from this. It is a special case of directed_dcsbm() where all degree-heterogeneity parameters are equal to one.

Value

A directed_planted_partition S3 object, which is a subclass of the directed_dcsbm() object (with theta_out and theta_in identically one), with additional fields:

  • within_block: The probability of edge formation within a block, as specified (or as computed from a / n), before any rescaling by expected_out_degree, expected_in_degree or expected_density.

  • between_block: The probability of edge formation between two distinct blocks, as specified (or as computed from b / n), before any rescaling by expected_out_degree, expected_in_degree or expected_density.

Generative Model

Block memberships

Each node ii has an outgoing block membership zout,iz_{out, i}, which governs the edges it sends, and an incoming block membership zin,iz_{in, i}, which governs the edges it receives. Both take values in ⁠1, ..., k⁠. By default, the outgoing memberships are a uniformly random assignment of nodes to blocks with block sizes that are as balanced as possible (as in planted_partition()), or with exactly block_sizes[j] nodes in block j when block_sizes is specified. The incoming memberships are assigned in the same way, independently of the outgoing memberships. When pi is specified, memberships are instead sampled independently across nodes from a categorical distribution with parameter π\pi (again, independently for outgoing and incoming blocks).

When shared_blocks = TRUE, a single membership vector is sampled and zout,i=zin,iz_{out, i} = z_{in, i} for every node.

Mixing matrix

The mixing matrix is the k by k matrix with within_block (or a / n) on the diagonal and between_block (or b / n) everywhere else, i.e.

B=pbetween11T+(pwithin−pbetween)Ik,B = p_{between} \mathbf{1} \mathbf{1}^T + (p_{within} - p_{between}) I_k,

where pwithinp_{within} is within_block and pbetweenp_{between} is between_block. If you specify expected_out_degree, expected_in_degree or expected_density, B is rescaled by a constant, so only the ratio of within_block to between_block matters.

Edge formation

Given the block memberships, each directed edge AijA_{ij} from node ii to node jj is sampled independently (for every ordered pair (i,j)(i, j), so the adjacency matrix is not symmetric) with expectation

E[Aij]=Bzout,i,zin,j.E[A_{ij}] = B_{z_{out, i}, z_{in, j}}.

Edges are Poisson distributed when poisson_edges = TRUE (yielding a multigraph) and Bernoulli distributed with the same probabilities when poisson_edges = FALSE. Self-loops are allowed or not according to allow_self_loops. Note that with the default shared_blocks = FALSE and sort_nodes = TRUE, rows and columns of AA are sorted independently, so the diagonal entry AiiA_{ii} pairs the ii-th sender with the ii-th receiver rather than node ii with itself (see sort_nodes).

Interpretation

When within_block > between_block, nodes in outgoing block ss preferentially send edges to nodes in incoming block ss. With the default independent memberships, this is a co-clustering structure: the communities that describe who a node sends edges to are unrelated to the communities that describe who sends edges to it. With shared_blocks = TRUE, each node has one community, and edges in both directions are more common within communities than between them.

See Also

Other stochastic block models: dcsbm(), directed_dcsbm(), mmsbm(), overlapping_sbm(), planted_partition(), sbm()

Other directed graphs: directed_dcsbm(), directed_erdos_renyi()

Examples

set.seed(27)

lazy_dpp <- directed_planted_partition(
  n = 100,
  k = 5,
  expected_density = 0.01,
  within_block = 0.1,
  between_block = 0.01
)

lazy_dpp

# sparse parameterization, with Bernoulli edges

sparse_dpp <- directed_planted_partition(
  n = 1000,
  k = 3,
  a = 10,
  b = 4,
  poisson_edges = FALSE
)

A <- sample_sparse(sparse_dpp)

# only zeroes and ones!
range(A)

# each node belongs to a single community, which determines both
# the edges it sends and the edges it receives

shared_dpp <- directed_planted_partition(
  n = 100,
  k = 4,
  within_block = 0.3,
  between_block = 0.02,
  shared_blocks = TRUE
)

identical(shared_dpp$z_out, shared_dpp$z_in)

# exact block sizes

sized_dpp <- directed_planted_partition(
  n = 90,
  k = 3,
  within_block = 0.3,
  between_block = 0.05,
  block_sizes = c(20, 30, 40)
)

table(sized_dpp$z_out)
table(sized_dpp$z_in)

population_svd <- svds(sized_dpp)
population_svd$d

Compute the eigendecomposition of the expected adjacency matrix of an undirected factor model

Description

Compute the eigendecomposition of the expected adjacency matrix of an undirected factor model

Usage

## S3 method for class 'undirected_factor_model'
eigs_sym(A, k = A$k, which = "LM", sigma = NULL, opts = list(), ...)

Arguments

A

An undirected_factor_model().

k

Desired rank of decomposition.

which

Selection criterion. See Details below.

sigma

Shift parameter. See section Shift-And-Invert Mode.

opts

Control parameters related to the computing algorithm. See Details below.

...

Unused, included only for consistency with generic signature.

Details

The which argument is a character string that specifies the type of eigenvalues to be computed. Possible values are:

"LM" The kk eigenvalues with largest magnitude. Here the magnitude means the Euclidean norm of complex numbers.
"SM" The kk eigenvalues with smallest magnitude.
"LR" The kk eigenvalues with largest real part.
"SR" The kk eigenvalues with smallest real part.
"LI" The kk eigenvalues with largest imaginary part.
"SI" The kk eigenvalues with smallest imaginary part.
"LA" The kk largest (algebraic) eigenvalues, considering any negative sign.
"SA" The kk smallest (algebraic) eigenvalues, considering any negative sign.
"BE" Compute kk eigenvalues, half from each end of the spectrum. When kk is odd, compute more from the high and then from the low end.

eigs() with matrix types "matrix", "dgeMatrix", "dgCMatrix" and "dgRMatrix" can use "LM", "SM", "LR", "SR", "LI" and "SI".

eigs_sym() with all supported matrix types, and eigs() with symmetric matrix types ("dsyMatrix", "dsCMatrix", and "dsRMatrix") can use "LM", "SM", "LA", "SA" and "BE".

The opts argument is a list that can supply any of the following parameters:

ncv

Number of Lanzcos basis vectors to use. More vectors will result in faster convergence, but with greater memory use. For general matrix, ncv must satisfy k+2≤ncv≤nk+2\le ncv \le n, and for symmetric matrix, the constraint is k<ncv≤nk < ncv \le n. Default is min(n, max(2*k+1, 20)).

tol

Precision parameter. Default is 1e-10.

maxitr

Maximum number of iterations. Default is 1000.

retvec

Whether to compute eigenvectors. If FALSE, only calculate and return eigenvalues.

initvec

Initial vector of length nn supplied to the Arnoldi/Lanczos iteration. It may speed up the convergence if initvec is close to an eigenvector of AA.


Create an undirected erdos renyi object

Description

Create an undirected erdos renyi object

Usage

erdos_renyi(n, ..., p = NULL, poisson_edges = TRUE, allow_self_loops = TRUE)

Arguments

n

Number of nodes in graph.

...

Arguments passed on to undirected_factor_model

expected_degree

If specified, the desired expected degree of the graph. Specifying expected_degree simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

p

Probability of an edge between any two nodes. You must specify either p, expected_degree or expected_density.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Value

An undirected_factor_model S3 class based on a list with the following elements:

  • X: The latent positions as a Matrix::Matrix() object.

  • S: The mixing matrix as a Matrix::Matrix() object.

  • n: The number of nodes in the network.

  • k: The rank of expectation matrix. Equivalently, the dimension of the latent node position vectors.

See Also

Other erdos renyi: directed_erdos_renyi()

Other undirected graphs: chung_lu(), dcsbm(), mmsbm(), overlapping_sbm(), planted_partition(), sbm()

Examples

set.seed(87)

er <- erdos_renyi(n = 10, p = 0.1)
er


er <- erdos_renyi(n = 10, expected_density = 0.1)
er

big_er <- erdos_renyi(n = 1000, expected_degree = 5)
big_er

A <- sample_sparse(er)
A

Calculate the expected adjacency matrix

Description

Calculate the expected adjacency matrix

Usage

expectation(model, ...)

## S3 method for class 'undirected_factor_model'
expectation(model, ...)

## S3 method for class 'directed_factor_model'
expectation(model, ...)

Arguments

model

A directed_factor_model() or an undirected_factor_model() object.

...

Unused.

Value

The expected value of the adjacency matrix, conditional on the latent factors X and Y (if the model is directed).


Calculate the expected edges in Poisson RDPG graph

Description

These calculations are conditional on the latent factors X and Y.

Usage

expected_edges(factor_model, ...)

expected_degrees(factor_model, ...)

expected_degree(factor_model, ...)

expected_in_degree(factor_model, ...)

expected_out_degree(factor_model, ...)

expected_density(factor_model, ...)

Arguments

factor_model

A directed_factor_model() or undirected_factor_model().

...

Ignored. Do not use.

Details

Write P=E[A∣X,S]=XSXTP = \mathbb{E}[A \mid X, S] = X S X^T for an undirected factor model, and P=XSYTP = X S Y^T for a directed one.

For undirected graphs, every edge between distinct nodes i and j appears twice in the symmetric adjacency matrix A, as both A[i, j] and A[j, i], while a self-loop appears once, as A[i, i]. Accordingly:

  • expected_edges() is the expected number of edges, counting each undirected edge once: (∑ijPij+tr(P))/2(\sum_{ij} P_{ij} + \mathrm{tr}(P)) / 2. This includes expected self-loops, even when allow_self_loops = FALSE.

  • expected_degree() is the expected mean degree, i.e. the average row sum of PP: ∑ijPij/n\sum_{ij} P_{ij} / n. expected_degrees() gives the expected degree of each node.

  • expected_density() is the expected number of edges between distinct nodes, divided by the number of pairs of distinct nodes: (∑ijPij−tr(P))/(n(n−1))(\sum_{ij} P_{ij} - \mathrm{tr}(P)) / (n (n - 1)). This is the average edge probability (or rate) between distinct nodes, and does not depend on self-loops.

For directed graphs, expected_edges() is ∑ijPij\sum_{ij} P_{ij}, expected_out_degree() and expected_in_degree() divide this by the number of rows and columns of A, and expected_density() divides it by the number of entries of A.

These are expectations under Poisson edges. For Bernoulli graphs (poisson_edges = FALSE), they are computed from the Poisson parameterization of S, and overestimate edge counts slightly when edge probabilities are large.

Note that the runtime of the fastRG algorithm is proportional to the expected number of edges in the graph. See Rohe et al. (2018) for details.

Value

Expected edge counts, degrees, or graph densities.

References

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

Examples

##### an undirected blockmodel example

n <- 100
pop <- n / 2
a <- .1
b <- .05

B <- matrix(c(a, b, b, a), nrow = 2)

b_model <- sbm(n = n, B = B, poisson_edges = FALSE)

b_model

A <- sample_sparse(b_model)

# compare
mean(rowSums(A))

pop * a + pop * b # analytical average degree

##### more generic examples

n <- 1000
k <- 5

X <- matrix(rpois(n = n * k, 1), nrow = n)
S <- matrix(runif(n = k * k, 0, .1), nrow = k)

ufm <- undirected_factor_model(X, S)

expected_edges(ufm)
expected_degree(ufm)
eigs_sym(ufm)

n <- 1000
d <- 100

k1 <- 5
k2 <- 3

X <- matrix(rpois(n = n * k1, 1), nrow = n)
Y <- matrix(rpois(n = d * k2, 1), nrow = d)
S <- matrix(runif(n = k1 * k2, 0, .1), nrow = k1)

dfm <- directed_factor_model(X = X, S = S, Y = Y)

expected_edges(dfm)
expected_in_degree(dfm)
expected_out_degree(dfm)

svds(dfm)

Create an undirected degree-corrected mixed membership stochastic blockmodel object

Description

To specify a degree-corrected mixed membership stochastic blockmodel, you must specify the degree-heterogeneity parameters (via n or theta), the mixing matrix (via k or B), and the relative block propensities (optional, via alpha). We provide defaults for most of these options to enable rapid exploration, or you can invest the effort for more control over the model parameters. We strongly recommend setting the expected_degree or expected_density argument to avoid large memory allocations associated with sampling large, dense graphs.

Usage

mmsbm(
  n = NULL,
  theta = NULL,
  k = NULL,
  B = NULL,
  ...,
  alpha = rep(1, k),
  sort_nodes = TRUE,
  force_pure = TRUE,
  poisson_edges = TRUE,
  allow_self_loops = TRUE
)

Arguments

n

(degree heterogeneity) The number of nodes in the blockmodel. Use when you don't want to specify the degree-heterogeneity parameters theta by hand. When n is specified, theta is randomly generated from a LogNormal(2, 1) distribution. This is subject to change, and may not be reproducible. n defaults to NULL. You must specify either n or theta, but not both.

theta

(degree heterogeneity) A numeric vector explicitly specifying the degree heterogeneity parameters. This implicitly determines the number of nodes in the resulting graph, i.e. it will have length(theta) nodes. Must be positive. Setting to a vector of ones recovers a stochastic blockmodel without degree correction. Defaults to NULL. You must specify either n or theta, but not both.

k

(mixing matrix) The number of blocks in the blockmodel. Use when you don't want to specify the mixing-matrix by hand. When k is specified, the elements of B are drawn randomly from a Uniform(0, 1) distribution. This is subject to change, and may not be reproducible. k defaults to NULL. You must specify either k or B, but not both.

B

(mixing matrix) A k by k matrix of block connection probabilities. The probability that a node in block i connects to a node in community j is Poisson(B[i, j]). Must be a square matrix. matrix and Matrix objects are both acceptable. If B is not symmetric, it will be symmetrized via the update B := B + t(B) / 2. Defaults to NULL. You must specify either k or B, but not both.

...

Arguments passed on to undirected_factor_model

expected_degree

If specified, the desired expected degree of the graph. Specifying expected_degree simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

expected_density

If specified, the desired expected density of the graph, that is, the expected number of edges between distinct nodes divided by choose(n, 2). See expected_density(). Specifying expected_density simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

alpha

(relative block propensities) Relative block propensities, which are parameters of a Dirichlet distribution. All elments of alpha must thus be positive. Must match the dimensions of B or k. Defaults to rep(1, k), or balanced membership across blocks.

sort_nodes

Logical indicating whether or not to sort the nodes so that they are grouped by block and by theta. Useful for plotting. Defaults to TRUE. When TRUE, nodes are first sorted by block membership, and then by degree-correction parameters within each block. Additionally, pi is sorted in increasing order, and the columns of the B matrix are permuted to match the new order of pi.

force_pure

Logical indicating whether or not to force presence of "pure nodes" (nodes that belong only to a single block) for the sake of identifiability. To include pure nodes, block membership sampling first proceeds as per usual. Then, after it is complete, k distinct nodes are chosen uniformly at random, and the memberships of the jth chosen node are overwritten so that it belongs to block j and to no other block. Requires n >= k. Defaults to TRUE.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Value

An undirected_mmsbm S3 object, a subclass of the undirected_factor_model() with the following additional fields:

  • theta: A numeric vector of degree-heterogeneity parameters.

  • Z: The community memberships of each node, a matrix() with k columns, whose row sums all equal one.

  • alpha: Community membership proportion propensities.

  • sorted: Logical indicating where nodes are arranged by block (and additionally by degree heterogeneity parameter) within each block.

Generative Model

There are two levels of randomness in a degree-corrected stochastic blockmodel. First, we randomly choose how much each node belongs to each block in the blockmodel. Each node is one unit of block membership to distribute. This is handled by mmsbm(). Then, given these block memberships, we randomly sample edges between nodes. This second operation is handled by sample_edgelist(), sample_sparse(), sample_igraph() and sample_tidygraph(), depending depending on your desired graph representation.

Block memberships

Let ZiZ_i by a vector on the k dimensional simplex representing the block memberships of node ii. To generate ziz_i we sample from a Dirichlet distribution with parameter vector α\alpha. Block memberships for each node are independent.

Degree heterogeneity

In addition to block membership, the MMSBM also allows nodes to have different propensities for edge formation. We represent this propensity for node ii by a positive number θi\theta_i.

Edge formulation

Once we know the block membership vector zi,zjz_i, z_j and the degree heterogeneity parameters θ\theta, we need one more ingredient, which is the baseline intensity of connections between nodes in block i and block j. This is given by a k×kk \times k matrix BB. Then each edge Ai,jA_{i,j} is Poisson distributed with parameter

λi,j=θi⋅ziTBzj⋅θj.\lambda_{i, j} = \theta_i \cdot z_i^T B z_j \cdot \theta_j.

See Also

Other stochastic block models: dcsbm(), directed_dcsbm(), directed_planted_partition(), overlapping_sbm(), planted_partition(), sbm()

Other undirected graphs: chung_lu(), dcsbm(), erdos_renyi(), overlapping_sbm(), planted_partition(), sbm()

Examples

set.seed(27)

lazy_mmsbm <- mmsbm(n = 100, k = 5, expected_density = 0.01)
lazy_mmsbm

# sometimes you gotta let the world burn and
# sample a wildly dense graph

dense_lazy_mmsbm <- mmsbm(n = 500, k = 3, expected_density = 0.8)
dense_lazy_mmsbm

# explicitly setting the degree heterogeneity parameter,
# mixing matrix, and relative community sizes rather
# than using randomly generated defaults

k <- 5
n <- 100
B <- matrix(stats::runif(k * k), nrow = k, ncol = k)

theta <- round(stats::rlnorm(n, 2))

alpha <- c(1, 2, 4, 1, 1)

custom_mmsbm <- mmsbm(
  theta = theta,
  B = B,
  alpha = alpha,
  expected_degree = 50
)

custom_mmsbm

edgelist <- sample_edgelist(custom_mmsbm)
edgelist

# efficient eigendecompostion that leverages low-rank structure in
# E(A) so that you don't have to form E(A) to find eigenvectors,
# as E(A) is typically dense. computation is
# handled via RSpectra

population_eigs <- eigs_sym(custom_mmsbm)
svds(custom_mmsbm)$d

Create an undirected overlapping stochastic blockmodel object

Description

To specify an overlapping stochastic blockmodel, you must specify the number of nodes (via n), the mixing matrix (via k or B), and the block membership probabilities (optional, via pi). In an overlapping stochastic blockmodel, each node can belong to any number of blocks: zero, one, or several. We provide defaults for most of these options to enable rapid exploration, or you can invest the effort for more control over the model parameters. We strongly recommend setting the expected_degree or expected_density argument to avoid large memory allocations associated with sampling large, dense graphs.

Usage

overlapping_sbm(
  n,
  k = NULL,
  B = NULL,
  ...,
  pi = rep(1/k, k),
  sort_nodes = TRUE,
  force_pure = TRUE,
  poisson_edges = TRUE,
  allow_self_loops = TRUE
)

Arguments

n

The number of nodes in the overlapping SBM. Must be at least k when force_pure = TRUE.

k

(mixing matrix) The number of blocks in the blockmodel. Use when you don't want to specify the mixing-matrix by hand. When k is specified, B is set to a diagonally dominant matrix with value 0.8 along the diagonal and 0.1 / (k - 1) on the off-diagonal. This is subject to change, and may not be reproducible. k defaults to NULL. You must specify either k or B, but not both.

B

(mixing matrix) A k by k matrix of baseline connection intensities between blocks. Before any rescaling via expected_degree or expected_density, B[a, b] is the expected number of edges contributed to the pair of nodes (i,j)(i, j) by node ii's membership in block a and node jj's membership in block b. These contributions add up over all pairs of blocks that i and j belong to (see "Edge formulation" below). All elements of B must be contained in [0,1][0, 1]. matrix and Matrix objects are both acceptable. If B is not symmetric, it will be symmetrized via the update B := (B + t(B)) / 2, and the symmetrized B must be invertible. Defaults to NULL. You must specify either k or B, but not both.

...

Arguments passed on to undirected_factor_model

expected_degree

If specified, the desired expected degree of the graph. Specifying expected_degree simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

expected_density

If specified, the desired expected density of the graph, that is, the expected number of edges between distinct nodes divided by choose(n, 2). See expected_density(). Specifying expected_density simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

pi

(block membership probabilities) A vector of length k whose jth element is the probability that a node belongs to block j. All elements must be contained in [0,1][0, 1]. Each node joins each block independently, so pi is not normalized and does not need to sum to one: sum(pi) is the expected number of blocks a node joins before nodes in no block are reassigned (ignoring force_pure). A node that joins no block is instead assigned to exactly one block, chosen with probability proportional to pi, so every node belongs to at least one block and at least one element of pi must be positive. Defaults to rep(1 / k, k), in which case a fraction of roughly (1−1/k)k≈e−1(1 - 1/k)^k \approx e^{-1} of nodes initially join no block and are reassigned to a single block chosen uniformly at random. Regardless of sort_nodes, pi is sorted in increasing order, and the rows and columns of B are permuted to match the new order of pi.

sort_nodes

Logical indicating whether or not to sort the nodes so that they are grouped by block. Useful for plotting. Defaults to TRUE. When TRUE, the rows of Z are sorted in decreasing lexicographic order, so that members of the first block come first, and within the members of the first block, members of the second block come first, and so on.

force_pure

Logical indicating whether or not to force presence of "pure nodes" (nodes that belong only to a single block) for the sake of identifiability. To include pure nodes, block membership sampling first proceeds as per usual. Then, after it is complete, k distinct nodes are chosen uniformly at random, and the memberships of the jth chosen node are overwritten so that it belongs to block j and to no other block. Requires n >= k. Defaults to TRUE.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired Bernoulli edge probability, and back-transform S to a Poisson parameterization before sampling (see "Edge formulation" below), so all elements of S (after symmetrizing and any rescaling) must be at most 1.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Value

An undirected_overlapping_sbm S3 object, a subclass of the undirected_factor_model() with the following additional fields:

  • Z: The block memberships of each node, as an n by k binary Matrix::Matrix(). Z[i, j] is one if node i belongs to block j and zero otherwise. Rows can contain any number of ones, including none. Columns are ordered to match pi and B. For this model, Z is identical to the latent positions X.

  • pi: Block membership probabilities for each block, sorted in increasing order.

  • B: The mixing matrix, as specified by the user (or the default when only k is given), with rows and columns permuted to match the order of pi. Note that B is not symmetrized or rescaled: the symmetrized and rescaled matrix used for sampling is S.

  • sorted: Logical indicating whether nodes are arranged by block membership (see sort_nodes).

Generative Model

overlapping_sbm() implements the stochastic blockmodel with overlaps (SBMO) of Kaufmann, Bonald and Lelarge (2016), with Poisson rather than Bernoulli edges. There are two levels of randomness in an overlapping stochastic blockmodel. First, for each node, we independently determine if that node is a member of each block. This is handled by overlapping_sbm(). Then, given these block memberships, we randomly sample edges between nodes. This second operation is handled by sample_edgelist(), sample_sparse(), sample_igraph() and sample_tidygraph(), depending on your desired graph representation.

Block memberships

Let Z∈{0,1}n×kZ \in \{0, 1\}^{n \times k} be the binary block membership matrix, and let ziz_i be its iith row, so that Zia=1Z_{ia} = 1 when node ii belongs to block aa. Each entry is sampled independently as

Zia∼Bernoulli(πa),i=1,…,n,a=1,…,k.Z_{ia} \sim \text{Bernoulli}(\pi_a), \qquad i = 1, \dots, n, \quad a = 1, \dots, k.

Unlike in dcsbm(), where each node belongs to exactly one block, or in mmsbm(), where each node splits one unit of membership among blocks, here a node can be a full member of several blocks at once.

Every node must belong to at least one block. After the Bernoulli draws above, any node with Zia=0Z_{ia} = 0 for every block aa is assigned to exactly one block, chosen at random with probability πa/∑bπb\pi_a / \sum_b \pi_b. As a result, the entries of ZZ are not exactly independent, and nodes that belong to a single block are somewhat more common than independent Bernoulli draws alone would give. When force_pure = TRUE, k randomly chosen nodes are then made pure members of one block each (see "Identifiability").

Degree heterogeneity

The overlapping SBM has no degree heterogeneity parameters (equivalently, θi=1\theta_i = 1 for every node). Nodes that belong to more blocks tend to have higher expected degree, but all members of the same set of blocks have the same expected degree. See dcsbm() and mmsbm() for models with degree heterogeneity.

Edge formulation

Once we know the block memberships, we need one more ingredient, which is the baseline intensity of connections between nodes in block a and block b. This is given by the symmetric k×kk \times k matrix BB. Then each edge AijA_{ij} is Poisson distributed with parameter

λij=ziTBzj=∑a=1k∑b=1kZiaZjbBab.\lambda_{ij} = z_i^T B z_j = \sum_{a = 1}^k \sum_{b = 1}^k Z_{ia} Z_{jb} B_{ab}.

That is, every pair of blocks (a,b)(a, b) with ii in block aa and jj in block bb contributes BabB_{ab} to the expected number of edges between ii and jj, so two nodes that share more blocks connect at a higher rate. When expected_degree or expected_density is specified, BB is multiplied by a constant to achieve the desired value, so only the relative magnitudes of the entries of BB matter in that case.

In the factor model parameterization, the latent positions are X=ZX = Z and the mixing matrix SS is the symmetrized and rescaled BB, so that E[A∣Z]=ZSZT\mathbb{E}[A \mid Z] = Z S Z^T.

When poisson_edges = FALSE, the symmetrized and rescaled BB is instead treated as a matrix of Bernoulli probabilities, and replaced by −log⁡(1−B)-\log(1 - B) (elementwise) before sampling. Nodes ii and jj are then connected with probability

1−∏a=1k∏b=1k(1−Bab)ZiaZjb,1 - \prod_{a = 1}^k \prod_{b = 1}^k (1 - B_{ab})^{Z_{ia} Z_{jb}},

that is, each pair of shared blocks independently gets a chance to connect ii and jj. This is the "noisy-OR" model discussed in Section 3 of Kaufmann, Bonald and Lelarge (2016), and for sparse graphs it is close to the SBMO with Bernoulli edges.

Identifiability

Kaufmann, Bonald and Lelarge (2016, Theorem 1) show that the parameters kk, BB and ZZ of an SBMO are identifiable, up to a permutation of the block labels, when:

  1. BB is invertible, and

  2. there is at least one "pure node" in each block that belongs to no other blocks.

overlapping_sbm() checks that the symmetrized and rescaled BB (i.e. S) is invertible, and force_pure = TRUE guarantees the second condition. Kaufmann, Bonald and Lelarge (2016) further assume that every node belongs to at least one block, which overlapping_sbm() guarantees by reassigning nodes that join no block (see "Block memberships" above).

Related models

Latouche, Birmelé and Ambroise (2011) introduced the overlapping stochastic block model (OSBM), which also uses binary membership vectors but passes them through a logistic link, so that block contributions add up on the logit scale rather than on the scale of the edge rate. The OSBM is not implemented in fastRG.

The overlapping continuous community assignment model (OCCAM) of Zhang, Levina and Zhu (2020) generalizes the SBMO by allowing non-negative, real-valued membership vectors (normalized to have unit length) and per-node degree heterogeneity parameters θi\theta_i, with E[A∣Z,θ]=ΘZBZTΘ\mathbb{E}[A \mid Z, \theta] = \Theta Z B Z^T \Theta for Θ=diag(θ)\Theta = \mathrm{diag}(\theta). The SBMO can be viewed as a special case of the OCCAM (Kaufmann, Bonald and Lelarge 2016). overlapping_sbm() does not include degree heterogeneity parameters.

References

Kaufmann, Emilie, Thomas Bonald, and Marc Lelarge. 2016. "A Spectral Algorithm with Additive Clustering for the Recovery of Overlapping Communities in Networks." In Algorithmic Learning Theory (ALT 2016), edited by R. Ortner et al., 355–70. Lecture Notes in Computer Science, vol. 9925. Cham: Springer International Publishing. doi:10.1007/978-3-319-46379-7_24.

Latouche, Pierre, Etienne Birmelé, and Christophe Ambroise. 2011. "Overlapping Stochastic Block Models with Application to the French Political Blogosphere." The Annals of Applied Statistics 5 (1): 309–36. doi:10.1214/10-AOAS382.

Zhang, Yuan, Elizaveta Levina, and Ji Zhu. 2020. "Detecting Overlapping Communities in Networks Using Spectral Methods." SIAM Journal on Mathematics of Data Science 2 (2): 265–83. doi:10.1137/19M1272238. Preprint: https://arxiv.org/abs/1412.3432.

See Also

Other stochastic block models: dcsbm(), directed_dcsbm(), directed_planted_partition(), mmsbm(), planted_partition(), sbm()

Other undirected graphs: chung_lu(), dcsbm(), erdos_renyi(), mmsbm(), planted_partition(), sbm()

Examples

set.seed(27)

lazy_overlapping_sbm <- overlapping_sbm(n = 1000, k = 5, expected_density = 0.01)
lazy_overlapping_sbm

# block memberships: a binary matrix, nodes can belong to several blocks
lazy_overlapping_sbm$Z[1:5, ]

# how many blocks does each node belong to? every node belongs to
# at least one block
table(Matrix::rowSums(lazy_overlapping_sbm$Z))

# sometimes you gotta let the world burn and
# sample a wildly dense graph

dense_lazy_overlapping_sbm <- overlapping_sbm(n = 500, k = 3, expected_density = 0.8)
dense_lazy_overlapping_sbm

# explicitly setting the mixing matrix and block membership
# probabilities rather than using defaults. pi does not need to
# sum to one: here nodes belong to 1.7 blocks on average

k <- 5
n <- 1000
B <- matrix(stats::runif(k * k), nrow = k, ncol = k)

pi <- c(1, 2, 4, 1, 0.5) / 5

custom_overlapping_sbm <- overlapping_sbm(
  n = n,
  B = B,
  pi = pi,
  expected_degree = 5
)

custom_overlapping_sbm

# pi is sorted, and B is permuted to match
custom_overlapping_sbm$pi
colMeans(custom_overlapping_sbm$Z)

edgelist <- sample_edgelist(custom_overlapping_sbm)
edgelist

A <- sample_sparse(custom_overlapping_sbm)

# nodes that belong to more blocks have higher degree on average
memberships <- Matrix::rowSums(custom_overlapping_sbm$Z)
tapply(Matrix::rowSums(A), memberships, mean)

# efficient eigendecompostion that leverages low-rank structure in
# E(A) so that you don't have to form E(A) to find eigenvectors,
# as E(A) is typically dense. computation is
# handled via RSpectra

population_eigs <- eigs_sym(custom_overlapping_sbm)
population_eigs$values

Create an undirected planted partition object

Description

To specify a planted partition model, you must specify the number of nodes (via n), the mixing matrix (optional, either via within_block/between_block or a/b), and the relative block probabilites (optional, via pi). We provide defaults for most of these options to enable rapid exploration, or you can invest the effort for more control over the model parameters. We strongly recommend setting the expected_degree or expected_density argument to avoid large memory allocations associated with sampling large, dense graphs.

Usage

planted_partition(
  n,
  k,
  ...,
  within_block = NULL,
  between_block = NULL,
  a = NULL,
  b = NULL,
  block_sizes = NULL,
  pi = NULL,
  sort_nodes = TRUE,
  poisson_edges = TRUE,
  allow_self_loops = TRUE
)

Arguments

n

The number of nodes in the network. Must be a positive integer. This argument is required.

k

Number of planted partitions, as a positive integer. This argument is required.

...

Arguments passed on to undirected_factor_model

expected_degree

If specified, the desired expected degree of the graph. Specifying expected_degree simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

expected_density

If specified, the desired expected density of the graph, that is, the expected number of edges between distinct nodes divided by choose(n, 2). See expected_density(). Specifying expected_density simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

within_block

Probability of within block edges. Must be strictly between zero and one. Must specify either within_block and between_block, or a and b to determine edge probabilities.

between_block

Probability of between block edges. Must be strictly between zero and one. Must specify either within_block and between_block, or a and b to determine edge probabilities.

a

Integer such that a/n is the probability of edges within a block. Useful for sparse graphs. Must specify either within_block and between_block, or a and b to determine edge probabilities.

b

Integer such that b/n is the probability of edges between blocks. Useful for sparse graphs. Must specify either within_block and between_block, or a and b to determine edge probabilities.

block_sizes

(block sizes) Number of nodes in each block, as a vector of integers. Must match the dimensions of B, or k and must sum to n. Defaults to NULL, in which case blocks are made to be as balanced as possible. You can specify either pi or block_sizes, but not both.

pi

(block sizes) Relative block probabilities. Must be positive, but do not need to sum to one, as they will be normalized internally. Must match the dimensions of B or k. Defaults to NULL, in which case the block_sizes argument will take precedence. Note that you can specify either pi or block_sizes, but should not specify both.

sort_nodes

Logical indicating whether or not to sort the nodes so that they are grouped by block and by theta. Useful for plotting. Defaults to TRUE. When TRUE, nodes are first sorted by block membership, and then by degree-correction parameters within each block. Additionally, pi is sorted in increasing order, and the columns of the B matrix are permuted to match the new order of pi.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Details

A planted partition model is stochastic blockmodel in which the diagonal and the off-diagonal of the mixing matrix B are both constant. This means that edge probabilities depend only on whether two nodes belong to the same block, or to different blocks, but the particular blocks themselves don't have any impact apart from this.

Value

An undirected_planted_partition S3 object, which is a subclass of the sbm() object, with additional fields:

  • within_block: The probability of edge formation within a block.

  • between_block: The probability of edge formation between two distinct blocks.

See Also

Other stochastic block models: dcsbm(), directed_dcsbm(), directed_planted_partition(), mmsbm(), overlapping_sbm(), sbm()

Other undirected graphs: chung_lu(), dcsbm(), erdos_renyi(), mmsbm(), overlapping_sbm(), sbm()

Examples

set.seed(27)

lazy_pp <- planted_partition(
  n = 100,
  k = 5,
  expected_density = 0.01,
  within_block = 0.1,
  between_block = 0.01
)

lazy_pp

Plot (expected) adjacency matrices

Description

Plot (expected) adjacency matrices

Usage

plot_expectation(model)

plot_dense_matrix(A, ...)

plot_sparse_matrix(A)

Arguments

model

A directed_factor_model() or an undirected_factor_model() object.

A

A matrix(), Matrix::Matrix() or Matrix::sparseMatrix() object.

...

Unused.

Value

A ggplot2::ggplot2() plot.

Examples

set.seed(27)

model <- dcsbm(n = 10, k = 2, expected_density = 0.2)

plot_expectation(model)

A <- sample_sparse(model)

plot_sparse_matrix(A)

Sample a random edgelist from a random dot product graph

Description

There are two steps to using the fastRG package. First, you must parameterize a random dot product graph by sampling the latent factors. Use functions such as dcsbm(), sbm(), etc, to perform this specification. Then, use ⁠sample_*()⁠ functions to generate a random graph in your preferred format.

Usage

sample_edgelist(factor_model, ..., multigraph = TRUE)

## S3 method for class 'undirected_factor_model'
sample_edgelist(factor_model, ..., multigraph = TRUE)

## S3 method for class 'directed_factor_model'
sample_edgelist(factor_model, ..., multigraph = TRUE)

Arguments

factor_model

A directed_factor_model() or undirected_factor_model().

...

Ignored. Do not use.

multigraph

Logical scalar, only relevant for Poisson graphs (poisson_edges = TRUE), where a pair of nodes can be connected by more than one edge. When TRUE (the default), such repeated edges are represented as a multigraph, that is, as repeated edges (or repeated rows of an edgelist) without any edge weights. When FALSE, repeated edges between the same pair of nodes are collapsed into a single edge with an integer weight attribute that counts the number of times the edge was sampled. This weight is the corresponding entry of the adjacency matrix returned by sample_sparse(). In undirected graphs, the edges ⁠(i, j)⁠ and ⁠(j, i)⁠ are the same edge and are collapsed together. When multigraph = FALSE the weight attribute is always present, even for Bernoulli graphs (poisson_edges = FALSE), where every weight is 1.

Details

This function implements the fastRG algorithm as described in Rohe et al (2017). Please see the paper (which is short and open access!!) for details.

Value

A single realization of a random Poisson (or Bernoulli) Dot Product Graph, represented as a tibble::tibble() with two integer columns, from and to. When multigraph = FALSE, there is an additional integer column weight and each ⁠(from, to)⁠ pair appears at most once.

NOTE: Indices for isolated nodes will not appear in the edgelist! This can lead to issues if you construct network objects from the edgelist directly.

In the undirected case, from and to do not encode information about edge direction, but we will always have from <= to for convenience of edge identification.

To avoid handling such considerations yourself, we recommend using sample_sparse(), sample_igraph(), and sample_tidygraph() over sample_edgelist().

References

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

See Also

Other samplers: sample_edgelist.matrix(), sample_igraph(), sample_sparse(), sample_tidygraph()

Examples

library(igraph)
library(tidygraph)

set.seed(27)

##### undirected examples ----------------------------

n <- 100
k <- 5

X <- matrix(rpois(n = n * k, 1), nrow = n)
S <- matrix(runif(n = k * k, 0, .1), nrow = k)

# S will be symmetrized internal here, or left unchanged if
# it is already symmetric

ufm <- undirected_factor_model(
  X, S,
  expected_density = 0.1
)

ufm

### sampling graphs as edgelists ----------------------

edgelist <- sample_edgelist(ufm)
edgelist

### sampling graphs as sparse matrices ----------------

A <- sample_sparse(ufm)

inherits(A, "dsCMatrix")
isSymmetric(A)
dim(A)

B <- sample_sparse(ufm)

inherits(B, "dsCMatrix")
isSymmetric(B)
dim(B)

### sampling graphs as igraph graphs ------------------

sample_igraph(ufm)

### sampling graphs as tidygraph graphs ---------------

sample_tidygraph(ufm)

### weighted graphs instead of multigraphs ------------

# collapse repeated edges into a single edge with an integer weight

sample_edgelist(ufm, multigraph = FALSE)
sample_igraph(ufm, multigraph = FALSE)

##### directed examples ----------------------------

n2 <- 100

k1 <- 5
k2 <- 3

d <- 50

X <- matrix(rpois(n = n2 * k1, 1), nrow = n2)
S <- matrix(runif(n = k1 * k2, 0, .1), nrow = k1, ncol = k2)
Y <- matrix(rexp(n = k2 * d, 1), nrow = d)

fm <- directed_factor_model(X, S, Y, expected_in_degree = 2)
fm

### sampling graphs as edgelists ----------------------

edgelist2 <- sample_edgelist(fm)
edgelist2

### sampling graphs as sparse matrices ----------------

A2 <- sample_sparse(fm)

inherits(A2, "dgCMatrix")
isSymmetric(A2)
dim(A2)

B2 <- sample_sparse(fm)

inherits(B2, "dgCMatrix")
isSymmetric(B2)
dim(B2)

### sampling graphs as igraph graphs ------------------

# since the number of rows and the number of columns
# in `fm` differ, we will get a bipartite igraph here

# creating the bipartite igraph is slow relative to other
# sampling -- if this is a blocker for
# you please open an issue and we can investigate speedups

dig <- sample_igraph(fm)
is_bipartite(dig)

### sampling graphs as tidygraph graphs ---------------

sample_tidygraph(fm)

Low level interface to sample RPDG edgelists

Description

This is a brakes-off, no safety checks interface. We strongly recommend that you do not call sample_edgelist.matrix() unless you know what you are doing, and even then, we still do not recommend it, as you will bypass all typical input validation. extremely loud coughing All those who bypass input validation suffer foolishly at their own hand. extremely loud coughing

Usage

## S3 method for class 'matrix'
sample_edgelist(
  factor_model,
  S,
  Y,
  directed,
  poisson_edges,
  allow_self_loops,
  ...,
  multigraph = TRUE
)

## S3 method for class 'Matrix'
sample_edgelist(
  factor_model,
  S,
  Y,
  directed,
  poisson_edges,
  allow_self_loops,
  ...,
  multigraph = TRUE
)

Arguments

factor_model

An n by k1 matrix() or Matrix::Matrix() of latent node positions encoding incoming edge community membership. The X matrix in Rohe et al (2017). Naming differs only for consistency with the S3 generic.

S

A k1 by k2 mixing matrix() or Matrix::Matrix(). In the undirect case this is assumed to be symmetric but we do not check that this is the case.

Y

A d by k2 matrix() or Matrix::Matrix() of latent node positions encoding outgoing edge community membership.

directed

Logical indicating whether or not the graph should be directed. When directed = FALSE, symmetrizes S internally. Y = X together with a symmetric S implies a symmetric expectation (although not necessarily an undirected graph). When directed = FALSE, samples a directed graph with symmetric expectation, and then adds edges until symmetry is achieved.

poisson_edges

Whether or not to remove duplicate edges after sampling. See Section 2.3 of Rohe et al. (2017) for some additional details. Defaults to TRUE.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

...

Ignored, for generic consistency only.

multigraph

Logical scalar, only relevant for Poisson graphs (poisson_edges = TRUE), where a pair of nodes can be connected by more than one edge. When TRUE (the default), such repeated edges are represented as a multigraph, that is, as repeated edges (or repeated rows of an edgelist) without any edge weights. When FALSE, repeated edges between the same pair of nodes are collapsed into a single edge with an integer weight attribute that counts the number of times the edge was sampled. This weight is the corresponding entry of the adjacency matrix returned by sample_sparse(). In undirected graphs, the edges ⁠(i, j)⁠ and ⁠(j, i)⁠ are the same edge and are collapsed together. When multigraph = FALSE the weight attribute is always present, even for Bernoulli graphs (poisson_edges = FALSE), where every weight is 1.

Details

This function implements the fastRG algorithm as described in Rohe et al (2017). Please see the paper (which is short and open access!!) for details.

Value

A single realization of a random Poisson (or Bernoulli) Dot Product Graph, represented as a tibble::tibble() with two integer columns, from and to. When multigraph = FALSE, there is an additional integer column weight and each ⁠(from, to)⁠ pair appears at most once.

NOTE: Indices for isolated nodes will not appear in the edgelist! This can lead to issues if you construct network objects from the edgelist directly.

In the undirected case, from and to do not encode information about edge direction, but we will always have from <= to for convenience of edge identification.

To avoid handling such considerations yourself, we recommend using sample_sparse(), sample_igraph(), and sample_tidygraph() over sample_edgelist().

References

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

See Also

Other samplers: sample_edgelist(), sample_igraph(), sample_sparse(), sample_tidygraph()

Examples

set.seed(46)

n <- 10000
d <- 1000

k1 <- 5
k2 <- 3

X <- matrix(rpois(n = n * k1, 1), nrow = n)
S <- matrix(runif(n = k1 * k2, 0, .1), nrow = k1)
Y <- matrix(rpois(n = d * k2, 1), nrow = d)

sample_edgelist(X, S, Y, TRUE, TRUE, TRUE)

Sample a random dot product graph as an igraph graph

Description

There are two steps to using the fastRG package. First, you must parameterize a random dot product graph by sampling the latent factors. Use functions such as dcsbm(), sbm(), etc, to perform this specification. Then, use ⁠sample_*()⁠ functions to generate a random graph in your preferred format.

Usage

sample_igraph(factor_model, ..., multigraph = TRUE)

## S3 method for class 'undirected_factor_model'
sample_igraph(factor_model, ..., multigraph = TRUE)

## S3 method for class 'directed_factor_model'
sample_igraph(factor_model, ..., multigraph = TRUE)

Arguments

factor_model

A directed_factor_model() or undirected_factor_model().

...

Ignored. Do not use.

multigraph

Logical scalar, only relevant for Poisson graphs (poisson_edges = TRUE), where a pair of nodes can be connected by more than one edge. When TRUE (the default), such repeated edges are represented as a multigraph, that is, as repeated edges (or repeated rows of an edgelist) without any edge weights. When FALSE, repeated edges between the same pair of nodes are collapsed into a single edge with an integer weight attribute that counts the number of times the edge was sampled. This weight is the corresponding entry of the adjacency matrix returned by sample_sparse(). In undirected graphs, the edges ⁠(i, j)⁠ and ⁠(j, i)⁠ are the same edge and are collapsed together. When multigraph = FALSE the weight attribute is always present, even for Bernoulli graphs (poisson_edges = FALSE), where every weight is 1.

Details

This function implements the fastRG algorithm as described in Rohe et al (2017). Please see the paper (which is short and open access!!) for details.

Value

An igraph::igraph() object. For Poisson graphs (poisson_edges = TRUE) with multigraph = TRUE (the default), this is possibly a multigraph (that is, we take there to be multiple edges rather than weighted edges). With multigraph = FALSE, repeated edges are instead collapsed into a single edge, and every edge has an integer weight attribute equal to the corresponding entry of the sample_sparse() adjacency matrix (all weights are 1 when poisson_edges = FALSE).

When factor_model is undirected:

- the graph is undirected and one-mode.

When factor_model is directed and square:

- the graph is directed and one-mode.

When factor_model is directed and rectangular:

- the graph is undirected and bipartite.

Note that working with bipartite graphs in igraph is more complex than working with one-mode graphs.

References

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

See Also

Other samplers: sample_edgelist(), sample_edgelist.matrix(), sample_sparse(), sample_tidygraph()

Examples

library(igraph)
library(tidygraph)

set.seed(27)

##### undirected examples ----------------------------

n <- 100
k <- 5

X <- matrix(rpois(n = n * k, 1), nrow = n)
S <- matrix(runif(n = k * k, 0, .1), nrow = k)

# S will be symmetrized internal here, or left unchanged if
# it is already symmetric

ufm <- undirected_factor_model(
  X, S,
  expected_density = 0.1
)

ufm

### sampling graphs as edgelists ----------------------

edgelist <- sample_edgelist(ufm)
edgelist

### sampling graphs as sparse matrices ----------------

A <- sample_sparse(ufm)

inherits(A, "dsCMatrix")
isSymmetric(A)
dim(A)

B <- sample_sparse(ufm)

inherits(B, "dsCMatrix")
isSymmetric(B)
dim(B)

### sampling graphs as igraph graphs ------------------

sample_igraph(ufm)

### sampling graphs as tidygraph graphs ---------------

sample_tidygraph(ufm)

### weighted graphs instead of multigraphs ------------

# collapse repeated edges into a single edge with an integer weight

sample_edgelist(ufm, multigraph = FALSE)
sample_igraph(ufm, multigraph = FALSE)

##### directed examples ----------------------------

n2 <- 100

k1 <- 5
k2 <- 3

d <- 50

X <- matrix(rpois(n = n2 * k1, 1), nrow = n2)
S <- matrix(runif(n = k1 * k2, 0, .1), nrow = k1, ncol = k2)
Y <- matrix(rexp(n = k2 * d, 1), nrow = d)

fm <- directed_factor_model(X, S, Y, expected_in_degree = 2)
fm

### sampling graphs as edgelists ----------------------

edgelist2 <- sample_edgelist(fm)
edgelist2

### sampling graphs as sparse matrices ----------------

A2 <- sample_sparse(fm)

inherits(A2, "dgCMatrix")
isSymmetric(A2)
dim(A2)

B2 <- sample_sparse(fm)

inherits(B2, "dgCMatrix")
isSymmetric(B2)
dim(B2)

### sampling graphs as igraph graphs ------------------

# since the number of rows and the number of columns
# in `fm` differ, we will get a bipartite igraph here

# creating the bipartite igraph is slow relative to other
# sampling -- if this is a blocker for
# you please open an issue and we can investigate speedups

dig <- sample_igraph(fm)
is_bipartite(dig)

### sampling graphs as tidygraph graphs ---------------

sample_tidygraph(fm)

Sample a random dot product graph as a sparse Matrix

Description

There are two steps to using the fastRG package. First, you must parameterize a random dot product graph by sampling the latent factors. Use functions such as dcsbm(), sbm(), etc, to perform this specification. Then, use ⁠sample_*()⁠ functions to generate a random graph in your preferred format.

Usage

sample_sparse(factor_model, ...)

## S3 method for class 'undirected_factor_model'
sample_sparse(factor_model, ...)

## S3 method for class 'directed_factor_model'
sample_sparse(factor_model, ...)

Arguments

factor_model

A directed_factor_model() or undirected_factor_model().

...

Ignored. Do not use.

Details

This function implements the fastRG algorithm as described in Rohe et al (2017). Please see the paper (which is short and open access!!) for details.

Value

For undirected factor models, a sparse Matrix::Matrix() of class dsCMatrix. In particular, this means the Matrix object (1) has double data type, (2) is symmetric, and (3) is in column compressed storage format.

For directed factor models, a sparse Matrix::Matrix() of class dgCMatrix. This means the Matrix object (1) has double data type, (2) in not symmetric, and (3) is in column compressed storage format.

To reiterate: for undirected graphs, you will get a symmetric matrix. For directed graphs, you will get a general sparse matrix.

References

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

See Also

Other samplers: sample_edgelist(), sample_edgelist.matrix(), sample_igraph(), sample_tidygraph()

Examples

library(igraph)
library(tidygraph)

set.seed(27)

##### undirected examples ----------------------------

n <- 100
k <- 5

X <- matrix(rpois(n = n * k, 1), nrow = n)
S <- matrix(runif(n = k * k, 0, .1), nrow = k)

# S will be symmetrized internal here, or left unchanged if
# it is already symmetric

ufm <- undirected_factor_model(
  X, S,
  expected_density = 0.1
)

ufm

### sampling graphs as edgelists ----------------------

edgelist <- sample_edgelist(ufm)
edgelist

### sampling graphs as sparse matrices ----------------

A <- sample_sparse(ufm)

inherits(A, "dsCMatrix")
isSymmetric(A)
dim(A)

B <- sample_sparse(ufm)

inherits(B, "dsCMatrix")
isSymmetric(B)
dim(B)

### sampling graphs as igraph graphs ------------------

sample_igraph(ufm)

### sampling graphs as tidygraph graphs ---------------

sample_tidygraph(ufm)

### weighted graphs instead of multigraphs ------------

# collapse repeated edges into a single edge with an integer weight

sample_edgelist(ufm, multigraph = FALSE)
sample_igraph(ufm, multigraph = FALSE)

##### directed examples ----------------------------

n2 <- 100

k1 <- 5
k2 <- 3

d <- 50

X <- matrix(rpois(n = n2 * k1, 1), nrow = n2)
S <- matrix(runif(n = k1 * k2, 0, .1), nrow = k1, ncol = k2)
Y <- matrix(rexp(n = k2 * d, 1), nrow = d)

fm <- directed_factor_model(X, S, Y, expected_in_degree = 2)
fm

### sampling graphs as edgelists ----------------------

edgelist2 <- sample_edgelist(fm)
edgelist2

### sampling graphs as sparse matrices ----------------

A2 <- sample_sparse(fm)

inherits(A2, "dgCMatrix")
isSymmetric(A2)
dim(A2)

B2 <- sample_sparse(fm)

inherits(B2, "dgCMatrix")
isSymmetric(B2)
dim(B2)

### sampling graphs as igraph graphs ------------------

# since the number of rows and the number of columns
# in `fm` differ, we will get a bipartite igraph here

# creating the bipartite igraph is slow relative to other
# sampling -- if this is a blocker for
# you please open an issue and we can investigate speedups

dig <- sample_igraph(fm)
is_bipartite(dig)

### sampling graphs as tidygraph graphs ---------------

sample_tidygraph(fm)

Sample a random dot product graph as a tidygraph graph

Description

There are two steps to using the fastRG package. First, you must parameterize a random dot product graph by sampling the latent factors. Use functions such as dcsbm(), sbm(), etc, to perform this specification. Then, use ⁠sample_*()⁠ functions to generate a random graph in your preferred format.

Usage

sample_tidygraph(factor_model, ..., multigraph = TRUE)

## S3 method for class 'undirected_factor_model'
sample_tidygraph(factor_model, ..., multigraph = TRUE)

## S3 method for class 'directed_factor_model'
sample_tidygraph(factor_model, ..., multigraph = TRUE)

Arguments

factor_model

A directed_factor_model() or undirected_factor_model().

...

Ignored. Do not use.

multigraph

Logical scalar, only relevant for Poisson graphs (poisson_edges = TRUE), where a pair of nodes can be connected by more than one edge. When TRUE (the default), such repeated edges are represented as a multigraph, that is, as repeated edges (or repeated rows of an edgelist) without any edge weights. When FALSE, repeated edges between the same pair of nodes are collapsed into a single edge with an integer weight attribute that counts the number of times the edge was sampled. This weight is the corresponding entry of the adjacency matrix returned by sample_sparse(). In undirected graphs, the edges ⁠(i, j)⁠ and ⁠(j, i)⁠ are the same edge and are collapsed together. When multigraph = FALSE the weight attribute is always present, even for Bernoulli graphs (poisson_edges = FALSE), where every weight is 1.

Details

This function implements the fastRG algorithm as described in Rohe et al (2017). Please see the paper (which is short and open access!!) for details.

Value

A tidygraph::tbl_graph() object. For Poisson graphs (poisson_edges = TRUE) with multigraph = TRUE (the default), this is possibly a multigraph (that is, we take there to be multiple edges rather than weighted edges). With multigraph = FALSE, repeated edges are instead collapsed into a single edge, and the edge data has an integer weight column equal to the corresponding entry of the sample_sparse() adjacency matrix (all weights are 1 when poisson_edges = FALSE).

When factor_model is undirected:

- the graph is undirected and one-mode.

When factor_model is directed and square:

- the graph is directed and one-mode.

When factor_model is directed and rectangular:

- the graph is undirected and bipartite.

Note that working with bipartite graphs in tidygraph is more complex than working with one-mode graphs.

References

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

See Also

Other samplers: sample_edgelist(), sample_edgelist.matrix(), sample_igraph(), sample_sparse()

Examples

library(igraph)
library(tidygraph)

set.seed(27)

##### undirected examples ----------------------------

n <- 100
k <- 5

X <- matrix(rpois(n = n * k, 1), nrow = n)
S <- matrix(runif(n = k * k, 0, .1), nrow = k)

# S will be symmetrized internal here, or left unchanged if
# it is already symmetric

ufm <- undirected_factor_model(
  X, S,
  expected_density = 0.1
)

ufm

### sampling graphs as edgelists ----------------------

edgelist <- sample_edgelist(ufm)
edgelist

### sampling graphs as sparse matrices ----------------

A <- sample_sparse(ufm)

inherits(A, "dsCMatrix")
isSymmetric(A)
dim(A)

B <- sample_sparse(ufm)

inherits(B, "dsCMatrix")
isSymmetric(B)
dim(B)

### sampling graphs as igraph graphs ------------------

sample_igraph(ufm)

### sampling graphs as tidygraph graphs ---------------

sample_tidygraph(ufm)

### weighted graphs instead of multigraphs ------------

# collapse repeated edges into a single edge with an integer weight

sample_edgelist(ufm, multigraph = FALSE)
sample_igraph(ufm, multigraph = FALSE)

##### directed examples ----------------------------

n2 <- 100

k1 <- 5
k2 <- 3

d <- 50

X <- matrix(rpois(n = n2 * k1, 1), nrow = n2)
S <- matrix(runif(n = k1 * k2, 0, .1), nrow = k1, ncol = k2)
Y <- matrix(rexp(n = k2 * d, 1), nrow = d)

fm <- directed_factor_model(X, S, Y, expected_in_degree = 2)
fm

### sampling graphs as edgelists ----------------------

edgelist2 <- sample_edgelist(fm)
edgelist2

### sampling graphs as sparse matrices ----------------

A2 <- sample_sparse(fm)

inherits(A2, "dgCMatrix")
isSymmetric(A2)
dim(A2)

B2 <- sample_sparse(fm)

inherits(B2, "dgCMatrix")
isSymmetric(B2)
dim(B2)

### sampling graphs as igraph graphs ------------------

# since the number of rows and the number of columns
# in `fm` differ, we will get a bipartite igraph here

# creating the bipartite igraph is slow relative to other
# sampling -- if this is a blocker for
# you please open an issue and we can investigate speedups

dig <- sample_igraph(fm)
is_bipartite(dig)

### sampling graphs as tidygraph graphs ---------------

sample_tidygraph(fm)

Create an undirected stochastic blockmodel object

Description

To specify a stochastic blockmodel, you must specify the number of nodes (via n), the mixing matrix (via k or B), and the relative block probabilites (optional, via pi). We provide defaults for most of these options to enable rapid exploration, or you can invest the effort for more control over the model parameters. We strongly recommend setting the expected_degree or expected_density argument to avoid large memory allocations associated with sampling large, dense graphs.

Usage

sbm(
  n,
  k = NULL,
  B = NULL,
  ...,
  block_sizes = NULL,
  pi = NULL,
  sort_nodes = TRUE,
  poisson_edges = TRUE,
  allow_self_loops = TRUE
)

Arguments

n

The number of nodes in the network. Must be a positive integer. This argument is required.

k

(mixing matrix) The number of blocks in the blockmodel. Use when you don't want to specify the mixing-matrix by hand. When k is specified, the elements of B are drawn randomly from a Uniform(0, 1) distribution. This is subject to change, and may not be reproducible. k defaults to NULL. You must specify either k or B, but not both.

B

(mixing matrix) A k by k matrix of block connection probabilities. The probability that a node in block i connects to a node in community j is Poisson(B[i, j]). Must be a square matrix. matrix and Matrix objects are both acceptable. If B is not symmetric, it will be symmetrized via the update B := B + t(B) / 2. Defaults to NULL. You must specify either k or B, but not both.

...

Arguments passed on to undirected_factor_model

expected_degree

If specified, the desired expected degree of the graph. Specifying expected_degree simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

expected_density

If specified, the desired expected density of the graph, that is, the expected number of edges between distinct nodes divided by choose(n, 2). See expected_density(). Specifying expected_density simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

block_sizes

(block sizes) Number of nodes in each block, as a vector of integers. Must match the dimensions of B, or k and must sum to n. Defaults to NULL, in which case blocks are made to be as balanced as possible. You can specify either pi or block_sizes, but not both.

pi

(block sizes) Relative block probabilities. Must be positive, but do not need to sum to one, as they will be normalized internally. Must match the dimensions of B or k. Defaults to NULL, in which case the block_sizes argument will take precedence. Note that you can specify either pi or block_sizes, but should not specify both.

sort_nodes

Logical indicating whether or not to sort the nodes so that they are grouped by block and by theta. Useful for plotting. Defaults to TRUE. When TRUE, nodes are first sorted by block membership, and then by degree-correction parameters within each block. Additionally, pi is sorted in increasing order, and the columns of the B matrix are permuted to match the new order of pi.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Details

A stochastic block is equivalent to a degree-corrected stochastic blockmodel where the degree heterogeneity parameters have all been set equal to 1.

Value

An undirected_sbm S3 object, which is a subclass of the dcsbm() object.

See Also

Other stochastic block models: dcsbm(), directed_dcsbm(), directed_planted_partition(), mmsbm(), overlapping_sbm(), planted_partition()

Other undirected graphs: chung_lu(), dcsbm(), erdos_renyi(), mmsbm(), overlapping_sbm(), planted_partition()

Examples

set.seed(27)

lazy_sbm <- sbm(n = 100, k = 5, expected_density = 0.01)
lazy_sbm

# by default we get a multigraph (i.e. multiple edges are
# allowed between the same two nodes). using bernoulli edges
# will with an adjacency matrix with only zeroes and ones

bernoulli_sbm <- sbm(
  n = 500,
  k = 30,
  poisson_edges = FALSE,
  expected_degree = 8
)

bernoulli_sbm

edgelist <- sample_edgelist(bernoulli_sbm)
edgelist

A <- sample_sparse(bernoulli_sbm)

# only zeroes and ones!
sign(A)


# sbm with repeated eigenvalues

# block sizes equal by default, needed to prevent variation in spectrum
# from variation in block sizes. also need B to have a single repeated
# eigenvalue

repeated_eigen <- sbm(
  n = 100,
  B = diag(rep(0.8, 5)),
  expected_degree = 10
)

# exactly repeated eigenvalues in the population
e <- eigs_sym(repeated_eigen)
e$values

Compute the singular value decomposition of the expected adjacency matrix of a directed factor model

Description

Compute the singular value decomposition of the expected adjacency matrix of a directed factor model

Usage

## S3 method for class 'directed_factor_model'
svds(A, k = min(A$k1, A$k2), nu = k, nv = k, opts = list(), ...)

Arguments

A

An undirected_factor_model().

k

Desired rank of decomposition.

nu

Number of left singular vectors to be computed. This must be between 0 and k.

nv

Number of right singular vectors to be computed. This must be between 0 and k.

opts

Control parameters related to the computing algorithm. See Details below.

...

Unused, included only for consistency with generic signature.

Details

The opts argument is a list that can supply any of the following parameters:

ncv

Number of Lanzcos basis vectors to use. More vectors will result in faster convergence, but with greater memory use. ncv must be satisfy k<ncv≤pk < ncv \le p where p = min(m, n). Default is min(p, max(2*k+1, 20)).

tol

Precision parameter. Default is 1e-10.

maxitr

Maximum number of iterations. Default is 1000.

center

Either a logical value (TRUE/FALSE), or a numeric vector of length nn. If a vector cc is supplied, then SVD is computed on the matrix A−1c′A - 1c', in an implicit way without actually forming this matrix. center = TRUE has the same effect as center = colMeans(A). Default is FALSE.

scale

Either a logical value (TRUE/FALSE), or a numeric vector of length nn. If a vector ss is supplied, then SVD is computed on the matrix (A−1c′)S(A - 1c')S, where cc is the centering vector and S=diag(1/s)S = diag(1/s). If scale = TRUE, then the vector ss is computed as the column norm of A−1c′A - 1c'. Default is FALSE.


Compute the singular value decomposition of the expected adjacency matrix of an undirected factor model

Description

Compute the singular value decomposition of the expected adjacency matrix of an undirected factor model

Usage

## S3 method for class 'undirected_factor_model'
svds(A, k = A$k, nu = k, nv = k, opts = list(), ...)

Arguments

A

An undirected_factor_model().

k

Desired rank of decomposition.

nu

Number of left singular vectors to be computed. This must be between 0 and k.

nv

Number of right singular vectors to be computed. This must be between 0 and k.

opts

Control parameters related to the computing algorithm. See Details below.

...

Unused, included only for consistency with generic signature.

Details

The opts argument is a list that can supply any of the following parameters:

ncv

Number of Lanzcos basis vectors to use. More vectors will result in faster convergence, but with greater memory use. ncv must be satisfy k<ncv≤pk < ncv \le p where p = min(m, n). Default is min(p, max(2*k+1, 20)).

tol

Precision parameter. Default is 1e-10.

maxitr

Maximum number of iterations. Default is 1000.

center

Either a logical value (TRUE/FALSE), or a numeric vector of length nn. If a vector cc is supplied, then SVD is computed on the matrix A−1c′A - 1c', in an implicit way without actually forming this matrix. center = TRUE has the same effect as center = colMeans(A). Default is FALSE.

scale

Either a logical value (TRUE/FALSE), or a numeric vector of length nn. If a vector ss is supplied, then SVD is computed on the matrix (A−1c′)S(A - 1c')S, where cc is the centering vector and S=diag(1/s)S = diag(1/s). If scale = TRUE, then the vector ss is computed as the column norm of A−1c′A - 1c'. Default is FALSE.


Create an undirected factor model graph

Description

An undirected factor model graph is an undirected generalized Poisson random dot product graph. The edges in this graph are assumed to be independent and Poisson distributed. The graph is parameterized by its expected adjacency matrix, which is ⁠E[A|X] = X S X'⁠. We do not recommend that casual users use this function, see instead dcsbm() and related functions, which will formulate common variants of the stochastic blockmodels as undirected factor models with lots of helpful input validation.

Usage

undirected_factor_model(
  X,
  S,
  ...,
  expected_degree = NULL,
  expected_density = NULL,
  poisson_edges = TRUE,
  allow_self_loops = TRUE
)

Arguments

X

A matrix() or Matrix::Matrix() representing real-valued latent node positions. Entries must be positive.

S

A matrix() or Matrix::Matrix() mixing matrix. S is symmetrized if it is not already, as this is the undirected case. Entries must be positive.

...

Ignored. Must be empty.

expected_degree

If specified, the desired expected degree of the graph. Specifying expected_degree simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

expected_density

If specified, the desired expected density of the graph, that is, the expected number of edges between distinct nodes divided by choose(n, 2). See expected_density(). Specifying expected_density simply rescales S to achieve this. Defaults to NULL. Do not specify both expected_degree and expected_density at the same time.

poisson_edges

Logical indicating whether or not multiple edges are allowed to form between a pair of nodes. Defaults to TRUE. When FALSE, sampling proceeds as usual, and duplicate edges are removed afterwards. Further, when FALSE, we assume that S specifies a desired between-factor connection probability, and back-transform this S to the appropriate Poisson intensity parameter to approximate Bernoulli factor connection probabilities. See Section 2.3 of Rohe et al. (2017) for some additional details.

allow_self_loops

Logical indicating whether or not nodes should be allowed to form edges with themselves. Defaults to TRUE. When FALSE, sampling proceeds allowing self-loops, and these are then removed after the fact.

Value

An undirected_factor_model S3 class based on a list with the following elements:

  • X: The latent positions as a Matrix::Matrix() object.

  • S: The mixing matrix as a Matrix::Matrix() object.

  • n: The number of nodes in the network.

  • k: The rank of expectation matrix. Equivalently, the dimension of the latent node position vectors.

Examples

n <- 100
k <- 5

X <- matrix(rpois(n = n * k, 1), nrow = n)
S <- matrix(runif(n = k * k, 0, .1), nrow = k)

ufm <- undirected_factor_model(X, S)
ufm

ufm2 <- undirected_factor_model(X, S, expected_degree = 50)
ufm2

svds(ufm2)