Tutorial on graphs

First load the packages into the R session

library(igraph)
library(brainwaver)

Graph representations

Vertex and edges

A simple example of graph:

g <- graph.empty(directed=FALSE) + vertices(letters[1:10])
g <- g + path(letters[1:10], letters[1], color="grey")
g <- g + edges(sample(V(g), 10, replace=TRUE), color="red")

g$layout <- layout.circle
plot(g)

plot of chunk unnamed-chunk-2

Question 1: Describe the obtained graph in terms of vertex, edges… ?
 V(g) ### vertices
## + 10/10 vertices, named:
##  [1] a b c d e f g h i j
 E(g) ### edges
## + 15/15 edges (vertex names):
##  [1] a--b b--c c--d d--e e--f f--g g--h h--i i--j a--j b--j c--e g--j a--f
## [15] d--g
 get.adjacency(g) ### adjacency matrix
## 10 x 10 sparse Matrix of class "dgCMatrix"
##    [[ suppressing 10 column names 'a', 'b', 'c' ... ]]
##                      
## a . 1 . . . 1 . . . 1
## b 1 . 1 . . . . . . 1
## c . 1 . 1 1 . . . . .
## d . . 1 . 1 . 1 . . .
## e . . 1 1 . 1 . . . .
## f 1 . . . 1 . 1 . . .
## g . . . 1 . 1 . 1 . 1
## h . . . . . . 1 . 1 .
## i . . . . . . . 1 . 1
## j 1 1 . . . . 1 . 1 .
Question 2: Propose a new graph with 9 edges between \(a\) and the other vertices of the graph.
g <- graph.empty(directed=FALSE) + vertices(letters[1:10])
g <- g + path(letters[1:10], letters[1], color="grey")
new_edges<-array(c(rep("a",9),letters[2:10]),dim=c(9,2))
g <- g + edges(as.vector(t(new_edges)), color="red")
g$layout <- layout.circle
plot(g)

plot of chunk unnamed-chunk-4

Question 3: Propose a new simple undirected graph with 90 vertices and 400 edges.
g <- graph.empty(directed=FALSE) + vertices(1:90)
g <- g + path(1:90, 1, color="grey")
g <- g + edges(sample(V(g), 620, replace=TRUE), color="red")
g$layout <- layout.circle
plot(g)

plot of chunk unnamed-chunk-5

Other functions can be used to construct graphs:

# graph
# graph.adjacency
# graph.adjlist
# graph.edgelist

Graphical representation

The package igraph proposes various ways to plot the graphs when no coordinates are specified for the position of vertices.

g <- graph.lattice( c(3,3) )
plot(g,layout=layout.grid)

plot of chunk unnamed-chunk-7

plot(g,layout=layout.circle)

plot of chunk unnamed-chunk-7

plot(g,layout=layout.random)

plot of chunk unnamed-chunk-7

plot(g,layout=layout.star)

plot of chunk unnamed-chunk-7

plot(g,layout=layout.auto)

plot of chunk unnamed-chunk-7

Question 2: Simulate another possible graph and comment the results of the layout.
g <- graph.empty(directed=FALSE) + vertices(letters[1:10])
g <- g + path(letters[1:10], letters[1], color="grey")
new_edges<-array(c(rep("a",9),letters[2:10]),dim=c(9,2))
g <- g + edges(as.vector(t(new_edges)), color="red")

g$layout <- layout.star
plot(g)

plot of chunk unnamed-chunk-8

Simulation of random or lattice graphs

The function graph.lattice simulates a lattice graph and the function random.graph.game simulates a random graph. Some examples:

Question 1: Simulate a lattice graph by fixing the number of neighbours to be equal to 3.
graph.lattice(length=50, dim=1, nei=3)
## IGRAPH U--- 50 144 -- Lattice graph
## + attr: name (g/c), dimvector (g/n), nei (g/n), mutual (g/l),
## | circular (g/l)
## + edges:
##  [1]  1-- 2  2-- 3  3-- 4  4-- 5  5-- 6  6-- 7  7-- 8  8-- 9  9--10 10--11
## [11] 11--12 12--13 13--14 14--15 15--16 16--17 17--18 18--19 19--20 20--21
## [21] 21--22 22--23 23--24 24--25 25--26 26--27 27--28 28--29 29--30 30--31
## [31] 31--32 32--33 33--34 34--35 35--36 36--37 37--38 38--39 39--40 40--41
## [41] 41--42 42--43 43--44 44--45 45--46 46--47 47--48 48--49 49--50  1-- 3
## [51]  1-- 4  2-- 4  2-- 5  3-- 5  3-- 6  4-- 6  4-- 7  5-- 7  5-- 8  6-- 8
## [61]  6-- 9  7-- 9  7--10  8--10  8--11  9--11  9--12 10--12 10--13 11--13
## + ... omitted several edges
Question 2: Simulate a random graph by fixing the number of neighbours to be equal to 3.
random.graph.game(n=50, p.or.m=144, type='gnm')
## IGRAPH U--- 50 144 -- Erdos renyi (gnm) graph
## + attr: name (g/c), type (g/c), loops (g/l), m (g/n)
## + edges:
##  [1]  2-- 4  4-- 5  4-- 9  2--10  8--11  9--11  5--12  2--14  9--14  3--15
## [11]  9--16 12--16  9--18 11--18 15--18  9--19 12--19  3--20 16--20 10--21
## [21] 16--21  5--22 16--22  9--23 14--23 17--23  4--24 15--24  7--25 14--25
## [31] 16--25 17--25  1--26  5--26 24--26  4--27 12--27 15--27 17--27 18--27
## [41] 22--27 13--28 15--28 20--28 21--28  7--29  9--29  1--30  6--30  8--30
## [51] 13--30 20--30 24--30 26--30  4--31  6--31 11--31 26--31 30--31 16--32
## [61] 28--32  3--33 12--33 15--33 22--34 10--35 14--35  2--36 31--36 14--37
## [71] 18--37 20--37 22--37 36--37  4--38 20--38 24--38 26--38 25--39 32--39
## + ... omitted several edges

Graph metrics

This part is dedicated to the study of the topology of the graphs. A list of functions in igraph to extract topological measures is given below:

# degree
# diameter
# shortest.paths
# modularity
# graph.laplacian
Question 1: Write a function to define global and local efficiency.
Eglob_func<-function(G){
N<-length(V(G))
Eglob<-rep(0,N)
L<-shortest.paths(G)
if(N>1){
for(i in 1:N){
tmp<-L[i,-i]
Eglob[i]<-sum(1/tmp)
}
}else{
Eglob[i]<-0
}
Eglob<-Eglob/(N-1)

return(Eglob)
}
Eloc_func<-function(G){
N<-length(V(G))
Eloc<-rep(0,N)
for(i in 1:N){
Eloc[i]<-mean(Eglob_func(induced.subgraph(G,neighbors(G,V(G)[i]))))
}
return(Eloc)
}
Question 2: Write a function to compute the clustering as defined by Watts and Strogatz.
clustering<-function(G){
N<-length(V(G))
clustering<-rep(0,N)
for(i in 1:N){
G_i<-induced.subgraph(G,neighbors(G,V(G)[i]))
k_i<-length(V(G_i))
clustering[i]<-length(E(G_i))/(k_i*(k_i-1)/2)
}
return(clustering)
}
Question 3: Try these functions with a lattice or random graph with 100 vertices.

Generative models for graphs

Small-world model

The small-world model is a combination of good properties of the lattice graph and the random graph. The corresponding igraph function is called watts.strogatz.game.

Question 1: Using the function rewire_edges, try to simulate the small-world model of Watts and Strogatz.
Question 2: Reproduce the plot showing the evolution of minimum path length and clustering with the probability of rewiring.
n<-c(0.0001,0.001,0.01,0.1,1)
graph.lattice(length=200, dim=1, nei=6)->g.lattice
L0.lattice<-round(mean(average.path.length(g.lattice)),2)
C0.lattice<-round(mean(clustering(g.lattice)),2)

vec_L<-rep(0,length(n))
vec_C<-rep(0,length(n))


# par(mfrow=c(1,6))
g<-g.lattice
# plot(g,layout=layout.circle,main='regular')
for(i in 1:length(n)){

gg<-rewire(g,with=each_edge(p=n[i],loops = FALSE))
L_g<-round(mean(average.path.length(gg))/L0.lattice,2)
C_g<-round(mean(clustering(gg))/C0.lattice,2)
vec_L[i]<-L_g
vec_C[i]<-C_g

# plot(gg,layout=layout.circle,main=paste('L = ',L_g,'-- C = ',C_g,sep=''))

}

plot(log(n),vec_L,pch=16,ylim=c(0,1),xaxt='n',xlab='n')
points(log(n),vec_C,pch=4)
axis(1,at=log(n),labels=n)

plot of chunk unnamed-chunk-15

Barábasi-Albert model

The Barabási-Albert model tries to reproduce a degree distribution as a power law as observed in a lot of different networks. The model is based on a preferential attachement procedure. The corresponding function in igraph is ba.game.

Question 1: Try the function to simulate scale-free graphs. Verify the power law of the degree distribution.
Question 2: Use the different graph metrics to characterise these graphs.

Summary

You have learned to characterize the topology of the graphs using various metrics and you can now simulate different types of graphs. Using graphs with 100 vertices and 400 edges, the objective is to summarize the topology of the various obtained graphs using different graph metrics.

Question: Write a table to summarize the results for the comparisons of the graph metrics computed with the 4 different generative models.

Sparse or not so sparse graphs

We have seen from the beginning that the two crucial parameters for a graph is the number of vertices, the number of edges. We also studied different ways to add the edges in the graph, but we may wonder how the different metrics are sensitive to these different constructions of the graphs.

Question 1: Compute the different metrics using various generative models with a small number of edges in comparison to the total possible number of edges in the graph. You can fix the number of vertices to be equal to 100.
Question 2: Try to do the same but with nearly complete graphs.
Question 3: Comment the results, what can you suggest to practionners when they try to compare graphs.

What's happening on real data?

The brain is modelled as a graph with anatomical regions as nodes and connections between pairs of regions as edges.

Two data sets available

Young and elderly

This data sets is published in (Achard et al. PLoS Comp. Biol. 2007). It consists of 15 young subjects and 11 elderly subjects. The graphs contain 90 nodes and 400 edges.

Coma patients

This data sets is published in (Achard et al. PNAS. 2012). It consists of 20 healthy controls and 17 coma patients. The graphs contain 90 nodes and 400 edges.

Visualisation of a graph with spatial coordinate

source('http://www.gipsa-lab.grenoble-inp.fr/~sophie.achard/Tutorial_brainwaver/plot_brain_graphs.R')
adj.mat<-read.table('http://www.gipsa-lab.grenoble-inp.fr/~sophie.achard/Tutorial_brainwaver/Data/Young_Old/Adj_mat/adj_mat_90_wave_scale_3_ts_Young_dat21P.txt_cost_400.txt')
adj.mat<-as.matrix(adj.mat)
plot_brain_graphs(adj.mat,file_coord='coord_file_AAL.tt',view='transverse')

plot of chunk unnamed-chunk-16

A combination of the classical three views together

 par(mfrow=c(2,2))
 plot_brain_graphs(adj.mat,file_coord='http://www.gipsa-lab.grenoble-inp.fr/~sophie.achard/Tutorial_brainwaver/coord_file_AAL.tt',view='sagittal')
 plot_brain_graphs(adj.mat,file_coord='http://www.gipsa-lab.grenoble-inp.fr/~sophie.achard/Tutorial_brainwaver/coord_file_AAL.tt',view='transverse')
 plot_brain_graphs(adj.mat,file_coord='http://www.gipsa-lab.grenoble-inp.fr/~sophie.achard/Tutorial_brainwaver/coord_file_AAL.tt',view='frontal')

plot of chunk unnamed-chunk-17

In order to extract the modularity of a graph, we use fastgreedy.community.

graph.adjacency(adj.mat,mode='undirected')->graph.brain
wc <- fastgreedy.community(graph.brain)
coord<-read.table('http://www.gipsa-lab.grenoble-inp.fr/~sophie.achard/Tutorial_brainwaver/coord_file_AAL.tt',header=F)
plot(wc, graph.brain, layout=as.matrix(coord[,3:4]),rescale=F,xlim=c(0,100),ylim=c(0,100),vertex.label=NA)

plot of chunk unnamed-chunk-18

Another way to represent the modules

coord<-read.table('http://www.gipsa-lab.grenoble-inp.fr/~sophie.achard/Tutorial_brainwaver/coord_file_AAL.tt',header=F)

     comps <- wc$membership ##clusters(graph.brain)$membership
     colbar <- rainbow(max(comps)+1)
     V(graph.brain)$color <- colbar[comps+1]
     plot(graph.brain, layout=layout.fruchterman.reingold, vertex.size=5, vertex.label=NA)