is igraph preferential attachment directed graph acyclic?

Question

I am generating graphs using the Barabasi-Albert model implemented by igraph:

Graph.Barabasi(10,5,directed=True)

How can I be sure that the generated directed graphs are acyclic? Is there a basic property that implies that?

I found here this about the model in question:

"This model however lacks several properties of the world wide web : • If we regard the model as producing a directed network, then it generates acyclic graphs which are a poor representation of the Web."

but how I can be sure of that properties on the graphs generated by igraph?

Answer 1

The algorithm generates random scale-free networks.

Here is the description of how it works from wikipedia:

The network begins with an initial network of m0 nodes. [...] 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.

This means that if we start out with a small acyclic network and add new nodes with directed edges they will always point at existing nodes. There is no possibility of completing a cycle in this way since this would require an existing node to point to a new node.

When each new node only connects to one other node it is easy to see that the resulting graph will be acyclic as the figure on the wikipedia page shows. The graph is generated with m = 1.

But this property also holds for larger values of m when the added edges are directed.

Note: It is assumed here that the seed-graph is acyclic. If we would have had a cycle in the small seed-graph this cycle would of course remain as new nodes are generated and the graph grows.