SDP {NAC}

Semidefinite programming for Community Detection in Networks with Covariates.

Description

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

Usage

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

Arguments

Adj

An n \times n symmetric adjacency matrix with diagonals being 0 and positive entries being 1.

Covariate

An n \times p 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 which is no larger than n. This is the predefined number of communities.

alpha

The element-wise upper bound in the SDP.

rho

The learning rate of SDP.

TT

The maximum of iteration.

tol

The tolerance for stopping criterion.

quiet

An optional input, indicating whether to print result at each step.

report_interval

An optional input. The frequency to print intermediate result.

r

An optional input. The expected rank of the solution, leave NULL if no constraint is required.

Details

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

Value

estall

A factor indicating nodes' labels. Items sharing the same label are in the same community.

References

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

Examples

# Simulate the Network
n = 10; K = 2; p =5; prob1 = 0.9;
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)]
Q = 0.1*matrix(sign(runif(p*K) - 0.5), nrow = p);
for(i in 1:K){
  Q[(i-1)*(p/K)+(1:(p/K)), i] = 0.3; #remark. has a change here
}
W = matrix(0, nrow = n, ncol = K);
for(jj in 1:n) {
  pp = rep(1/(K-1), K); pp[l[jj]] = 0;
  if(runif(1) <= prob1) {W[jj, 1:K] = Pi[jj, ];}
  else
  W[jj, sample(K, 1, prob = pp)] = 1;
  }
W = t(W)
D0 = Q %*% W
D = matrix(0, n, p)
for (i in 1:n){
  D[i,] = rnorm(p, mean = D0[,i], sd = 1);
}
SDP(Adj, D, lambda = 0.2, K = 2, alpha = 0.5, rho = 2, TT = 100, tol = 5)