Topologies

Sabaody implements all the topologies provided by PyGMO version 1.

One-way Ring

This topology is a directed cycle - migrants only flow in one direction around the ring.

In [1]:
#import tellurium
#from sabaody import TopologyFactory
from sabaody.topology import TopologyFactory

# dummy problem and algorithm for generated islands
class NoProblem:
    pass
class NoAlgo:
    pass

# create one way ring topology
f = TopologyFactory(NoProblem)
one_way_ring = f.createOneWayRing(NoAlgo,6)

# draw the topology
import networkx as nx
nx.draw(one_way_ring, pos=nx.spring_layout(one_way_ring,0.01,random_state=0))
import matplotlib
matplotlib.pyplot.show()
<Figure size 640x480 with 1 Axes>

Bidirectional ring

Like the one-way ring but migrants can flow in either direction.

In [2]:
bidir_ring = f.createBidirRing(NoAlgo,6)
nx.draw(bidir_ring, pos=nx.spring_layout(bidir_ring,0.01,random_state=0))
matplotlib.pyplot.show()
_images/topologies_4_0.png

Bidirectional chain

A simple linear topology.

In [3]:
bidir_chain = f.createBidirChain(NoAlgo,3)
nx.draw(bidir_chain, pos=nx.spring_layout(bidir_chain,0.01,random_state=0))
matplotlib.pyplot.show()
_images/topologies_6_0.png

Lollipop

A lollipop is a complete graph connected to a linear chain.

Note: Appears not to be working.
In [4]:
lollipop = f.createLollipop(NoAlgo,complete_subgraph_size=5,chain_size=5)
nx.draw(lollipop, pos=nx.spring_layout(lollipop,0.01,random_state=0))
matplotlib.pyplot.show()
_images/topologies_8_0.png

Rim

A bidirectional cycle with all nodes connected to a single node on the rim.

In [5]:
rim = f.createRim(NoAlgo,6)
nx.draw(rim, pos=nx.spring_layout(rim,0.05,random_state=0))
matplotlib.pyplot.show()
_images/topologies_10_0.png

1-2 Ring

A bidirectional cycle where each node is also connected to its next-nearest neighbor.

Note: Not present in PyGMO.
In [6]:
ring12 = f.create_12_Ring(NoAlgo,8)
nx.draw(ring12, pos=nx.spring_layout(ring12,0.1,random_state=0))
matplotlib.pyplot.show()
_images/topologies_12_0.png

1-2-3 Ring

A topology where each node is connect to its next-nearest neighbor, as in a 1-2 ring, but is also additionally connected to its respective third neighbors.

In [7]:
ring123 = f.create_123_Ring(NoAlgo,8)
nx.draw(ring123, pos=nx.spring_layout(ring123,0.1,random_state=0))
matplotlib.pyplot.show()
_images/topologies_14_0.png

Fully Connected (Complete Graph)

A topology where each node is connected to every other node (i.e. a complete graph).

In [8]:
fully_connected = f.createFullyConnected(NoAlgo,6)
nx.draw(fully_connected, pos=nx.spring_layout(fully_connected,0.1,random_state=0))
matplotlib.pyplot.show()
_images/topologies_16_0.png

Broadcast

A collection of nodes not connected to each other but to a central node.

In [9]:
broadcast = f.createBroadcast(NoAlgo,6)
nx.draw(broadcast, pos=nx.spring_layout(broadcast,0.1,random_state=0))
matplotlib.pyplot.show()
_images/topologies_18_0.png

Hypercube

A topology defined by the hypercube of dimension \(N\), with \(2^N\) verticies and \(N\cdot2^{N-1}\) edges.

In [10]:
hypercube = f.createHypercube(NoAlgo,4)
nx.draw(hypercube, pos=nx.spring_layout(hypercube,0.1,random_state=0))
matplotlib.pyplot.show()
_images/topologies_20_0.png

Watts-Strogats

A Watts-strogats graph tends to exhibit small-world effects.

In [11]:
watts_strogatz = f.createWattsStrogatz(NoAlgo,num_nodes=16,k=8,p=0.1,seed=1)
nx.draw(watts_strogatz, pos=nx.spring_layout(watts_strogatz,0.1,random_state=0))
matplotlib.pyplot.show()
_images/topologies_22_0.png

Erdős-Rényi

The oft-cited original random graph algorithm, the Erdős-Rényi method samples graphs uniformly from a distribution of \(N\) nodes and \(M\) edges. That is, all graphs with \(N\) nodes and \(M\) edges are equally likely.

In [12]:
erdos_renyi = f.createErdosRenyi(NoAlgo,num_nodes=16,p=0.5,seed=1)
nx.draw(erdos_renyi, pos=nx.spring_layout(erdos_renyi,0.1,random_state=0))
matplotlib.pyplot.show()
_images/topologies_24_0.png

Barabási-Albert

Designed to exhibit the same power-law scaling behavior found in many naturally occurring networks (such as genetic circuits, social networks, and the World Wide Web), the Barabási-Albert method constructs graphs by adding new edges to nodes based on the number of edges already connected to the node. The end result is a graph with a small number of centralized “hubs” harboring the majority of connections.

References:

Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509-512.

In [13]:
barabasi_albert = f.createBarabasiAlbert(NoAlgo,num_nodes=16,m=3,seed=1)
nx.draw(barabasi_albert, pos=nx.spring_layout(barabasi_albert,0.1,random_state=0))
matplotlib.pyplot.show()
_images/topologies_26_0.png

Extended Barabási-Albert

The original Barabási-Albert algorithm spawned many variants. In this popular variant, implemented as extended_barabasi_albert_graph in networkx, the graph is grown via three processes, which can be selected probabilistically at each step of the algorithm:

  1. Addition of m new edges with probability p
  2. Rewiring of m edges with probability q
  3. Addition of a new node with probability 1 - p - q

Of course, the processes are mutually exclusive and \(p + q < 1\). This method can operate in a scale-free regime (\(q = 0\)) or an exponential regime (\(q \rightarrow 1\)).

References:

Albert, R., & Barabási, A. L. (2000). Topology of Evolving Networks: Local Events and Universality. Physical Review Letters 85(24), 5234.

In [14]:
extended_barabasi_albert = f.createExtendedBarabasiAlbert(NoAlgo,16,m=3,p=0.3,q=0.1,seed=1)
nx.draw(extended_barabasi_albert, pos=nx.spring_layout(extended_barabasi_albert,0.1,random_state=0))
matplotlib.pyplot.show()
_images/topologies_28_0.png

Extended Ageing Barabási-Albert

Identical to the extended Barabási-Albert but nodes older than max_age cannot be connected to, effectively capping the connectivity of individual nodes. This topology is intended to fill the role of the ageing clustered Barabási-Albert topology from PyGMO. However, the PyGMO version uses an unknown variant of the Barabási-Albert for their “clustered” Barabási-Albert model and this one. For our implementation, we use the well-known “local events” model referenced above (Phys Rev. Letters, Dec. 2000).

In [15]:
ageing_barabasi_albert = f.createAgeingExtendedBarabasiAlbert(NoAlgo,n=16,m=3,p=0.3,q=0.1,max_age=10,seed=1)
nx.draw(ageing_barabasi_albert, pos=nx.spring_layout(ageing_barabasi_albert,0.1,random_state=0))
matplotlib.pyplot.show()
_images/topologies_30_0.png