The Small-World vs. Scale-Free Graphs

WEN, Tzai-Hung (NTU Geography)

Source: Hartvigsen (2011), Using R to Build and Assess Network Models in Biology, Math. Model. Nat. Phenom 6(6):61-75

library(igraph)

1. The Random Graph

A random graph is constructed by taking a set of vertices and connecting each pair with a probability P.

1.1 Plotting a random graph

#?random.graph.game
g = random.graph.game(25, p.or.m = 0.2, type = "gnp")
plot(g, layout = layout.fruchterman.reingold, vertex.size = 5, vertex.label.dist = 1)

1.2 Frequency of vertex degree

gx = random.graph.game(10000, p.or.m = 0.1, type = "gnp")
hist_g = hist(degree(gx), main="random graph", col="Gray")

1.3 Counting the size of giant component

A giant component is a connected component of a given random graph that contains a constant fraction of the entire graph’s vertices.

size.giant.comp = function(g) {max(clusters(g)$csize)}

Nverts = 10000
Nedges = seq(Nverts/10, Nverts*2, by = Nverts/100)

P = numeric(length(Nedges)) # creating a null vector: Prop. verts in giant component.

for (i in 1:length(Nedges)) {
  g = erdos.renyi.game(Nverts, Nedges[i], type = "gnm")
  P[i] = size.giant.comp(g)/Nverts
}
plot(Nedges/Nverts, P,
     ylab = "% of vertices in giant comp.",
     xlab = "Nedges/Nvertices", xlim = c(0,2), ylim = c(0,1), cex.lab = 1.5)

abline(h=0.8);abline(v=1) # add reference lines

---

2. Comparing Watts-Strogatz’s Small-World vs. Albert and Barabasi’s Scale-Free Graphs

Characteristics of small-world graphs

# The Watts-Strogatz "Small-World" model
# ?watts.strogatz.game 
# ?sample_smallworld

g1 = sample_smallworld(1,size=100,nei=4,p=0.03)
par(mfrow = c(1,2))
plot(g1, vertex.size=5, edge.color="Blue", edge.arrow.size=.3,vertex.label=NA, main='Small-World Network')
plot(g1, vertex.size=5, edge.color="Blue", edge.arrow.size=.3,layout=layout.circle, vertex.label=NA, main='Small-World Network')

# The Albert and Barabasi "Scale-Free" model
# ?barabasi.game 
# ?sample_pa

h1= sample_pa (100)
par(mfrow = c(1,1))
plot(h1, vertex.size=5, edge.color="Blue", edge.arrow.size=.3, vertex.label=NA, main='Scale-Free Network')

g0 = watts.strogatz.game(1,size=100000,nei=4,p=0.25)
h0 = barabasi.game(100000)
par(mfrow = c(1,2))
a = hist(degree(g0), main="Small-World", col="Blue")
b = hist(degree(h0), main="Scale-Free", col="Green")

plot(1:length(a$counts),a$counts+1, xlab = "Degree", ylab = "Frequency", cex.lab = 1.5, main = "Small-World (log-log scale)", log = "xy", type = "b")
plot(1:length(b$counts),b$counts+1, xlab = "Degree",ylab = "Frequency", cex.lab = 1.5,main = "Scale-Free (log-log scale)", log = "xy", type = "b")

---

3. Network intervention: Assessing vaccination policy in small-world network

Nverts = 1000
prw = 0.05 # Prob of rewiring parameter
VE = seq(0,0.9, by = 0.05) # Vaccination Effort
SGC = numeric(length(VE)) # array hold size of giant comps.
for (i in 1:length(VE)) {
  g = sample_smallworld(1, size = Nverts, nei = 2, p = prw)
  Ndel = VE[i]*Nverts
  g = delete.vertices(g, sample(V(g),Ndel))
  SGC[i] = size.giant.comp(g)
}
par(mfrow = c(1,1))
plot(VE,SGC, type = "b", xlab = "Vaccination Effort", ylab="Size of giant comps.")