The igraph library

Screenshots

The Fruchterman-Reingold layout algorithm

Illustration

The Fruchterman-Reingold is a robust algorithm to generate visually appealing placements for vertices. It works well on unconnected graphs and can be used up to a couple of thousand vertices.

The frgraphs() function is available here.

library(igraph)

source("frgraphs.R")
graphs <- frgraphs()
lay <- lapply(graphs, layout.fruchterman.reingold, niter=3000)

# png(file="frplots.png")
par(mai=c(0,0,0,0))
layout(matrix(1:16, nr=4, byrow=TRUE))
layout.show(16)
for (i in seq(along=graphs)) {
  plot(graphs[[i]], layout=lay[[i]],
       vertex.label=NA, vertex.size=13, edge.color="black",
       vertex.color="red")
}
# dev.off()



The tkplot editor of the R package

Illustration

The igraph R package features an interactive graph layout editor for small graphs. It is a little toy only, but can be useful if you want to adjust the layout of small graphs. Here is how we generated this picture:

library(igraph)
g <- read.graph("karate.net", format="pajek")

cs <- leading.eigenvector.community(g, steps=1)
V(g)$color <- ifelse(cs$membership==1, "lightblue", "green")

scale <- function(v, a, b) {
  v <- v-min(v) ; v <- v/max(v) ; v <- v * (b-a) ; v+a
}

V(g)$size <- scale(abs(cs$eigenvectors[[1]]), 10, 20)
E(g)$color <- "grey"
E(g)[ V(g)[ color=="lightblue" ] %--% V(g)[ color=="green" ] ]$color <- "red"

tkplot(g, layout=layout.kamada.kawai, vertex.label.font=2)

After hand-tuning the layout, you can obtain the new coordinates using the id of the plot, as shown on the window border:

coords <- tkplot.getcoords(1)

You can find the karate.net file here.


Transparency

Illustration

The R graphics device handles transparency (on most platforms), we use this to plot one graph on top of another.

library(igraph)

g <- barabasi.game(100, power=0.6, m=10)
V(g)$name <- seq(vcount(g))
g <- simplify(g)
l <- layout.fruchterman.reingold(g)
l <- layout.norm(l, -1,1, -1,1) 

fcs <- fastgreedy.community(simplify(as.undirected(g)))
Q <- round(modularity(fcs), 3)

# png(file="fastgreedy.png")

plot(g, layout=l, vertex.size=3, vertex.label=NA, vertex.color="#ff000033",
     vertex.frame.color="#ff000033", edge.color="#55555533", edge.arrow.size=0.3,
     rescale=FALSE, xlim=range(l[,1]), ylim=range(l[,2]),
     main=paste(sep="", "Fast greedy community detection,\nQ=", Q))

g2 <- induced.subgraph(g, communities(fcs)[[1]])
l2 <- l[ communities(fcs)[[1]], ]

plot(g2, layout=l2, vertex.size=3, vertex.label=V(g2)$name,
     vertex.color="#ff0000", vertex.frame.color="#ff0000", edge.color="#555555",
     vertex.label.dist=0.5, vertex.label.cex=0.8, vertex.label.font=2,
     edge.arrow.size=0.3, add=TRUE, rescale=FALSE)

nodes <- communities(fcs)[[1]]
nodes <- paste(collapse=", ", nodes)
text(0,-1.3, nodes, col="blue")

# dev.off()


Components of an Erdős-Rényi random graph

Illustration

Erdős-Rényi random graphs have a fixed number of vertices (given by the parameter n) and a fixed number of edges (given by m) that are placed between pairs of vertices with equal probability. When one increases m gradually, small disconnected tree-like components will appear, but there exists a threshold m' (depending on n) where a giant component appears suddenly.

In this visualization, we used the Python interface to show an Erdős-Rényi graph near its threshold m'. Components are colored with different colors according to their size, isolated vertices are colored with light gray.

from igraph import *

g = Graph.Erdos_Renyi(n=300, m=250)
colors = ["lightgray", "cyan", "magenta", "yellow", "blue", "green", "red"]
components = g.components()
for component in components:
  color = colors[min(6, len(component)-1)]
  g.vs[component]["color"] = color
  
plot(g, layout="fr", vertex_label=None)


Kautz graph and its adjacency matrix

Illustration

Kautz graphs are regular graphs used for processor connection patterns in high-performance and fault-tolerant computing (see its Wikipedia entry for details). igraph is able to generate Kautz graphs (and their counterparts, De Bruijn graphs). Here we used the Python interface to visualize a Kautz graph with M=3 and N=2 along with its adjacency matrix to decipher the inner structure of the graph. The adjacency matrix is shown as an inset in the upper right corner with opacity 0.7.

from igraph import *

g = Graph.Kautz(m=3, n=2)
adj = g.get_adjacency()
fig = Plot(bbox=(480, 480))
fig.add(g, layout="fr", vertex_label=None)
fig.add(adj, bbox=(360, 0, 480, 120), grid_width=0, opacity=0.7)
fig.show()


Minimum spanning tree of a geometric random graph

Illustration

The image on the right shows a geometric random graph with 100 vertices dropped randomly onto the unit squre. Two vertices are connected if and only if their distance is less than 0.2. The edge weights correspond to the distance of the two endpoints, while the widths of the edges are proportional to the closeness of the endpoints (the closer they are, the thicker the edge is). Red edges show the calculated minimum weight spanning tree of the graph.

from igraph import *

def distance(p1, p2):
    return ((p1[0]-p2[0]) ** 2 + (p1[1]-p2[1]) ** 2) ** 0.5
    
g = Graph.GRG(100, 0.2)
layout = Layout(zip(g.vs["x"], g.vs["y"]))

weights = [distance(layout[edge.source], layout[edge.target]) for edge in g.es]
max_weight = max(weights)
g.es["width"] = [6 - 5*weight/max_weight for weight in weights]
mst = g.spanning_tree(weights)

fig = Plot()
fig.add(g, layout=layout, opacity=0.25, vertex_label=None)
fig.add(mst, layout=layout, edge_color="red", vertex_label=None)
fig.show()


Plotting the diameter

Illustration

This example shows how vertices along a path (the diameter in this case) can be selected. We use the igraph R package.

library(igraph)

g <- read.graph("karate.net", format="pajek")
d <- get.diameter(g)

E(g)$color <- "grey"
E(g)$width <- 1
E(g, path=d)$color <- "red"
E(g, path=d)$width <- 2
V(g)$label.color <- "blue"
V(g)$color  <- "SkyBlue2"
V(g)[ d ]$label.color <- "black"
V(g)[ d ]$color <- "red"

plot(g, layout=layout.fruchterman.reingold, 
     vertex.label.dist=0, vertex.size=15)
title(main="Diameter of the Zachary Karate Club network",
      xlab=paste("created by igraph", packageVersion("igraph")))
axis(1, labels=FALSE, tick=TRUE)
axis(2, labels=FALSE, tick=TRUE)


You can find the karate.net file here.


Degree distributions for nonlinear preferential attachment

Illustration

We plot how the (cumulative) in-degree distribution of a graph changes if we change the exponent of the preferential attachment process. We use the igraph R package.

library(igraph)

g <- barabasi.game(100000)
d <- degree(g, mode="in")
dd <- degree.distribution(g, mode="in", cumulative=TRUE)
alpha <- power.law.fit(d, xmin=20)
plot(dd, log="xy", xlab="degree", ylab="cumulative frequency",
     col=1, main="Nonlinear preferential attachment")
lines(10:500, 10*(10:500)^(-coef(alpha)+1))

powers <- c(0.9, 0.8, 0.7, 0.6)
for (p in seq(powers)) {
  g <- barabasi.game(100000, power=powers[p])
  dd <- degree.distribution(g, mode="in", cumulative=TRUE)
  points(dd, col=p+1, pch=p+1)
}

legend(1, 1e-5, c(1,powers), col=1:5, pch=1:5, ncol=1, yjust=0, lty=0)


Plotting the dendrogram of a community structure algorithm

Illustration

We use the R package and convert the output of the Walktrap community finding algorithm to a dendrogram.

library(igraph)
g <- read.graph("karate.net", format="pajek")

wt <- walktrap.community(g, modularity=TRUE)
dend <- as.dendrogram(wt, use.modularity=TRUE)
plot(dend, nodePar=list(pch=c(NA, 20)))


You can find the karate.net file here.


Creating simple animations

Illustration

We plot the network after each iteration of the Girvan-Newman edge betweenness based community structure finding algorithm. The edge betweenness values are shown on the left, the top five values are also shown as edge colors. The components are coded with different vertex colors and the modularity score of the actual division is on the top.

You can get the karate.net file from here. Download the animation: AVI file, MNG file.

library(igraph)

g <- read.graph("karate.net", format="pajek")
l <- layout.kamada.kawai(g, niter=1000)
ebc <- edge.betweenness.community(g)

colbar <- rainbow(6)
colbar2 <- c(rainbow(5), rep("black",15))

for (i in 1:20) {

  g2 <- delete.edges(g, ebc$removed.edges[seq(length=i-1)])
  
  eb <- edge.betweenness(g2)
  cl <- clusters(g2)$membership
  q <- modularity(g, cl)

  E(g2)$color <- "grey"
  E(g2)[ order(eb, decreasing=TRUE)[1:5] ]$color <- colbar2[1:5]

  E(g2)$width <- 1
  E(g2)[ color != "grey" ]$width <- 2

  # png(sprintf("eb-community-%04d.png", i))
  plot(g2, layout=l, vertex.size=6, vertex.label=NA,
       edge.label.color="red", vertex.color=colbar[cl+2],
       edge.label.font=2)
  title(main=paste("Q=", round(q,3)), font=2)
  ty <- seq(1,by=-strheight("1")*1.5, length=20)
  text(-1.3, ty, adj=c(0,0.5), round(sort(eb, dec=TRUE)[1:20],2), col=colbar2,
       font=2)

  # dev.off()
  if (interactive()) Sys.sleep(1)
}