| Type: | Package |
| Title: | Semidefinite Programming for Fitting Block Models of Equal Block Sizes |
| Version: | 0.2 |
| Date: | 2015-06-18 |
| Author: | Arash A. Amini |
| Maintainer: | Arash A. Amini <amini.aa@gmail.com> |
| 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.) |
| License: | GPL-3 |
| Imports: | Rcpp (≥ 0.11.6) |
| LinkingTo: | Rcpp, RcppArmadillo |
| NeedsCompilation: | yes |
| Packaged: | 2015-06-21 05:51:08 UTC; arash |
| Repository: | CRAN |
| Date/Publication: | 2015-06-22 01:31:11 |
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 <amini.aa@gmail.com>
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)