Random Graphs

Classic Random Graphs
Preferential Attachment and Variations
The Configuration Model
Growing Random Graphs
Trait Based Random Graphs
Preferential Attachment and Aging

Classic Random Graphs

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

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

A Gn,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 Gn,p graphs, but if the type argument is set to gnm then Gn,m graph will be generated. The first argument of the function is the number of vertices and the second is either p or m depending on the type of the random graph.

Here 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 arguments.

Preferential Attachment and Variations

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. TODO: examples

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 not initiated by the given vertex as long as the out.pref argument is not set to 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 is normalized to create proper probabilities. It is an error however to supply meaningless values in out.dist, like negative numbers, or only zero elements, or an empty vector.

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 are counted as a basis of the preferential attachment. Some plots with different time window parameters: TODO.

The Configuration Model

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 

[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 

[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.

Growing Random Graphs


Trait Based Random Graphs

callaway.traits.game() establishment.game()

Preferential Attachment and Aging