Overview
INCVCommunityDetection implements Inductive
Node-Splitting Cross-Validation (INCV) for selecting the number
of communities in Stochastic Block Models (SBM). The package also
provides competing methods — CROISSANT, Edge
Cross-Validation (ECV), and Node Cross-Validation
(NCV) — for comprehensive model selection in network
analysis.
Simulating a network
We start by generating a network from a planted-partition SBM with 3
communities, 150 nodes, within-community connection probability 0.5, and
between-community probability 0.05.
library(INCVCommunityDetection)
set.seed(42)
net <- community.sim(k = 3, n = 150, n1 = 50, p = 0.5, q = 0.05)
table(net$membership)
#>
#> 1 2 3
#> 50 50 50
The adjacency matrix is a 150 × 150 binary symmetric matrix:
dim(net$adjacency)
#> [1] 150 150
ord <- order(net$membership)
image(net$adjacency[ord, ord],
main = "Adjacency matrix (3-community SBM, reordered)",
xlab = "Node", ylab = "Node")
Selecting K with INCV (f-fold)
The main function nscv.f.fold() partitions nodes into
f folds and uses spectral clustering on the training
subgraph. Held-out nodes are assigned to communities based on their
connections to training nodes, and the held-out negative log-likelihood
and MSE are computed.
result <- nscv.f.fold(net$adjacency, k.vec = 2:6, f = 5)
result$k.loss # K selected by neg-log-likelihood
#> [1] 3
result$k.mse # K selected by MSE
#> [1] 3
We can inspect the full CV loss curve:
plot(2:6, result$cv.loss, type = "b", pch = 19,
xlab = "Number of communities (K)",
ylab = "CV Negative Log-Likelihood",
main = "INCV f-fold: CV loss by K")
abline(v = result$k.loss, lty = 2, col = "red")
Selecting K with INCV (random split)
An alternative is to use repeated random node splits instead of fixed
folds:
result2 <- nscv.random.split(net$adjacency, k.vec = 2:6,
split = 0.66, ite = 20)
result2$k.chosen
#> [1] 3
plot(2:6, result2$cv.loss, type = "b", pch = 19,
xlab = "Number of communities (K)",
ylab = "CV Negative Log-Likelihood",
main = "INCV random-split: CV loss by K")
abline(v = result2$k.chosen, lty = 2, col = "red")
Spectral clustering and probability estimation
The building blocks are also available directly:
cl <- SBM.spectral.clustering(net$adjacency, k = 3)
table(cl$cluster)
#>
#> 1 2 3
#> 50 50 50
prob <- SBM.prob(cl$cluster, k = 3, A = net$adjacency, restricted = TRUE)
round(prob$p.matrix, 3)
#> [,1] [,2] [,3]
#> [1,] 0.502 0.050 0.050
#> [2,] 0.050 0.502 0.050
#> [3,] 0.050 0.050 0.502
Distance-decaying SBM simulation
For more realistic simulations, community.sim.sbm()
generates networks where block probabilities decay with community
distance:
net2 <- community.sim.sbm(n = 120, n1 = 40, eta = 0.3, rho = 0.2, K = 4)
round(net2$conn, 4)
#> [,1] [,2] [,3] [,4]
#> [1,] 0.2000 0.060 0.018 0.0054
#> [2,] 0.0600 0.200 0.060 0.0180
#> [3,] 0.0180 0.060 0.200 0.0600
#> [4,] 0.0054 0.018 0.060 0.2000