global.efficiency: Graph efficiency

In brainwaver: Basic wavelet analysis of multivariate time series with a visualisation and parametrisation using graph theory.

Description

Computes various measures of efficiency of a graph using the definition given by (Latora, 2001 and 2003)

Usage

global.efficiency(adj.mat, weight.mat)
local.efficiency(adj.mat, weight.mat)
global.cost(adj.mat, weight.mat)
cost.evaluator(x)

Arguments

adj.mat	adjacency matrix of the graph
weight.mat	weighted matrix associated to the graph
x	real

Details

Formula for the global efficiency :

E_global = 1/N(N-1) sum_{i <= j in G} 1/L_{i,j}

where L_{i,j} is the minimum path length between each pair of nodes, and G the graph.

Formula for the nodal efficiency for the node i:

E_nodal(i) = 1/(N-1) sum_{j in G} 1/L_{i,j}

Formula for the local efficiency for node i:

E_local = 1/N_{G{_i}}(N_{G{_i}}-1) sum_{j,k in G_i} 1/L_{j,k}

where G_i is the set of nodes which are nearest-neighbours of the ith node, i.e., the nodes in G_i are each directly connected by a single edge to the index node i and N_{G{_i}} is the number of nodes in the sub-graph G_i.

The computation of the cost requires the definition of an internal function, called cost.evaluator. For the moment, the cost.evaluator is the identity. Refer to Latora (2001) for the exact definition and usage of this function.

Value

global.efficiency$nodal.eff	vector containing the nodal efficiency for each node of the graph (equal to the inverse of the harmonic mean of the path length, when two nodes are disconnected, the path length is taken to be infinity so the inverse is 0)
global.efficiency$eff	real corresponding to the mean of the nodal efficiency for the whole graph
local.efficiency$loc.eff	vector containing the local efficiency for each node of the graph (see details for the exact fomula)
global.efficiency$eff	real corresponding to the mean of the local efficiency for the whole graph
global.cost	real corresponding to the mean of the cost for the whole graph

Note

only in version 2 and higher

Author(s)

S. Achard

References

V. Latora, M. Marchiori (2001) Efficient Behavior of Small-World Networks. Phys. Rev. Lett., Vol. 87, N. 19, pages 1-4.

V. Latora, and M. Marchiori (2003) Economic Small-World Behavior in Weighted Networks. Europ. Phys. Journ. B, Vol. 32, pages 249-263.

S. Achard, R. Salvador, B. Whitcher, J. Suckling, Ed Bullmore (2006) A Resilient, Low-Frequency, Small-World Human Brain Functional Network with Highly Connected Association Cortical Hubs. Journal of Neuroscience, Vol. 26, N. 1, pages 63-72.

See Also

const.adj.list, small.world

Examples

data(brain)
brain<-as.matrix(brain)

# WARNING : To process only the first five regions
brain<-brain[,1:5]




n.regions<-dim(brain)[2]

#Construction of the correlation matrices for each level of the wavelet decomposition
wave.cor.list<-const.cor.list(brain, method = "modwt" ,wf = "la8", n.levels = 6, 
                               boundary = "periodic", p.corr = 0.975)


sup.seq<-((1:10)/10) #sequence of the correlation threshold 
nmax<-length(sup.seq)
Eglob<-matrix(0,6,nmax)
Eloc<-matrix(0,6,nmax)
Cost<-matrix(0,6,nmax)

n.levels<-6

#For each value of the correlation thrashold
for(i in 1:nmax){
n.sup<-sup.seq[i]

#Construction of the adjacency matrices associated to each level of the wavelet decomposition
wave.adj.list<-const.adj.list(wave.cor.list, sup = n.sup)


#For each level of the wavelet decomposition
for(j in 1:n.levels){

Eglob.brain<-global.efficiency(wave.adj.list[[j]],
			weight.mat=matrix(1,n.regions,n.regions))
Eglob[j,i]<-Eglob.brain$eff

Eloc.brain<-local.efficiency(wave.adj.list[[j]],
				weight.mat=matrix(1,n.regions,n.regions))
Eloc[j,i]<-Eloc.brain$eff

Cost.brain<-global.cost(wave.adj.list[[j]],
				weight.mat=matrix(1,n.regions,n.regions))
Cost[j,i]<-Cost.brain

}}


plot(sup.seq,(1:nmax)/2,type='n',xlab='Correlation threshold, R',ylab='Global efficiency',
     cex.axis=2,cex.lab=2,xlim=c(0,1),ylim=c(0,1))


for(i in 1:n.levels){
lines(sup.seq,Eglob[i,],type='l',col=i,lwd=2)
}
legend(x="topright",legend=c("Level 1","Level 2","Level 3","Level 4",
				"Level 5","Level 6"),fill=TRUE,col=(1:n.levels),lwd=2)

brainwaver documentation built on May 2, 2019, 10:23 a.m.