Introduction
Network science aims to build models of graphs that reproduces the proporties of real networks. Maybe you need to generate different type of graphs to test an algorithm or want to looking for some proporties of a mathematically clear (without outliers) graph instead of real graph. {igraph} package gives different opportunities to generate graph you want.
(Barabási 2015) 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 probabliity that two nodes is 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")
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")
Small world model (Watts-Strogatz)
The small world phenomenon also known as six degrees of separation. Two individual people on Earth are just six people “distance” from each other. (Was known earlier… Investigated facebook data it is just 4.74)
Small world model play with dimensionality of lattice (like a 2D, 3D lattice). There is an initial lattice structure of nodes with links to its k closest neighbors. The next proporties of rewiring probability that means 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")
You can eximane some parameters of graph, for example aveage distance is 11.1365186.
There are many other option in function details. For example other names of funtion, 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 proporty 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")
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, 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.006, 0.006, 0.008, 0.014, 0.02, 0.038, 0.072, 0.182, 0.642
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)")
The exponent of power law of node degree of this graph is \(\gamma\) = 7.4131307.
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:
Details of erdos.renyi.game() function
Details of watts.strogatz.game() function
References
Barabási, Albert-László. 2015. Network Science.
No comments:
Post a Comment