Network Analysis with igraph |
---|

Random graphs were introduced by Erdős and Rényi in the late
fifties. They defined two ways for generating random graph:
G_{n,p} and G_{n,m}, these
determine two ensembles of random graphs as well.

A G_{n,p} graph is undirected, has n vertices and
p is the probability that an edge is present in the graph. So
G_{n,p} graphs are generated by drawing an
indicator random variable for each possible edge in the graph.

A G_{n,m} random graph is undirected, has n
vertices and m edges. The m edges are drawn uniformly random from the
set of all possible edges.

igraph can generate both types of random graphs with the
`erdos.renyi.game()`

function. (All random graph
generators are called *games* in igraph.)
By default this function generates G_{n,p} graphs,
but if the * type* argument is set to

`gnm`

then GHere is an example of a small random graph with low edge density:

`>`

g <- erdos.renyi.game(100, 2/100)`>`

plot(g, layout=layout.fruchterman.reingold, vertex.size=3, labels=NA, frame=TRUE)

As an example we generate two random graphs, one of each type and plot their degree distribution:

`>`

g1 <- erdos.renyi.game(10000, 8/10000, type="gnp")`>`

g2 <- erdos.renyi.game(10000, 30000, type="gnm")`>`

plot(degree.distribution(g1), xlab="degree", ylab="frequency", pch=1, col=1, type="b")`>`

points(degree.distribution(g2), pch=2, col=2, type="b")

In addition to the standard undirected random graphs,
`erdos.renyi.game`

is also able to generate
directed graphs and graphs with loop edges. See the
* directed* and

`loops`

This is a growing graph model introduced first by Price [TODO] and reintroduced later by Barabási and Albert [1]. This is a discrete time step model and it creates a directed graph (although igraph can create an undirected one as well). We start with a single vertex and in each time step add another vertex to the graph. This vertex then chooses a number of old vertices (this is a parameter called m) randomly based on their in-degree and initiates edges to them. In particular the probability that a vertex is chosen is proportional to its in-degree plus some constant (a). (This constant is need to have zero in-degree vertices non-zero connection probability.) The same process is repeated in the following time steps.

`>`

g <- barabasi.game(100)`>`

plot(g, layout=layout.kamada.kawai, vertex.size=3, labels=NA, frame=TRUE)

In the default version of the igraph
`barabasi.game()`

function, the number of edges
added in each time step is one (m=1) and the constant giving the
connection “probability” of the zero in-degree vertices
is also one (a=1). The former can be changes by assigning a different
value to the * m* parameter of the function, while
the latter is set via the

`zero.appeal`

`barabasi.game()`

creates directed graphs by
default, set the * directed* to

`FALSE`

to generate undirected graphs. Note however
that even if the generated graph is undirected the connection
probability is still calculated based on the number of adjacent edges
`out.pref`

`TRUE`

. You can imagine this as first generating a
directed graph and then converting that to an undirected one.
If the * out.pref* is set to

`TRUE`

then the total degree of the vertices is
used to generate the connection probabilities independently of whether
a directed or undirected graph is being created.
If the * out.seq* parameter is not

`NULL`

then it must be a vector of n integer
numbers, n is the number of vertices in the graph. This vector is used
as the number of edges to add per time step, it's first element is
ignored as no edges are added while there is only a single vertex in
the graph.
If the * out.dist* parameter is not

`NULL`

then it is used as the probabilities for
creating the number of edges to add in each time step. The first
element of it gives the probability that no edges will be added in a
time step, the second is the probability to add one edge, etc.
Note that you don't need to supply probabilities,
`out.dist`

`out.dist`

Note that the current version of `barabasi.game()`

may create graphs with multiple edges, this might change in the
future.

The original Barabási-Albert model uses linear preferential
attachment, ie. the connection probability is proportional to the
degree of the vertices. Nonlinear variations can also be studied with
igraph by supplying the * power* parameter:

`>`

g1 <- barabasi.game(10000, power=0.5)`>`

g2 <- barabasi.game(10000, power=1)`>`

g3 <- barabasi.game(10000, poert=1.5)`>`

plot(degree.distribution(g3), xlab="degree", ylab="frequency", log="xy", pch=3, col=3, type="b")`>`

points(degree.distribution(g2), pch=2, col=2, type="b")`>`

points(degree.distribution(g1), pch=1, col=1, type="b")`>`

legend(max(degree(g3)), 1, xjust=1, yjust=1, c(0.5,1,1.5), pch=1:3, col=1:3, lty=1)

Another generalization is the * time.window*
parameter. If this is not

`NULL`

then its value is
used as a time window: only adjacent edges connected in the previous
`time.window`

The configuration model is a random in which the degree sequence is given. Ie. in an undirected graph the degree of each node is given and one should create a random graph with the given degree sequence. Note that this is not always possible, eg. if the sum of the degrees is odd then there is no such graph which could be the realization of this model since in a graph the sum of the degrees is always even.

If the sum of the degrees is even in an undirected, then there is always a graph which has the given degree sequence, but it may happen that no simple graphs fit the model, ie. every graph with the given degree sequence has either multiple or loop edges or both.

For a directed graph, two degree sequences are given, one for the in- and one for the out-degree. It is required that the sum of these be the same even number. Note that for some degree sequences all the possible realizations contain either multiple or loop edges or both, ie. there are no simple graphs with the given degree sequences.

In igraph the `degree.sequence.game()`

can
generate a graph with the given degree sequence(s). If only one
argument is given then an undirected graph will be created using the
single argument as a degree sequence. (Obviously the number of vertices
can be determined from the length of the degree sequence.)

`>`

g <- degree.sequence.game( rep(2, 10) )`>`

g

Vertices: 10 Edges: 10 Directed: FALSE Edges: [0] 4 -- 6 [1] 0 -- 7 [2] 0 -- 8 [3] 2 -- 5 [4] 1 -- 3 [5] 1 -- 4 [6] 5 -- 9 [7] 2 -- 7 [8] 3 -- 8 [9] 6 -- 9

`> `

degree(g)

[1] 2 2 2 2 2 2 2 2 2 2

If two arguments are given then the first is used as the out-degree and the second as the in-degree sequence:

`>`

g <- degree.sequence.game( rep(1,10), rep(1,10) )`>`

g

Vertices: 10 Edges: 10 Directed: TRUE Edges: [0] 8 -> 2 [1] 2 -> 0 [2] 4 -> 4 [3] 6 -> 1 [4] 3 -> 5 [5] 9 -> 7 [6] 0 -> 8 [7] 7 -> 3 [8] 1 -> 9 [9] 5 -> 6

`> `

degree(g, mode="in") ; degree(g, mode="out")

[1] 1 1 1 1 1 1 1 1 1 1 [1] 1 1 1 1 1 1 1 1 1 1

Function `degree.sequence.game()`

also has an
argument called * method*, which specifies the
algorithm to use for the graph generation. Right now only the

`simple`

algorithm is implemented so this is the
default method.
The `simple`

method first assigns degrees to
vertices and then creates stubs, uncorrected edge end-points, the
appropriate number for each vertex. Then it simply connects the stubs
randomly. This way multiple and loop edges might be generated.
It is known that this algorithm does not sample uniformly from the
ensemble of the random graphs with the given degree sequence.

<< Creating Graphs |
Importing and Exporting Graphs >> |