Message Boards Message Boards

[✓] DirectedEdges invalid for small-world nor scale-free network generation

GROUPS:

Dear Community,

I tried to generate a directed-edged small-world network using

RandomGraph[WattsStrogatzGraphDistribution[10, 0.4], 
 DirectedEdges -> True]

But was prompted that the call was made with invalid parameters. The same message was given for BarabasiAlbertGraphDistribution[10, 2].

Are the theories of small-world and scale-free networks not applicable to directed-edged networks? Or does just RandomGraph not allow these? For what reasons?

But RandomGraph generates directed-edged networks with BernoulliGraphDistribution and UniformGraphDistribution.

POSTED BY: Chi-Hsiang Wang
Answer
5 months ago

I have requested this feature in the past, i.e. that BarabasiAlbertGraphDistribution should support directed edges through the DirectedEdges option, but it was not added (yet?)

One workaround is

DirectedGraph[
 RandomGraph@BarabasiAlbertGraphDistribution[50, 1],
 "Acyclic"
 ]

This exploits the specific ordering of vertices in BarabasiAlbertGraphDistribution. This ordering is not documented, so I would not be 100% comfortable relying on it in the future.

Aside: You cal BarabasiAlbertGraphDistribution a scale-free network. This is a bit misleading. This is only one of the many models which generate a graph with a scale free degree distribution. This specific model (preferential attachment) has special properties which are not generally true for all networks with a similar degree distribution. As a trivial example, BarabasiAlbertGraphDistribution[..., 1] is always a tree. Other graphs with the same degree sequence may not be.

The IGraph/M package includes a preferential attachment model which allows for controlling whether the result should be directed.

IGBarabasiAlbertGame[50, 1, DirectedEdges -> True]
IGBarabasiAlbertGame[50, 1, DirectedEdges -> False]

The default is DirectedEdges -> True.

As for the Watts-Strogatz model, here's a quick implementation using IGraph/M again:

Options[wattsStrogatzGame] = {DirectedEdges -> False};
wattsStrogatzGame[n_, p_, k : _?Except[OptionQ] : 2, opt : OptionsPattern[]] := 
 IGRewireEdges[
  IGMakeLattice[{40}, "Periodic" -> True, "Radius" -> k, 
   DirectedEdges -> OptionValue[DirectedEdges]], p]

IGRewireEdges does what its name says: it rewires edges.

IGMakeLattice is like GridGraph, but it supports periodic lattices, as well as connecting all nodes within a certain radius.

Alternatively, we could have used IGConnectNeighborhood with CycleGraph to generate a starting graph to rewire.

As always, suggestions for improving IGraph/M are welcome. Future improvements will be prioritized based on user demand.

POSTED BY: Szabolcs Horvát
Answer
5 months ago

Many thanks for these excellent solutions, Szabolcs! DirectedGraph with option of either "Acyclic" or "Random" works fine for me now.

Thanks also for your effort creating IGraph/M, I'm sure I'll use it someday in future!

POSTED BY: Chi-Hsiang Wang
Answer
5 months ago

Group Abstract Group Abstract