Practical statistical network analysis
(with R and igraph)
Gábor Csárdi
csardi@rmki.kfki.hu
Department of Biophysics, KFKI Research Institute for Nuclear and Particle Physics of the
Hungarian Academy of Sciences, Budapest, Hungary
Currently at
Department of Medical Genetics,
University of Lausanne, Lausanne, Switzerland
What is a network (or graph)?
Practical statistical network analysis – WU Wien 2
What is a network (or graph)?
Practical statistical network analysis – WU Wien 3
What is a network (or graph)?
Practical statistical network analysis – WU Wien 4
What is a graph?
• Binary relation (=edges) between elements of a set (=vertices).
What is a graph?
• Binary relation (=edges) between elements of a set (=vertices).
• E.g.
vertices = {A, B, C, D, E}
edges = ({A, B}, {A, C}, {B, C}, {C, E}).
What is a graph?
• Binary relation (=edges) between elements of a set (=vertices).
• E.g.
vertices = {A, B, C, D, E}
edges = ({A, B}, {A, C}, {B, C}, {C, E}).
• It is “better” to draw it:
E
D
B
A
What is a graph?
• Binary relation (=edges) between elements of a set (=vertices).
• E.g.
vertices = {A, B, C, D, E}
edges = ({A, B}, {A, C}, {B, C}, {C, E}).
• It is “better” to draw it:
E B
D
A
C
C
E
B
A D
Practical statistical network analysis – WU Wien 5
Undirected and directed graphs
• If the pairs are unordered, then the graph is undirected:
B
A C
vertices = {A, B, C, D, E} E
edges = ({A, B}, {A, C}, {B, C}, {C, E}). D
Undirected and directed graphs
• If the pairs are unordered, then the graph is undirected:
B
A C
vertices = {A, B, C, D, E} E
edges = ({A, B}, {A, C}, {B, C}, {C, E}). D
• Otherwise it is directed:
B
A C
vertices = {A, B, C, D, E} E
edges = ((A, B), (A, C), (B, C), (C, E)). D
Practical statistical network analysis – WU Wien 6
The igraph “package”
• For classic graph theory and network science.
• Core functionality is implemented as a C library.
• High level interfaces from R and Python.
• GNU GPL.
• http://igraph.sf.net
Practical statistical network analysis – WU Wien 7
Vertex and edge ids
• Vertices are always numbered from zero (!).
• Numbering is continual, form 0 to |V | − 1.
Vertex and edge ids
• Vertices are always numbered from zero (!).
• Numbering is continual, form 0 to |V | − 1.
• We have to “translate” vertex names to ids:
V = {A, B, C, D, E}
E = ((A, B), (A, C), (B, C), (C, E)).
A = 0, B = 1, C = 2, D = 3, E = 4.
Vertex and edge ids
• Vertices are always numbered from zero (!).
• Numbering is continual, form 0 to |V | − 1.
• We have to “translate” vertex names to ids:
V = {A, B, C, D, E}
E = ((A, B), (A, C), (B, C), (C, E)).
A = 0, B = 1, C = 2, D = 3, E = 4.
1 > g <- graph( c(0,1, 0,2, 1,2, 2,4), n=5 )
Practical statistical network analysis – WU Wien 8
Creating igraph graphs
• igraph objects
Creating igraph graphs
• igraph objects
• print(), summary(), is.igraph()
Creating igraph graphs
• igraph objects
• print(), summary(), is.igraph()
• is.directed(), vcount(), ecount()
1 > g <- graph( c(0,1, 0,2, 1,2, 2,4), n=5 )
2 > g
3 Vertices: 5
4 Edges: 4
5 Directed: TRUE
6 Edges:
7
8 [0] 0 -> 1
9 [1] 0 -> 2
10 [2] 1 -> 2
11 [3] 2 -> 4
Practical statistical network analysis – WU Wien 9
Visualization
1 > g <- graph.tree(40, 4)
2 > plot(g)
3 > plot(g, layout=layout.circle)
Visualization
1 > g <- graph.tree(40, 4)
2 > plot(g)
3 > plot(g, layout=layout.circle)
1 # Force directed layouts
2 > plot(g, layout=layout.fruchterman.reingold)
3 > plot(g, layout=layout.graphopt)
4 > plot(g, layout=layout.kamada.kawai)
Visualization
1 > g <- graph.tree(40, 4)
2 > plot(g)
3 > plot(g, layout=layout.circle)
1 # Force directed layouts
2 > plot(g, layout=layout.fruchterman.reingold)
3 > plot(g, layout=layout.graphopt)
4 > plot(g, layout=layout.kamada.kawai)
1 # Interactive
2 > tkplot(g, layout=layout.kamada.kawai)
3 > l <- layout=layout.kamada.kawai(g)
Visualization
1 > g <- graph.tree(40, 4)
2 > plot(g)
3 > plot(g, layout=layout.circle)
1 # Force directed layouts
2 > plot(g, layout=layout.fruchterman.reingold)
3 > plot(g, layout=layout.graphopt)
4 > plot(g, layout=layout.kamada.kawai)
1 # Interactive
2 > tkplot(g, layout=layout.kamada.kawai)
3 > l <- layout=layout.kamada.kawai(g)
1 # 3D
2 > rglplot(g, layout=l)
Visualization
1 > g <- graph.tree(40, 4)
2 > plot(g)
3 > plot(g, layout=layout.circle)
1 # Force directed layouts
2 > plot(g, layout=layout.fruchterman.reingold)
3 > plot(g, layout=layout.graphopt)
4 > plot(g, layout=layout.kamada.kawai)
1 # Interactive
2 > tkplot(g, layout=layout.kamada.kawai)
3 > l <- layout=layout.kamada.kawai(g)
1 # 3D
2 > rglplot(g, layout=l)
1 # Visual properties
2 > plot(g, layout=l, vertex.color="cyan")
Practical statistical network analysis – WU Wien 10
Simple graphs
• igraph can handle multi-graphs:
V = {A, B, C, D, E}
E = ((AB), (AB), (AC), (BC), (CE)).
1 > g <- graph( c(0,1,0,1, 0,2, 1,2, 3,4), n=5 )
2 > g
3 Vertices: 5
4 Edges: 5
5 Directed: TRUE
6 Edges:
7
8 [0] 0 -> 1
9 [1] 0 -> 1
10 [2] 0 -> 2
11 [3] 1 -> 2
12 [4] 3 -> 4
Practical statistical network analysis – WU Wien 11
Simple graphs
• igraph can handle loop-edges:
V = {A, B, C, D, E}
E = ((AA), (AB), (AC), (BC), (CE)).
1 > g <- graph( c(0,0,0,1, 0,2, 1,2, 3,4), n=5 )
2 > g
3 Vertices: 5
4 Edges: 5
5 Directed: TRUE
6 Edges:
7
8 [0] 0 -> 0
9 [1] 0 -> 1
10 [2] 0 -> 2
11 [3] 1 -> 2
12 [4] 3 -> 4
Practical statistical network analysis – WU Wien 12
Creating (more) igraph graphs
1 el <- scan("lesmis.txt")
2 el <- matrix(el, byrow=TRUE, nc=2)
3 gmis <- graph.edgelist(el, dir=FALSE)
4 summary(gmis)
Practical statistical network analysis – WU Wien 13
Naming vertices
1 V(gmis)$name
2 g <- graph.ring(10)
3 V(g)$name <- sample(letters, vcount(g))
Practical statistical network analysis – WU Wien 14
Creating (more) igraph graphs
1 # A simple undirected graph
2 > g <- graph.formula( Alice-Bob-Cecil-Alice,
3 Daniel-Cecil-Eugene, Cecil-Gordon )
Creating (more) igraph graphs
1 # A simple undirected graph
2 > g <- graph.formula( Alice-Bob-Cecil-Alice,
3 Daniel-Cecil-Eugene, Cecil-Gordon )
1 # Another undirected graph, ":" notation
2 > g2 <- graph.formula( Alice-Bob:Cecil:Daniel,
3 Cecil:Daniel-Eugene:Gordon )
Creating (more) igraph graphs
1 # A simple undirected graph
2 > g <- graph.formula( Alice-Bob-Cecil-Alice,
3 Daniel-Cecil-Eugene, Cecil-Gordon )
1 # Another undirected graph, ":" notation
2 > g2 <- graph.formula( Alice-Bob:Cecil:Daniel,
3 Cecil:Daniel-Eugene:Gordon )
1 # A directed graph
2 > g3 <- graph.formula( Alice +-+ Bob --+ Cecil
3 +-- Daniel, Eugene --+ Gordon:Helen )
Creating (more) igraph graphs
1 # A simple undirected graph
2 > g <- graph.formula( Alice-Bob-Cecil-Alice,
3 Daniel-Cecil-Eugene, Cecil-Gordon )
1 # Another undirected graph, ":" notation
2 > g2 <- graph.formula( Alice-Bob:Cecil:Daniel,
3 Cecil:Daniel-Eugene:Gordon )
1 # A directed graph
2 > g3 <- graph.formula( Alice +-+ Bob --+ Cecil
3 +-- Daniel, Eugene --+ Gordon:Helen )
1 # A graph with isolate vertices
2 > g4 <- graph.formula( Alice -- Bob -- Daniel,
3 Cecil:Gordon, Helen )
Creating (more) igraph graphs
1 # A simple undirected graph
2 > g <- graph.formula( Alice-Bob-Cecil-Alice,
3 Daniel-Cecil-Eugene, Cecil-Gordon )
1 # Another undirected graph, ":" notation
2 > g2 <- graph.formula( Alice-Bob:Cecil:Daniel,
3 Cecil:Daniel-Eugene:Gordon )
1 # A directed graph
2 > g3 <- graph.formula( Alice +-+ Bob --+ Cecil
3 +-- Daniel, Eugene --+ Gordon:Helen )
1 # A graph with isolate vertices
2 > g4 <- graph.formula( Alice -- Bob -- Daniel,
3 Cecil:Gordon, Helen )
1 # "Arrows" can be arbitrarily long
2 > g5 <- graph.formula( Alice +---------+ Bob )
Practical statistical network analysis – WU Wien 15
Vertex/Edge sets, attributes
• Assigning attributes:
set/get.graph/vertex/edge.attribute.
Vertex/Edge sets, attributes
• Assigning attributes:
set/get.graph/vertex/edge.attribute.
• V(g) and E(g).
Vertex/Edge sets, attributes
• Assigning attributes:
set/get.graph/vertex/edge.attribute.
• V(g) and E(g).
• Smart indexing, e.g.
V(g)[color=="white"]
Vertex/Edge sets, attributes
• Assigning attributes:
set/get.graph/vertex/edge.attribute.
• V(g) and E(g).
• Smart indexing, e.g.
V(g)[color=="white"]
• Easy access of attributes:
1 > g <- erdos.renyi.game(100, 1/100)
2 > V(g)$color <- sample( c("red", "black"),
3 vcount(g), rep=TRUE)
4 > E(g)$color <- "grey"
5 > red <- V(g)[ color == "red" ]
6 > bl <- V(g)[ color == "black" ]
7 > E(g)[ red %--% red ]$color <- "red"
8 > E(g)[ bl %--% bl ]$color <- "black"
9 > plot(g, vertex.size=5, layout=
10 layout.fruchterman.reingold)
Practical statistical network analysis – WU Wien 16
Creating (even) more graphs
• E.g. from .csv files.
1 > traits <- read.csv("traits.csv", head=F)
2 > relations <- read.csv("relations.csv", head=F)
3 > orgnet <- graph.data.frame(relations)
4
5 > traits[,1] <- sapply(strsplit(as.character
6 (traits[,1]), split=" "), "[[", 1)
7 > idx <- match(V(orgnet)$name, traits[,1])
8 > V(orgnet)$gender <- as.character(traits[,3][idx])
9 > V(orgnet)$age <- traits[,2][idx]
10
11 > igraph.par("print.vertex.attributes", TRUE)
12 > orgnet
Practical statistical network analysis – WU Wien 17
Creating (even) more graphs
• From the web, e.g. Pajek files.
1 > karate <- read.graph("http://cneurocvs.rmki.kfki.hu/igraph/karate.net",
2 format="pajek")
3 > summary(karate)
4 Vertices: 34
5 Edges: 78
6 Directed: FALSE
7 No graph attributes.
8 No vertex attributes.
9 No edge attributes.
Practical statistical network analysis – WU Wien 18
Graph representation
• There is no best format, everything
depends on what kind of questions
one wants to ask.
Iannis
Esmeralda
Fabien
Alice
Diana
Helen
Cecil
Jennifer
Bob
Gigi
Practical statistical network analysis – WU Wien 19
Graph representation
• Adjacency matrix. Good for
questions like: is ’Alice’ connected
to ’Bob’ ?
Esmeralda
Jennifer
Fabien
Iannis
Diana
Helen
Cecil
Alice
Bob
Alice 0 1 0 0 1 0 Gigi
0 1 0 1
Bob 1 0 0 1 0 0 1 1 0 0
Cecil 0 0 0 1 0 1 1 0 0 0
Diana 0 1 1 0 1 0 1 1 1 0
Esmeralda 1 0 0 1 0 1 0 1 1 0
Fabien 0 0 1 0 1 0 0 1 0 0
Gigi 0 1 1 1 0 0 0 1 0 0
Helen 1 1 0 1 1 1 1 0 0 1
Iannis 0 0 0 1 1 0 0 0 0 0
Jennifer 1 0 0 0 0 0 0 1 0 0
Practical statistical network analysis – WU Wien 20
Graph representation
• Edge list. Not really good for
anything.
Alice Bob
Bob Diana
Cecil Diana
Alice Esmeralda
Diana Esmeralda
Cecil Fabien
Esmeralda Fabien
Bob Gigi
Cecil Gigi
Diana Gigi
Alice Helen
Bob Helen
Diana Helen
Esmeralda Helen
Fabien Helen
Gigi Helen
Diana Iannis
Esmeralda Iannis
Alice Jennifer
Helen Jennifer
Practical statistical network analysis – WU Wien 21
Graph representation
• Adjacency lists. GQ: who are the
neighbors of ’Alice’ ?
Alice Bob, Esmeralda, Helen, Jennifer
Bob Alice, Diana, Gigi, Helen
Cecil Diana, Fabien, Gigi
Diana Bob, Cecil, Esmeralda, Gigi, Helen, Iannis
Esmeralda Alice, Diana, Fabien, Helen, Iannis
Fabien Cecil, Esmeralda, Helen
Gigi Bob, Cecil, Diana, Helen
Helen Alice, Bob, Diana, Esmeralda, Fabien, Gigi, Jennifer
Iannis Diana, Esmeralda
Jennifer Alice, Helen
Practical statistical network analysis – WU Wien 22
Graph representation
• igraph. Flat data structures,
indexed edge lists. Easy to handle,
good for many kind of questions.
Practical statistical network analysis – WU Wien 23
Centrality in networks
• degree
Iannis
2
Esmeralda
5
Fabien
3
Alice
4
Diana
6 Helen
7
Cecil
3 Jennifer
2
Bob
Gigi 4
4
Practical statistical network analysis – WU Wien 24
Centrality in networks
• closeness
|V | − 1
Cv = P
i6=v dvi
Iannis
0.53
Esmeralda
0.69
Fabien
0.6
Alice
0.6
Diana
0.75 Helen
0.82
Cecil
0.53 Jennifer
0.5
Bob
Gigi 0.64
0.64
Practical statistical network analysis – WU Wien 25
Centrality in networks
• betweenness
X
Bv = givj /gij
i6=j,i6=v,j6=v
Iannis
0
Esmeralda
4.62
Fabien
1.45
Alice
1.67
Diana
6.76 Helen
10.1
Cecil
0.83 Jennifer
0
Bob
Gigi 1.12
1.45
Practical statistical network analysis – WU Wien 26
Centrality in networks
• eigenvector centrality
|V |
1X
Ev = Aiv Ei, Ax = λx
λ i=1
Iannis
0.36
Esmeralda
0.75
Fabien
0.49
Alice
0.63
Diana
0.88 Helen
1
Cecil
0.46 Jennifer
0.36
Bob
Gigi 0.71
0.68
Practical statistical network analysis – WU Wien 27
Centrality in networks
• page rank
|V |
1−d X
Ev = +d Aiv Ei
|V | i=1
Iannis
0.34
Esmeralda
0.74
Fabien
0.47
Alice
0.61
Diana
0.87 Helen
1
Cecil
0.47 Jennifer
0.34
Bob
Gigi 0.59
0.59
Practical statistical network analysis – WU Wien 28
Community structure in networks
• Organizing things, clustering items
to see the structure.
M. E. J. Newman, PNAS, 103, 8577–8582
Practical statistical network analysis – WU Wien 29
Community structure in networks
• How to define what is modular?
Many proposed definitions, here is
a popular one:
1 X
Q= [Avw −pvw ]δ(cv , cw ).
2|E| vw
Community structure in networks
• How to define what is modular?
Many proposed definitions, here is
a popular one:
1 X
Q= [Avw −pvw ]δ(cv , cw ).
2|E| vw
• Random graph null model:
1
pvw =p=
|V |(|V | − 1)
Community structure in networks
• How to define what is modular?
Many proposed definitions, here is
a popular one:
1 X
Q= [Avw −pvw ]δ(cv , cw ).
2|E| vw
• Random graph null model:
1
pvw =p=
|V |(|V | − 1)
• Degree sequence based null model:
kv kw
pvw =
2|E|
Practical statistical network analysis – WU Wien 30
Cohesive blocks
(Based on ‘Structural Cohesion and Embeddedness: a Hierarchical Concept of Social
Groups’ by J.Moody and D.White, Americal Sociological Review, 68, 103–127, 2003)
Definition 1: A collectivity is structurally cohesive to the extent that the social
relations of its members hold it together.
Cohesive blocks
(Based on ‘Structural Cohesion and Embeddedness: a Hierarchical Concept of Social
Groups’ by J.Moody and D.White, Americal Sociological Review, 68, 103–127, 2003)
Definition 1: A collectivity is structurally cohesive to the extent that the social
relations of its members hold it together.
Definition 2: A group is structurally cohesive to the extent that multiple
independent relational paths among all pairs of members hold it together.
Cohesive blocks
(Based on ‘Structural Cohesion and Embeddedness: a Hierarchical Concept of Social
Groups’ by J.Moody and D.White, Americal Sociological Review, 68, 103–127, 2003)
Definition 1: A collectivity is structurally cohesive to the extent that the social
relations of its members hold it together.
Definition 2: A group is structurally cohesive to the extent that multiple
independent relational paths among all pairs of members hold it together.
• Vertex-independent paths and vertex connectivity.
Cohesive blocks
(Based on ‘Structural Cohesion and Embeddedness: a Hierarchical Concept of Social
Groups’ by J.Moody and D.White, Americal Sociological Review, 68, 103–127, 2003)
Definition 1: A collectivity is structurally cohesive to the extent that the social
relations of its members hold it together.
Definition 2: A group is structurally cohesive to the extent that multiple
independent relational paths among all pairs of members hold it together.
• Vertex-independent paths and vertex connectivity.
• Vertex connectivity and network flows.
Practical statistical network analysis – WU Wien 31
Cohesive blocks
Practical statistical network analysis – WU Wien 32
Cohesive blocks
Practical statistical network analysis – WU Wien 33
Rapid prototyping
Weighted transitivity
A3ii
c(i) =
(A1A)ii
Rapid prototyping
Weighted transitivity
A3ii
c(i) =
(A1A)ii
3
Wii
cw (i) =
(WWmaxW)ii
Rapid prototyping
Weighted transitivity
A3ii
c(i) =
(A1A)ii
3
Wii
cw (i) =
(WWmaxW)ii
1 wtrans <- function(g) {
2 W <- get.adjacency(g, attr="weight")
3 WM <- matrix(max(W), nrow(W), ncol(W))
4 diag(WM) <- 0
5 diag( W %*% W %*% W ) /
6 diag( W %*% WM %*% W)
7 }
Practical statistical network analysis – WU Wien 34
Rapid prototyping
Clique percolation (Palla et
al., Nature 435, 814, 2005)
Practical statistical network analysis – WU Wien 35
. . . and the rest
• Cliques and independent vertex
sets.
• Network flows.
• Motifs, i.e. dyad and triad census.
• Random graph generators.
• Graph isomorphism.
• Vertex similarity measures,
topological sorting, spanning
trees, graph components, K-cores,
transitivity or clustering coefficient.
• etc.
• C-level: rich data type library.
Practical statistical network analysis – WU Wien 36
Acknowledgement
Tamás Nepusz
All the people who contributed code, sent bug reports, suggestions
The R project
Hungarian Academy of Sciences
The OSS community in general
Practical statistical network analysis – WU Wien 37
