Set the random number generator to make the experiments repeatable

set.seed(1234)

library(igraph)
## 
## Attaching package: 'igraph'
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## The following object is masked from 'package:base':
## 
##     union
source("http://michael.hahsler.net/SMU/ScientificCompR/code/map.R")

Create a random graph

g <-erdos.renyi.game(30, 3/30)
summary(g)
## IGRAPH U--- 30 53 -- Erdos renyi (gnp) graph
## + attr: name (g/c), type (g/c), loops (g/l), p (g/n)

Plot graphs

plot(g)

Plot with an externally created layout

layout <-layout.fruchterman.reingold(g)
plot(g, layout=layout)

Interactive plot

tkplot(g)
## [1] 1

Inspect vertex degree and use the degree for vertex size

degree(g)
##  [1] 5 2 0 4 2 3 0 6 1 2 6 2 5 3 6 5 3 4 7 3 2 4 3 3 2 6 3 4 5 5
hist(degree(g))

plot(g, layout=layout, vertex.size=map(degree(g),c(1,20)))

Number of paths between vertex 1 and 2

edge.disjoint.paths(g, 1, 2)
## [1] 2

Betweenness centrality - number of geodesics (shortest paths) going through a vertex or an edge

betweenness(g)
##  [1] 35.964286  1.952381  0.000000 19.983333  1.825000 12.400000  0.000000
##  [8] 33.283333  0.000000  2.700000 46.046429  4.850000 33.235714  9.176190
## [15] 45.428571 45.423810  8.854762 31.033333 61.590476 14.304762  3.783333
## [22] 16.188095  7.985714  9.200000  1.866667 47.700000  9.350000 15.059524
## [29] 15.392857 22.421429
edge.betweenness(g)
##  [1] 14.391667 12.391667 20.366667 23.533333 22.252381 17.083333 12.033333
##  [8] 18.583333 21.633333 22.411905 18.016667 22.854762 27.000000 31.907143
## [15] 21.952381 21.750000 18.258333 22.653571 28.188095 27.269048 10.835714
## [22] 17.504762 22.519048 13.183333 11.019048 12.654762 18.909524 11.319048
## [29] 17.854762  8.952381 18.592857 17.361905 21.453571 20.492857 26.552381
## [36] 17.969048 23.247619 17.333333 15.200000 13.166667 13.491667 15.217857
## [43] 15.666667 12.742857  7.700000 11.200000 13.800000 12.684524 13.834524
## [50] 12.826190 19.409524 13.371429 12.401190
plot(g, layout=layout,
  vertex.size=map(betweenness(g),c(1,15)),
  edge.width=map(edge.betweenness(g), c(1,10)))

Diameter of graph - Length of the longest geodesic path

diameter(g)
## [1] 5
get.diameter(g)
## + 6/30 vertices:
## [1]  9 18 16  6 27 12

Maximal independent vertex sets

independence.number(g)
## [1] 15
# mark the first maximal independent vertex set red
col <- rep("blue",length(V(g)))
col[maximal.independent.vertex.sets(g)[[1]]] <- "red"
plot(g, layout=layout, vertex.color=col)

Find connected components

cl <- clusters(g)
cl
## $membership
##  [1] 1 1 2 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## 
## $csize
## [1] 28  1  1
## 
## $no
## [1] 3
plot(g, layout=layout, vertex.color=cl$membership+1L)

Get connected components

dg <- decompose.graph(g)
length(dg)
## [1] 3
plot(dg[[1]])

plot(dg[[2]])

Max-flow between vertices 1 and 2

graph.maxflow(g, 1, 2)
## $value
## [1] 2
## 
## $flow
##  [1]  0  0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0
## [24]  0  0  0  0  0  1 -1  0  0  1  0  0 -1  0  0  0  0  0  0  0  0  0  0
## [47]  0  0  0  0  0  0  0
## 
## $cut
## [1] 15 30
## 
## $partition1
## + 29/30 vertices:
##  [1]  1  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
## [24] 25 26 27 28 29 30
## 
## $partition2
## + 1/30 vertex:
## [1] 2
## 
## $stats
## $stats$nopush
## [1] 30
## 
## $stats$norelabel
## [1] 13
## 
## $stats$nogap
## [1] 3
## 
## $stats$nogapnodes
## [1] 24
## 
## $stats$nobfs
## [1] 1

Min cut (of the first connected component)

graph.mincut(dg[[1]], value.only=FALSE)
## $value
## [1] 1
## 
## $cut
## + 1/53 edge:
## [1] 7--16
## 
## $partition1
## + 1/28 vertex:
## [1] 7
## 
## $partition2
## + 27/28 vertices:
##  [1]  1  2  3  4  5  6  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
## [24] 25 26 27 28
col <- rep("blue", length(V(dg[[1]])))
col[graph.mincut(dg[[1]], value.only=FALSE)[["partition2"]]] <- "red"
plot(dg[[1]], vertex.color=col)

Find neighborhood of vertices

gn <- graph.neighborhood(g, order = 1)
plot(gn[[1]])

plot(gn[[2]])

Find cliques

mc <- maximal.cliques(g)
length(mc)
## [1] 48

click size

sapply(mc, length)
##  [1] 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 2
## [36] 2 2 2 2 2 2 2 2 3 3 2 2 2
col <- rep("blue", length(V(g)))

plot the largest (last) click

col[mc[[length(mc)]]] <- "red"

plot(g, layout=layout, vertex.color=col)

Large graph (social networks)

g <- barabasi.game(1000, power=1)
layout <- layout.fruchterman.reingold(g)
plot(g, layout=layout, vertex.size=2,
  vertex.label=NA, edge.arrow.size=.2)

Page Rank

pr <- page.rank(g)$vector
plot(g, layout=layout, vertex.size=map(pr, c(1,20)),
  vertex.label=NA, edge.arrow.size=.2)

Eigenvector centrality

ec <- evcent(g)$vector
plot(g, layout=layout, vertex.size=map(ec, c(1,20)), vertex.label=NA, edge.arrow.size=.2)

Kleinberg’s hub and authority scores

auth <- authority.score(g)$vector
hub <- hub.score(g)$vector
plot(g, layout=layout, vertex.size=map(hub, c(1,5)), vertex.label=NA, edge.arrow.size=.2)

plot(g, layout=layout, vertex.size=map(auth, c(1,20)), vertex.label=NA, edge.arrow.size=.2)

Community detection (betweenness)

eb <- edge.betweenness.community(g)

create 10 communities

membership <- cut_at(eb, no = 10)
plot(g,
  vertex.color= rainbow(10, .8, .8, alpha=.8)[membership],
  vertex.size=5, layout=layout,  vertex.label=NA,
  edge.arrow.size=.2)

Random walk

eb <- walktrap.community(g)

create 10 communities

membership <- cut_at(eb, no = 10)
plot(g,
  vertex.color= rainbow(10, .8, .8, alpha=.8)[membership],
  vertex.size=5, layout=layout,  vertex.label=NA,
  edge.arrow.size=.2)