Package 'sbmSDP'

Title: Semidefinite Programming for Fitting Block Models of Equal Block Sizes
Description: An ADMM implementation of SDP-1, a semidefinite programming relaxation of the maximum likelihood estimator for fitting a block model. SDP-1 has a tendency to produce equal-sized blocks and is ideal for producing a form of network histogram approximating a nonparametric graphon model. Alternatively, it can be used for community detection. (This is experimental code, proceed with caution.)
Authors: Arash A. Amini
Maintainer: Arash A. Amini <[email protected]>
License: GPL-3
Version: 0.2
Built: 2024-11-22 06:30:27 UTC
Source: CRAN

Help Index


Semidefinite Programming for Fitting Block Models of Equal Block Sizes

Description

An ADMM implementation of SDP-1, a semidefinite programming relaxation of the maximum likelihood estimator for fitting a block model. SDP-1 has a tendency to produce equal-sized blocks and is ideal for producing a form of network histogram approximating a nonparametric graphon model. Alternatively, it can be used for community detection. (This is experimental code, proceed with caution.)

Details

Package: sbmSDP
Type: Package
Version: 0.2
Date: 2015-06-18
License: GPL-3

An ADMM implementation of SDP-1 algorithm for fitting stochastic block models (SBMs). The main function is sdp1_admm.

Author(s)

Arash A. Amini

Maintainer: Arash A. Amini <[email protected]>

References

On Semidefinite relaxations of the block model by A.A. Amini and E. Levina.


SDP-1 algorithm

Description

Fits a balanced stochastic block model to an adjacency matrix using SDP-1. The function implements a first-order ADMM solver for SDP-1.

Usage

sdp1_admm(As, K, opts)

Arguments

As

a binary adjacency matrix.

K

number of communities (or blocks).

opts

a list containing options. Pass the empty list, that is, "list()", to use the default values. (See examples.)

Value

A list containing the following items:

X

the estimated cluster matrix.

delta

a vector of norm differences between consecutive cluster matrices at each step of the ADMM iteration.

T_term

number of actual iterations performed.

Author(s)

Arash A. Amini

References

On Semidefinite relaxations of the block model by A.A. Amini and E. Levina.

Examples

# Create a simple blkmodel with K=3 communities each of size m=20
blkmodel <- list(m=20, K=3, p=.9, q=.4)
blkmodel <- within(blkmodel, { 
                   n <- m*K
                   M <- kronecker(matrix(c(p,q,q,q,p,q,q,q,p),nrow=3),matrix(1,m,m))
                   As <- 1*(matrix(runif(n^2),nrow=n) < M)
                   })
# Call sdp1_admm with options:
#  rho  the ADMM parameter, 
#  T    maximum number of iteration
#  tol  tolerance for norm(X_{t+1} - X_t)
#  report_interval  how many iteration between reporting progress
sdp.fit <- with(blkmodel, 
                sdp1_admm(as.matrix(As), K, list(rho=.1, T=10000, tol=1e-5, report_interval=100)))

# plot the adjacency matrix and the estimated cluster matrix
par(mfrow=c(1,2))
image(blkmodel$As)
image(sdp.fit$X)