6
$\begingroup$

My aim is to generate a 2D Small World network on a square grid. i.e. 20x20. With a probability of 5%, one node rewires from an adjacent node to a random node of the grid, allowing some long distance edges. Yet, the grid topology should be fixed. More specifically, the vertices sould be fixed, only the edges may be replaced, maintaining an average degree of <4>. All my tries ended up in the breaking of the grid topology. Unfortunately, the WattStrogatzGraphDistribution does not help as well,as it is not embedded on a lattice.

The result should somewhat look like this: 2D Small World on a Grid

(Source: Biondo et al. (2013) - Reducing Financial Avalanches By Random Investments , Phys. Rev. E 88, 062814)

The colored nodes are not from importance. The question might be helpful for others,too, who try to implement a certain type of network topology on a lattice. Thanks in advance for your help.

$\endgroup$
  • $\begingroup$ The IGraph/M package has the IGRewire function which will randomly rewire edges while keeping the degree sequence. There's also IGRewireEdges which keeps the total number of edges (thus also the average degree), but it does not preserve the degree sequence. Take a look. These can be implemented in pure Mathematica too, but I would be lazy to do that ;-) GridGraph will be useful too. $\endgroup$ – Szabolcs Feb 10 '16 at 22:57
  • 2
    $\begingroup$ g = GridGraph[{20, 20}]; EdgeAdd[EdgeDelete[g, #], Thread[UndirectedEdge[#[[All, 1]], RandomChoice[VertexList@g, Length@#]]]] &@ Pick[EdgeList@g, RandomVariate[BernoulliDistribution[.05], Length@EdgeList@g], 1]? $\endgroup$ – Dr. belisarius Feb 10 '16 at 23:36
  • $\begingroup$ Marginal to your question, but it's good to not that if you start with the grid shown here, the rewired networks will not have the small world property as originally defined by Watts and Strogatz because a simple lattice like this does not have a high clustering coefficient. $\endgroup$ – Szabolcs Feb 11 '16 at 9:29
8
$\begingroup$

Quick summary

  • The IGraph/M package has several functions to help with this (IGRewireEdges).
  • The rewired network will not have the small world property unless the starting grid connects at least second neighbours as well. IGraph/M has a function to generate such a starting grid (IGMakeLattice).

Easiest is to use IGraph/M!

While this can be implemented in pure Mathematica, it is even easier with the IGraph/M package.

<< IGraphM`

We start with a grid graph:

g = GridGraph[{30, 30}];
coords = GraphEmbedding[g];

IGRewireEdges will rewire each edge with probability p, preserving the total number of edges.

?IGRewireEdges

IGRewireEdges[graph, p] rewires each edge of the graph with probability p.

Graph[IGRewireEdges[g, 0.1], VertexCoordinates -> coords]

Mathematica graphics

We can control whether the creation of self loops or multi-edges is allowed:

Options[IGRewireEdges]
(* {SelfLoops -> False, "MultipleEdges" -> False} *)

IGRewire will rewire in such a way as to preserve the degree of each vertex. We can specify the number of rewiring trials (not all of which may succeed).

?IGRewire

IGRewire[graph, n] attempts to rewire the edges of graph n times while preserving its degree sequence.

Graph[IGRewire[g, 100], VertexCoordinates -> coords]

Mathematica graphics

We can control whether the creation of self loops is allowed:

Options[IGRewire]
(* {SelfLoops -> False} *)

Need for this functionality was one of the reasons why I wrote IGraph/M. While it can be implemented in Mathematica, that is simply not fast enough for many implemented.


What is a "small-world" network?

Originally (Watts & Strogatz) a "small world" property of the network referred to having

  1. A short average shortest path length
  2. A high clustering coefficient

A random graph has (1) but not (2).
A graph like in the figure below has (2) but not (1):

enter image description here

So they made something "inbetween" by starting with this regular lattice where every 2nd neighbour is connected and rewiring edges to make it more random, achieving both properties at the same time.

enter image description here

Does your network have the small world property? No, because a simple grid graph does not have a high clustering coefficient.

N@GlobalClusteringCoefficient@GridGraph[{30, 30}]

(* 0. *)

Nor does a cycle graph, which is a periodic 1D grid graph with only first neighbours connected. We need at least every second neighbour connected, like this:

g = IGMakeLattice[{10}, Radius -> 2, Periodic -> True]

Mathematica graphics

N@GlobalClusteringCoefficient[g]
(* 0.5 *)

IGraph/M's grid graph generator helps here because it has the Radius option to connect $n^\text{th}$ neighbours. We can also do it for 2D:

g = IGMakeLattice[{20, 20}, Radius -> 2]

Mathematica graphics

Let's check the clustering and average shortest path length before rewiring ...

N@GlobalClusteringCoefficient[g]
(* 0.468933 *)

IGAveragePathLength[g]
(* 6.91729 *)

... and after rewiring:

g2 = IGRewireEdges[g, 0.03];

N@GlobalClusteringCoefficient[g2]
(* 0.390251 *)

IGAveragePathLength[g2]
(* 3.64128 *)

The clustering coefficient is reduced somewhat, but not significantly. The average path length is however cut in half.

We see that to get the small world property we must start with a lattice where at least second neighbours are connected!

$\endgroup$
  • $\begingroup$ The IGraph tool looks very convincing! I'm going to give it a try for sure. Especially, since there is no global clusering coefficient involved in mathematica's gridgraph. The "problem" with the declining average path length is not really a problem, as it is an arbitrary setting, and we can keep the average path length low by considering smaller rewiring probabilities, to be in line with i.e. real world social network topologies. So, thanks for your Help! :) $\endgroup$ – ResidentStiefel Feb 11 '16 at 11:47
  • $\begingroup$ Sorry, i accidentally posted the comment before it was ready. $\endgroup$ – ResidentStiefel Feb 11 '16 at 11:48
  • $\begingroup$ @ResidentStiefel Let me know if you have any trouble with IGraph/M! What OS are you using? $\endgroup$ – Szabolcs Feb 11 '16 at 11:51
  • $\begingroup$ I'm using 64-Bit Windows10, and it works just fine! $\endgroup$ – ResidentStiefel Feb 11 '16 at 12:00
  • $\begingroup$ @Szabolcs Excellent answer! Question about the rewiring: given that we have the vertex coords and can calculate the Euclidean dist between pairs of nodes, could we rewire edges locally? (i.e. similar to a nearest neighbour approach, considering, 1st,2nd, 3rd.. furthest neighbours). $\endgroup$ – user929304 Aug 28 at 13:43
2
$\begingroup$

This is not an answer, but an extended comment. Dr.belisarius' answer, given in comment to the question, looks promising, but it can produce loops, Is this admissible?

SeedRandom[1];
With[{g = GridGraph[{20, 20}]}, 
  EdgeAdd[
    EdgeDelete[g, #], 
    Thread[UndirectedEdge[#[[All, 1]], RandomChoice[VertexList @ g, Length @ #]]]]& @
      Pick[
        EdgeList @ g, 
        RandomVariate[BernoulliDistribution[.05], Length@EdgeList@g], 1]]

graph

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.