GMPro (version 0.1.0)

DP_SBM: Degree profile graph matching with community detection.

Description

Given two community-structured networks, this function first applies a spectral clustering method SCORE to detect perceivable communities and then applies DPmatching or EEpost to match different communities. More details are in SCORE, DPmatching and EEpost.

Usage

DP_SBM(
  A,
  B,
  K,
  fun = c("DPmatching", "EEpost"),
  rep = NULL,
  tau = NULL,
  d = NULL
)

Arguments

A, B

Two 0/1 addjacency matrices.

K

A positive integer, the number of communities in A and B.

fun

A graph matching algorithm. Choices include DPmatching and EEpost.

rep

A parameter if choosing EEpost as the initial graph matching algorithm.

tau

Optional parameter if choosing EEpost as the initial graph matching algorithm. The default value is \(rep/10\).

d

Optional parameter if choosing EEpost as the initial graph matching algorithm. The default value is 1.

Value

A list of matching results for all possible permutations on {1,...,K}.

Details

The graphs to be matched are expected to have community structures. The result is the collection of all possible permutations on {1,...,K}.

Examples

# NOT RUN {
### Here we use graphs under stochastic block model(SBM).
set.seed(2020)
K = 2; n = 30; s = 1;
P  = matrix(c(1/2, 1/4, 1/4, 1/2), byrow = TRUE, nrow = K)
### define community label matrix Pi
distribution = c(1, 2);
l = sample(distribution, n, replace=TRUE, prob = c(1/2, 1/2))
Pi = matrix(0, n, 2) # label matrix
for (i in 1:n){
  Pi[i, l[i]] = 1
  }
### define the expectation of the parent graph's adjacency matrix
Omega = Pi %*% P %*% t(Pi)
### construct the parent graph G
G = matrix(runif(n*n, 0, 1), nrow = n)
G = G - Omega
temp = G
G[which(temp >0)] = 0
G[which(temp <=0)] = 1
diag(G) = 0
G[lower.tri(G)] = t(G)[lower.tri(G)];
### Sample Graphs Generation
### generate graph A from G
dA = matrix(rbinom(n*n, 1, s), nrow = n, ncol=n)
dA[lower.tri(dA)] = t(dA)[lower.tri(dA)]
A1 = G*dA
indA = sample(1:n, n, replace = FALSE)
labelA = l[indA]
A = A1[indA, indA]
### similarly, generate graph B from G
dB = matrix(rbinom(n*n, 1, s), nrow = n, ncol=n)
dB[lower.tri(dB)] = t(dB)[lower.tri(dB)]
B1 = G*dB
indB = sample(1:n, n, replace = FALSE)
labelB = l[indB]
B = B1[indB, indB]
DP_SBM(A = A, B = B, K = 2, fun = "EEpost", rep = 10, d = 3)

# }