ADMM: Penalized Optimization Framework for Community Detection in Networks with Covariates.

Description

Semidefinite programming for optimizing the inner product between combined network and the solution matrix.

Usage

ADMM(
  Adj,
  Covariate,
  lambda,
  K,
  alpha,
  rho,
  TT,
  tol,
  quiet = NULL,
  report_interval = NULL,
  r = NULL
)

Value

estall: A lavel vector.

Arguments

Adj: A 0/1 adjacency matrix.
Covariate: A covariate matrix. The rows correspond to nodes and the columns correspond to covariates.
lambda: A tuning parameter to weigh the covariate matrix.
K: A positive integer, indicating the number of underlying communities in graph Adj.
alpha: A number. The elementwise upper bound in the SDP.
rho: The learning rate of ADMM.
TT: The maximum of iteration.
tol: The tolerance for stopping criterion.
quiet: An optional inoput. Whether to print result at each step.
report_interval: An optional inoput. The frequency to print intermediate result.
r: An optional inoput. The expected rank of the solution, leave NULL if no constraint is required.

Details

ADMM is proposed in Covariate Regularized Community Detection in Sparse Graphs of Yan & Sarkar (2021). ADMM relies on semidefinite programming (SDP) relaxations for detecting the community structure in sparse networks with covariates.

References

Yan, B., & Sarkar, P. (2021). Covariate Regularized Community Detection in Sparse Graphs. Journal of the American Statistical Association, 116(534), 734-745.
tools:::Rd_expr_doi("10.1080/01621459.2019.1706541")

Examples

Run this code


# Simulate the Network
n = 10; K = 2;
theta = 0.4 + (0.45-0.05)*(seq(1:n)/n)^2; Theta = diag(theta);
P  = matrix(c(0.8, 0.2, 0.2, 0.8), byrow = TRUE, nrow = K)
set.seed(2022)
l = sample(1:K, n, replace=TRUE); # node labels
Pi = matrix(0, n, K) # label matrix
for (k in 1:K){
  Pi[l == k, k] = 1
}
Omega = Theta %*% Pi %*% P %*% t(Pi) %*% Theta;
Adj = matrix(runif(n*n, 0, 1), nrow = n);
Adj = Omega - Adj;
Adj = 1*(Adj >= 0)
diag(Adj) = 0
Adj[lower.tri(Adj)] = t(Adj)[lower.tri(Adj)]
caseno = 4; Nrange = 10; Nmin = 10; prob1 = 0.9; p = n*4;
Q = matrix(runif(p*K, 0, 1), nrow = p, ncol = K)
Q = sweep(Q,2,colSums(Q),`/`)
W = matrix(0, nrow = n, ncol = K);
for(jj in 1:n) {
  if(runif(1) <= prob1) {W[jj, 1:K] = Pi[jj, ];}
  else W[jj, sample(K, 1)] = 1;
}
W = t(W)
D0 = Q %*% W
X = matrix(0, n, p)
N = switch(caseno, rep(100, n), rep(100, n), round(runif(n)*Nrange+ Nmin),
  round(runif(n)* Nrange+Nmin))
for (i in 1: ncol(D0)){
  X[i, ] = rmultinom(1, N[i], D0[, i])
}
ADMM(Adj, X, lambda = 0.2, K = K, alpha = 0.5, rho = 2, TT = 100, tol = 5)

Run the code above in your browser using DataLab