{ "cells": [ { "cell_type": "markdown", "source": [ "# Topologies\n", "\nSabaody implements all the topologies provided by [PyGMO version 1](http://esa.github.io/pygmo/documentation/topology.html)." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## One-way Ring\n", "\nThis topology is a directed cycle - migrants only flow in one direction around the ring." ], "metadata": {} }, { "cell_type": "code", "source": [ "#import tellurium\n", "#from sabaody import TopologyFactory\n", "from sabaody.topology import TopologyFactory\n", "\n", "# dummy problem and algorithm for generated islands\n", "class NoProblem:\n", " pass\n", "class NoAlgo:\n", " pass\n", "\n", "# create one way ring topology\n", "f = TopologyFactory(NoProblem)\n", "one_way_ring = f.createOneWayRing(NoAlgo,6)\n", "\n", "# draw the topology\n", "import networkx as nx\n", "nx.draw(one_way_ring, pos=nx.spring_layout(one_way_ring,0.01,random_state=0))\n", "import matplotlib\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 16, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Bidirectional ring\n", "\nLike the one-way ring but migrants can flow in either direction." ], "metadata": {} }, { "cell_type": "code", "source": [ "bidir_ring = f.createBidirRing(NoAlgo,6)\n", "nx.draw(bidir_ring, pos=nx.spring_layout(bidir_ring,0.01,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 17, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Bidirectional chain\n", "\nA simple linear topology." ], "metadata": {} }, { "cell_type": "code", "source": [ "bidir_chain = f.createBidirChain(NoAlgo,3)\n", "nx.draw(bidir_chain, pos=nx.spring_layout(bidir_chain,0.01,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 18, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Lollipop\n", "\n", "A lollipop is a complete graph connected to a linear chain.\n", "\n", "
\n", "\n", "**Note:** Appears not to be working.\n", "\n
" ], "metadata": {} }, { "cell_type": "code", "source": [ "lollipop = f.createLollipop(NoAlgo,complete_subgraph_size=5,chain_size=5)\n", "nx.draw(lollipop, pos=nx.spring_layout(lollipop,0.01,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 19, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Rim\n", "\nA bidirectional cycle with all nodes connected to a single node on the rim." ], "metadata": {} }, { "cell_type": "code", "source": [ "rim = f.createRim(NoAlgo,6)\n", "nx.draw(rim, pos=nx.spring_layout(rim,0.05,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 20, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## 1-2 Ring\n", "\n", "A bidirectional cycle where each node is also connected to its next-nearest neighbor.\n", "\n", "
\n", "**Note:** Not present in PyGMO.\n", "
" ], "metadata": {} }, { "cell_type": "code", "source": [ "ring12 = f.create_12_Ring(NoAlgo,8)\n", "nx.draw(ring12, pos=nx.spring_layout(ring12,0.1,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 21, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## 1-2-3 Ring\n", "\nA 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." ], "metadata": {} }, { "cell_type": "code", "source": [ "ring123 = f.create_123_Ring(NoAlgo,8)\n", "nx.draw(ring123, pos=nx.spring_layout(ring123,0.1,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 22, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Fully Connected (Complete Graph)\n", "\nA topology where each node is connected to every other node (i.e. a complete graph)." ], "metadata": {} }, { "cell_type": "code", "source": [ "fully_connected = f.createFullyConnected(NoAlgo,6)\n", "nx.draw(fully_connected, pos=nx.spring_layout(fully_connected,0.1,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 23, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Broadcast\n", "\nA collection of nodes not connected to each other but to a central node." ], "metadata": {} }, { "cell_type": "code", "source": [ "broadcast = f.createBroadcast(NoAlgo,6)\n", "nx.draw(broadcast, pos=nx.spring_layout(broadcast,0.1,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 24, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Hypercube\n", "\nA topology defined by the hypercube of dimension $N$, with $2^N$ verticies and $N\\cdot2^{N-1}$ edges." ], "metadata": {} }, { "cell_type": "code", "source": [ "hypercube = f.createHypercube(NoAlgo,4)\n", "nx.draw(hypercube, pos=nx.spring_layout(hypercube,0.1,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 25, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Watts-Strogats\n", "\nA Watts-strogats graph tends to exhibit small-world effects." ], "metadata": {} }, { "cell_type": "code", "source": [ "watts_strogatz = f.createWattsStrogatz(NoAlgo,num_nodes=16,k=8,p=0.1,seed=1)\n", "nx.draw(watts_strogatz, pos=nx.spring_layout(watts_strogatz,0.1,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 26, "metadata": {} }, { "cell_type": "markdown", "source": [ "## Erdős-Rényi\n", "\nThe 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." ], "metadata": {} }, { "cell_type": "code", "source": [ "erdos_renyi = f.createErdosRenyi(NoAlgo,num_nodes=16,p=0.5,seed=1)\n", "nx.draw(erdos_renyi, pos=nx.spring_layout(erdos_renyi,0.1,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 27, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Barabási-Albert\n", "\n", "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.\n", "\n", "### References:\n", "\nBarabási, A. L., & Albert, R. (1999). **Emergence of scaling in random networks**. *Science*, 286(5439), 509-512." ], "metadata": {} }, { "cell_type": "code", "source": [ "barabasi_albert = f.createBarabasiAlbert(NoAlgo,num_nodes=16,m=3,seed=1)\n", "nx.draw(barabasi_albert, pos=nx.spring_layout(barabasi_albert,0.1,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 28, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Extended Barabási-Albert\n", "\n", "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:\n", "\n", "1. Addition of *m* new edges with probability *p*\n", "2. Rewiring of *m* edges with probability *q*\n", "3. Addition of a new node with probability *1 - p - q*\n", "\n", "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$).\n", "\n", "### References:\n", "\nAlbert, R., & Barabási, A. L. (2000). **Topology of Evolving Networks: Local Events and Universality**. *Physical Review Letters* 85(24), 5234." ], "metadata": {} }, { "cell_type": "code", "source": [ "extended_barabasi_albert = f.createExtendedBarabasiAlbert(NoAlgo,16,m=3,p=0.3,q=0.1,seed=1)\n", "nx.draw(extended_barabasi_albert, pos=nx.spring_layout(extended_barabasi_albert,0.1,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 29, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## Extended Ageing Barabási-Albert\n", "\nIdentical 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](http://esa.github.io/pygmo/documentation/topology.html#PyGMO.topology.ageing_clustered_ba). 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)." ], "metadata": {} }, { "cell_type": "code", "source": [ "ageing_barabasi_albert = f.createAgeingExtendedBarabasiAlbert(NoAlgo,n=16,m=3,p=0.3,q=0.1,max_age=10,seed=1)\n", "nx.draw(ageing_barabasi_albert, pos=nx.spring_layout(ageing_barabasi_albert,0.1,random_state=0))\n", "matplotlib.pyplot.show()" ], "outputs": [], "execution_count": 30, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } } ], "metadata": { "kernelspec": { "name": "python3", "language": "python", "display_name": "Python 3 (built-in)" }, "kernel_info": { "name": "python3" }, "language_info": { "name": "python", "version": "3.6.3", "mimetype": "text/x-python", "codemirror_mode": { "name": "ipython", "version": 3 }, "pygments_lexer": "ipython3", "nbconvert_exporter": "python", "file_extension": ".py" } }, "nbformat": 4, "nbformat_minor": 4 }