Introduction

Network science aims to build models of graphs that reproduces the properties of real networks. Maybe you need to generate different type of graphs to test an algorithm or want to look for some properties of a mathematically clear (without outliers) graph instead of the real graph. {igraph} package gives different opportunities to generate graph you want.

Barabasi: Network science suggests three models of graphs:

  • random network model (Erdős-Rényi)
  • small world (Watts-Strogatz)
  • scale free network (Barabási-Albert)

For model details see it in the online book in Chapter 3 and in Chapter 4.

{igraph} has more opportunity to generate random graphs, in this post I give an overview of this three model.

Random network model (Erdős-Rényi)

There are two definitions of random network:

  • G(N,L) model: N nodes are connected with L randomly placed links (Erdős-Rényi)
  • G(N,p) model: each pair of N nodes is connected with probability p (Gilbert)

G(N,L) fixes the total number of links, and G(N,p) fixes the probability that two nodes are connected or not.

{igraph} can works with both type of random model. For technical details
see the function details.

g <- erdos.renyi.game(500, 350, type = "gnm")
plot(g, vertex.label= NA, edge.arrow.size=0.02,vertex.size = 0.5, xlab = "Random Network: G(N,L) model")

plot of chunk random G(N.L)

g <- erdos.renyi.game(500, 0.0035, type = "gnp")
plot(g, vertex.label= NA, edge.arrow.size=0.02,vertex.size = 0.5, xlab = "Random Network: G(N,p) model")

plot of chunk random G(N.p)

Small world model (Watts-Strogatz)

The small world phenomenon is structure of nodes with links to its k closest neighbors. The next properties of rewiring probability that mean each edge has probability p that it will be rewired to the graph as a random edge.

g <- watts.strogatz.game(1, 500, 1, 0.35, loops = FALSE, multiple = FALSE)
plot(g, vertex.label= NA, edge.arrow.size=0.02,vertex.size = 0.5, xlab = "Small world model")

plot of chunk Watts-Strogatz

You can examine some parameters of graph, for example, average distance is 9.6916742.

There are many other option in function details. For example other names of function, and description of parameters.

Scale free network (Barabási-Albert)

A scale-free network is a network whose degree distribution follows a power law. If a network is directed, the scale-free property applies separately to the in- and out-degrees.

Barabasi suggests that the degrees of nodes should examine firstly, what kind of distribution it follows. Nodes with widely different degrees coexist in the same network, there are hubs and small degree nodes in the network at same time.

Dynamic mode

In this model, an edge is most likely to attach to nodes with higher degrees. The network begins with an initial network of m nodes. m \geq 2 and the degree of each node in the initial network should be at least 1, otherwise, it will always remain disconnected from the rest of the network.

In the Barabasi-Albert model, new nodes are added to the network one at a time. Each new node is connected to m existing nodes with a probability that is proportional to the number of links that the existing nodes already have.

g <- barabasi.game(500, power = 1.2, m = NULL, out.dist = NULL, out.seq = NULL,
  out.pref = FALSE, zero.appeal = 1, directed = FALSE,
  algorithm ="psumtree", start.graph = NULL)
plot(g, vertex.label= NA, edge.arrow.size=0.02,vertex.size = 0.5, xlab = "Scale-free network model")

plot of chunk barabasi

For this graph the degree distribution is

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.004, 0.008, 0.012, 0.032, 0.036, 0.076, 0.198, 0.618

It is suggested to see the function details.

Static mode

In this case static.power.law.game() function can be used with known power law exponent, # of edges, # of nodes.

g <- static.power.law.game(500, 500, exponent.out= 2.2, exponent.in = -1, loops = FALSE, multiple = FALSE, finite.size.correction = TRUE) 
plot(g, vertex.label= NA, edge.arrow.size=0.02,vertex.size = 0.5, xlab = "Scale-free network model (static)")

plot of chunk barabasi.static

The exponent of power law of node degree of this graph is \gamma = 3.0609354.

However, note that it is unlikely that you will recover your observed exponents exactly due to finite size effects. Suppose if # of nodes and # of edges are infinite than observed exponent equal to exactly the required exponent.

You can see details of this funtion here.


Be happyR! 🙂

See also:

Barabasi: Network science

Network science on Wikipedia

Blog post of Chen-Jug Wang

Details of erdos.renyi.game() function

Details of watts.strogatz.game() function

Details of barabasi.game() function

Details of static.power.law.game() function

Advertisements