fastRG::sbm without setting expected_degree is doubling the number of edges that should be there.

library(fastRG)
library(magrittr)

n = 1000
pop = n/2
a = .1
b = .05
B = matrix(c(a,b,b,a), nrow = 2)
b_model = fastRG::sbm(n = n, k =2, 
                          B = B,  edge_distribution = "bernoulli")

b_model %>% 
  sample_sparse(poisson_edges = F) %>% 
  rowSums %>% mean

pop*a + pop*b  # this should be average degree

Dividing B by two fixes the problem:

b_model = fastRG::sbm(n = n, k =2, 
                          B = B/2,  edge_distribution = "bernoulli")

b_model %>% 
  sample_sparse(poisson_edges = F) %>% 
  rowSums %>% mean

Perhaps we are symmetrizing the edges at some point... this would double the number of edges.

This is an intentional choice. If you want to count "undirected" edges you should just consider the upper triangle here. That is, the edge count is based on the actual edges in the graph rather the elements in the sparse matrix representation of the graph. I spent a lot longer than I anticipated running into confusing inconsistencies between the undirected and directed samplers until I settled on this convention, and am pretty convinced it is the right way to implement things.

If you want to specify E[A] for an undirected SBM according to row means, we can consider adding an option for that, but I don't think we should call rowMeans(E[A]) the average degree.

library(fastRG)
#> Loading required package: Matrix
library(magrittr)

n <- 1000
pop <- n / 2
a <- .1
b <- .05
B <- matrix(c(a, b, b, a), nrow = 2)

b_model <- sbm(
  n = n, k = 2,
  B = B, edge_distribution = "bernoulli"
)

A <- sample_sparse(b_model)

mean(rowSums(A))  # double counts undirected edges
#> [1] 156.269
mean(rowSums(triu(A)))  # right way to count undirected edges in E[A]
#> [1] 78.194


pop * a + pop * b  # expected "undirected edge degree"
#> [1] 75

^{Created on 2021-06-29 by the reprex package (v2.0.0)}

Crap there's some inconsistency in edge counting. Will resolve.

library(fastRG)
#> Loading required package: Matrix
library(magrittr)

n <- 1000
pop <- n / 2
a <- .1
b <- .05
B <- matrix(c(a, b, b, a), nrow = 2)

b_model <- sbm(
  n = n, k = 2,
  B = B, edge_distribution = "bernoulli"
)

A <- sample_sparse(b_model)

mean(rowSums(A))  # double counts undirected edges
#> [1] 156.845
mean(rowSums(triu(A)))  # right way to count undirected edges in E[A]
#> [1] 78.479


pop * a + pop * b  # expected "undirected edge degree"
#> [1] 75

model2 <- sbm(n = n, k = 2, B = B, edge_distribution = "bernoulli", expected_degree = 75)
A2 <- sample_sparse(model2)

mean(rowSums(A2))  # double counts undirected edges
#> [1] 76.393
mean(rowSums(triu(A2)))  # right way to count undirected edges in E[A]
#> [1] 38.225

^{Created on 2021-06-29 by the reprex package (v2.0.0)}

Correctly count possible undirected edges

Undirected edge, degree and density counts should now be consistent. Example below.

library(fastRG)
#> Loading required package: Matrix
library(magrittr)

n <- 1000
pop <- n / 2
a <- .1
b <- .05
B <- matrix(c(a, b, b, a), nrow = 2)

b_model <- sbm(
  n = n, k = 2,
  B = B, edge_distribution = "bernoulli"
)

# model display corrected, both expected degree and density
b_model
#> Undirected Stochastic Blockmodel
#> --------------------------------
#> 
#> Nodes (n): 1000 (arranged by block)
#> Blocks (k): 2
#> 
#> Traditional SBM parameterization:
#> 
#> Block memberships (z): 1000 [factor] 
#> Block probabilities (pi): 2 [numeric] 
#> Edge distribution: bernoulli
#> 
#> Factor model parameterization:
#> 
#> X: 1000 x 2 [dgeMatrix] 
#> S: 2 x 2 [dsyMatrix] 
#> 
#> Expected edges: 78329
#> Expected degree: 78.3
#> Expected density: 0.15681

A <- sample_sparse(b_model)

mean(rowSums(A))  # double counts undirected edges
#> [1] 155.641
mean(rowSums(triu(A)))  # right way to count undirected edges in E[A]
#> [1] 77.876

sum(triu(A)) / choose(n, 2)  # correct "undirected" density
#> [1] 0.1559079


pop * a + pop * b  # expected "undirected edge degree"
#> [1] 75

model2 <- sbm(n = n, k = 2, B = B, edge_distribution = "bernoulli", expected_degree = 75)
A2 <- sample_sparse(model2)

mean(rowSums(A2))  # double counts undirected edges
#> [1] 155.995
mean(rowSums(triu(A2)))  # right way to count undirected edges in E[A]
#> [1] 78.053

sum(triu(A)) / choose(n, 2)  # correct "undirected" density 
#> [1] 0.1559079

^{Created on 2022-06-29 by the reprex package (v2.0.1.9000)}

More consistency with degree/density scaling for undirected graphs (#27)

Okay, so I had a moment of confusion about upper triangles the last time I tried to sort this out. I think the confusion arose because:

expected degree of an individual node
expected degree of the overall network
expected density of the network

are all slightly different computations that need to be considered slightly differently when thinking about directed vs undirected edges.

Fix coming in #44. TL;DR: population spectrums and edge counts have been off by a factor of two for a while

Fixes #19 for real. Closes #43. Closes #33. Closes #31.

Fix #19 for real and document extensively

Navigation Menu

Repository navigation

fastRG::sbm without setting expected_degree is doubling the number of edges that should be there. #19

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

fastRG::sbm without setting expected_degree is doubling the number of edges that should be there. #19

Description

Activity

alexpghayes commented on Jun 29, 2021

alexpghayes commented on Jun 29, 2021

alexpghayes commented on Jun 29, 2022

alexpghayes commented on Nov 10, 2025

alexpghayes commented on Nov 10, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions