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 |
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.)
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.
Arash A. Amini
Maintainer: Arash A. Amini <[email protected]>
On Semidefinite relaxations of the block model by A.A. Amini and E. Levina.
Fits a balanced stochastic block model to an adjacency matrix using SDP-1. The function implements a first-order ADMM solver for SDP-1.
sdp1_admm(As, K, opts)
sdp1_admm(As, K, opts)
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.) |
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. |
Arash A. Amini
On Semidefinite relaxations of the block model by A.A. Amini and E. Levina.
# 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)
# 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)