Simple Interconnected Islands network generator

example of SII network

Overview

The Simple Interconnect Islands (SII) network generator creates networks made of nb.islands islands. Each island is made of a random network of size size.island and having density p.in. Every pairs of islands are interconnected by n.inter links.

This random network generator may be used for benchmarking and/or simulation. It creates small-world networks with communities. It does not intends to generate plausible nor realistic networks, but its statistical properties may be easily tuned by playing with its parameters.

Properties

expected total number of edges (total_links_expected): (nb.islands-1)*nb.islands/2 + nb.islands*size.island*(size.island-1)/2*p.in
total number of nodes (totalsize): nb.islands*size.island
expected average degree: 2*total_links_expected/totalsize
expected density: total_links_expected/(totalsize*(totalsize-1)/2)
expected clustering rate into each island: p.in (as in any random network)
expected clustering rate in the whole network: (p.in^3 + (n.inter/size.island)^3) / (p.in^2 + (n.inter/size.island)^2)
distribution of degree is Poisson-like (sum of the distribution of connectivity for islands).

Behaviour:

connected as long as p.in is high enough (as in any random network)
average path length increase slighly when size.island increase. Average path length decrease when nb.islands increase.
islands create areas with strong clustering
average short path remains low because of the interconnections between islands.
as a consequence, SII networks are small-world according to the Watts&Strogatz 1998 definition.

Sourcecode

This R script enable a low-perf generation of SII (requires the igraph package).

island.simple.game <- function (nb.islands, size.island, p.in, n.inter) 
{
	totalsize = nb.islands*size.island	

	nbOtherIsland = (nb.islands-1)*size.island	

	g <- graph.empty(n=totalsize, directed = FALSE)
	
	
	for (is in 1:nb.islands) { # for each island

		startIsland = size.island*(is-1)
		endIsland = startIsland+size.island-1

		# create links inside the island
		i = startIsland
		while (i <= endIsland) { # for each node in this island

			j = i+1
			while (j <= endIsland) { # create link with other nodes in the island

				if ( (p.in == 1) || (runif(min=0,max=1, n=1) <= p.in) ) {
					g <- add.edges(g, c(i, j))
				}
				j=j+1
			}

			
			i=i+1
		}

		
		# and create links with other islands 
		otherIsland = is+1
		while (otherIsland <= nb.islands) { # for each other island

			nb = 0
			while (nb < n.inter) {
				idInThisIsland = igraph.sample(low=startIsland, high=endIsland, length=1)
				idInOtherIsland = igraph.sample(low=((otherIsland-1)*size.island), high=(otherIsland*size.island-1), length=1) 
				g <- add.edges(g, c(idInThisIsland, idInOtherIsland))
				nb = nb + 1
			}

			otherIsland = otherIsland + 1
		}


	}

	return(g)
	
}

This network generator will next be included in the igraph package with a more efficient C version (see https://code.launchpad.net/~samuel-...) for sourcecode.

Example

First open R, load the igraph library, and copy/past the script above:

login@machine:~$ R

R version 2.12.1 (2010-12-16)
Copyright (C) 2010 The R Foundation for Statistical Computing
ISBN 3-900051-07-0
[...]

> library(igraph)

[... past sourcecode here]

Generating a SII network:

> g <- island.simple.game(nb.islands=5, size.island=20, p.in=0.1, n.inter=2)

Display it and observe some of its properties:

> tkplot(g, layout=layout.fruchterman.reingold)
> average.path.length(g)
> plot(degree.distribution(g))

Samuel Thiriot

Overview

Properties

Sourcecode

Example