EE_SBM {GMPro}

Edge exploited 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 a certain graph matching method to match different communities.

Usage

EE_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, indicating the number of communities in A and B.

fun

A graph matching algorithm. Choices include DPmatching and EEpost.

rep

Optional parameter if EEpost is the initial graph matching algorithm.

tau

Optional parameter if EEpost is the initial graph matching algorithm. The default value is rep/10.

d

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

Details

EE_SBM can be regarded as a post processing version of DP_SBM using EEpost.

Value

match

A vector containing matching results.

FLAG

An indicator vector indicating whether the matching result is converged, 0 for No and 1 for Yes.

Examples

### 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]
EE_SBM(A = A, B = B, K = 2, fun = "EEpost", rep = 10, d = 3)