DP_SBM: Degree profile graph matching with community detection.

In GMPro: Graph Matching with Degree Profiles

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.

Details

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

Value

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

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

GMPro documentation built on July 1, 2020, 6:05 p.m.