LOE: LOE for a unweighted Graph.

Description Usage Arguments Value Author(s) Examples

Description

Performs LOE for a given unweighted grah.

Usage

1
2
LOE(ADM, p=2, c=0.1,eps= 1e-5,maxit =1000,method=c("BFGS","SD","MM"),
iniX = "auto",report=100,DEL=1,H=0.5)

Arguments

ADM

The adjacency matrix.

p

Number of dimensions.

c

Scale parameter which only takes strictly positive value.

eps

Convergence criterion for the majorization algorithm or the steepest descent algorithm.

maxit

Maximum number of iteretions.

method

If "BFGS", then the BFGS method is used for optimizing the stress function. If "SD", then the steepest descent method is used. If "MM", then the majorization minimization algortihm is used.

iniX

Matrix with starting values for embedding (optional). If "auto", then Laplacian eigenmaps is used as a starting value.

report

The frequency of reports. Defaults to every 100 iterations.

DEL

The initial step size in the steepest descent algorithm. Defaults to 1.

H

The rate parameter of the backtracking line search in the steepest descent algorithm. This parameter only takes value in (0,1). Defaults to 0.5.

Value

LOE returns a list with components:

X

The best corrdinate matrix with p columns whose rows give the coordinates of the vertexes.

str

If method is "BFGS", then the value of the stress function of LOE corresponding to X is returned. If "SD" or "MM", then the vector of values on each iteration is returned.

Author(s)

Yoshikazu Terada

Examples

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#################
#Realizable case#
#################
library(igraph)
###############################
#Create a toy data
x <- seq(-5,5,by=1)
y <- seq(1,6,by=1)
hx1 <- seq(-3.5,-1.5,by=0.5)
hx2 <- seq(1.5,3.5,by=0.5)
hy <- seq(2.5,4.5,by=0.5)
D1 <- matrix(0,66,2)
for(i in 1:11){
	for(j in 1:6){
		D1[i+11*(j-1),] <- c(x[i],y[j])
	}
}
D2n <- matrix(0,25,2)
D2p <- matrix(0,25,2)
for(i in 1:5){
	for(j in 1:5){
		D2n[i+5*(j-1),] <- c(hx1[i],hy[j])
		D2p[i+5*(j-1),] <- c(hx2[i],hy[j])
	}
}
D2n <- D2n[-c(7,9,17,19),]
D2p <- D2p[-c(7,9,17,19),]
Data <- rbind(D1,D2n,D2p)
Data <- scale(Data[order(Data[,1]),], scale=FALSE)
N <- nrow(Data)
#Visualization of the original data
plot(Data,pch=20,xlab="",ylab="",cex=1,col=rainbow(N,start=.7,end=.9),
xlim=c(-7,7),ylim=c(-7,7),main="Original data")

#Creating a k-NN graph based on Data
DM <- as.matrix(dist(Data))
ADM <- make.kNNG(DM,k=25)

#plot of the adjacency matrix
AADM <- ADM
diag(AADM) <- NA
image(AADM[N:1,],col=topo.colors(3),ann=FALSE,axes=FALSE)

#Apply some graph embedding methods
LE <-spec.emb(A=ADM,2,norm=FALSE)
result.LOE <- LOE(ADM=ADM,p=2,c=0.1,method="BFGS",report=1000,iniX=LE)

#Procrustes transform
library(vegan)
LOEX <- procrustes(X=Data,Y=result.LOE$X)$Yrot
plot(LOEX,pch=20,xlab="",ylab="",cex=1,col=rainbow(N,start=.7,end=.9),
xlim=c(-7,7),ylim=c(-7,7),main="LOE")
###############################

#############
#This function provide appropriate vectors of xlim and ylim
#for given embedding matrix X.
#############
make.lim <- function(X){
			mima <- matrix(0, 2,2)
			mima[,1] <- apply(X, 2, min)
			mima[,2] <- apply(X, 2, max)
			han <- mima[,2] - mima[,1]
			cent <-  (mima[,2] + mima[,1])/2
			tmpr <- max(han)+max(han)*0.05
			for(s in 1:2){
				mima[s,] <- c(cent[s]-tmpr/2,cent[s]+tmpr/2)
			}
			return(mima)
		}
##############################
#Standered graph-drawing task#
##############################
###############################
ADM <- as.matrix( get.adjacency(graph.famous("Thomassen")) )
TG <- graph.adjacency(ADM)

#Apply some graph embedding methods
LE <-spec.emb(A=ADM,2,norm=FALSE)
KK <- layout.kamada.kawai(TG,maxiter=1000,start=LE)
FR <- layout.fruchterman.reingold(TG,maxiter=1000,start=LE)
result.LOE <- LOE(ADM=ADM,p=2,c=0.1,method="MM",report=1000,maxit=2000)


#Visualization of embeddings
par(mfrow=c(2,3),oma = c(0, 0, 4, 0))
#plot of the adjacency matrix
	AADM <- ADM
	N <- nrow(AADM)
	diag(AADM) <- NA
	image(AADM[N:1,],col=topo.colors(3),ann=FALSE,axes=FALSE)
#plot of Laplacian eigenmaps
	tmplim <- make.lim(LE)
	vsize <- (tmplim[1,2] -tmplim[1,1])*4
	plot(TG, layout=LE, main="Laplacian eigenmaps",
		vertex.size=vsize,vertex.color="blue",vertex.label.color="white",vertex.label=NA,
		edge.arrow.size=0.1,xlim=tmplim[1,],ylim=tmplim[2,],axes=TRUE,rescale=FALSE)
#plot of Kamada and Kawai
	tmplim <- make.lim(KK)
	vsize <- (tmplim[1,2] -tmplim[1,1])*4
	plot(TG, layout=KK, main="Kamada and Kawai",
		vertex.size=vsize,vertex.color="blue",vertex.label.color="white",vertex.label=NA,
		edge.arrow.size=0.1,xlim=tmplim[1,],ylim=tmplim[2,],axes=TRUE,rescale=FALSE)
#plot of Fruchterman Reingold
	tmplim <- make.lim(FR)
	vsize <- (tmplim[1,2] -tmplim[1,1])*4
	plot(TG, layout=FR, main="Fruchterman Reingold",
		vertex.size=vsize,vertex.color="blue",vertex.label.color="white",vertex.label=NA,
		edge.arrow.size=0.1,xlim=tmplim[1,],ylim=tmplim[2,],axes=TRUE,rescale=FALSE)
#plot of LOE
	tmplim <- make.lim(result.LOE$X)
	vsize <- (tmplim[1,2] -tmplim[1,1])*4
	plot(TG, layout=result.LOE$X, main="LOE",
		vertex.size=vsize,vertex.color="blue",vertex.label.color="white",vertex.label=NA,
		edge.arrow.size=0.1,xlim=tmplim[1,],ylim=tmplim[2,],axes=TRUE,rescale=FALSE)
	plot(result.LOE$str,type="l",xlab="Number of iter.", ylab="Stress")
#Make title
	mtext(side = 3, line=1, outer=TRUE, text = "Thomassen", cex=2)
###############################

Example output

Loading required package: MASS

Attaching package: 'igraph'

The following objects are masked from 'package:stats':

    decompose, spectrum

The following object is masked from 'package:base':

    union

initial  value 590.780031 
final  value 0.000000 
converged
Loading required package: permute

Attaching package: 'permute'

The following object is masked from 'package:igraph':

    permute

Loading required package: lattice
This is vegan 2.4-4

Attaching package: 'vegan'

The following object is masked from 'package:igraph':

    diversity

initial stress= 7.531723 
iter 1000 stress = 3.078888 
iter (final) 1494 stress = 3.068628 
converged

loe documentation built on May 29, 2017, 4:58 p.m.