NetworkGenerator.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Adrian Soto\n",
    "# 2016-09-13\n",
    "# Institute for Advanced Computational Science\n",
    "# Stony Brook University\n",
    "#\n",
    "# Code to generate networks for\n",
    "# IACS challenge at Tapia16\n",
    "\n",
    "import numpy as np\n",
    "from random import randint\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def genStarNet(N):\n",
    "# Generate star graph with N nodes.\n",
    "# i==0 is the central node\n",
    "\n",
    "    # Initialize adjacency matrix\n",
    "    A=np.zeros((N,N))\n",
    "\n",
    "                \n",
    "    # %%%   Constructing the network   %%%\n",
    "    for i in range(1,N):\n",
    "        A[0][i]=1    \n",
    "\n",
    "        # Symmetrize and return\n",
    "    return A + np.transpose(A)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def genBrdcRcvNet(Nb, Nr):\n",
    "#\n",
    "# Generate broadcasters-receivers network\n",
    "# with Nb broadcasters and Nr receiver nodes.\n",
    "# \n",
    "\n",
    "    # Initialize adjacency matrix\n",
    "    A=np.zeros((Nb+Nr,Nb+Nr))\n",
    "    \n",
    "    # %%%   Constructing the network   %%%\n",
    "    for ib in range(0,Nb):\n",
    "        for ir in range(Nb,Nb+Nr):\n",
    "            A[ib][ir]=1    \n",
    "\n",
    "        # Symmetrize and return\n",
    "    \n",
    "    return A + np.transpose(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def board2ind(i,j):  \n",
    "    # CHESSBOARD k indices for A\n",
    "    \n",
    "    #\n",
    "    #  /j  0  1  2  3  4  5  6  7 \n",
    "    # i\\\n",
    "    # 0|   0  1  2  3  4  5  6  7\n",
    "    # 1|   8  9 10 11 12 13 14 15\n",
    "    # 2|  16 17 18 19 20 21 22 23\n",
    "    # 3|  24 25 26 27 28 29 30 31\n",
    "    # 4|  32 33 34 35 36 37 38 39\n",
    "    # 5|  40 41 42 43 44 45 46 47\n",
    "    # 6|  48 49 50 51 52 53 54 55\n",
    "    # 7|  56 57 58 59 60 61 62 63\n",
    "    # \n",
    "    \n",
    "    return 8*i+j\n",
    "\n",
    "\n",
    "def ind2board(k):\n",
    "    # For a given index k in (0,64), give\n",
    "    # the corresponding i,j indices on the\n",
    "    # 8x8 lattice.\n",
    "    j=k%8\n",
    "    i=k//8\n",
    "    return i,j\n",
    "\n",
    "\n",
    "\n",
    "def genKnightNet():\n",
    "#\n",
    "# Generate network of knight-jump connected \n",
    "# chessboard cells.\n",
    "#\n",
    "# (1) Find allowed DOWNWARD moves (increasing i) \n",
    "#     on the 8x8 lattice and populate the corresponding \n",
    "#     entries of the adjacency matrix\n",
    "# (2) Symmetrize A (i.e. account for UPWARD moves)\n",
    "#\n",
    "\n",
    "        \n",
    "    N=64     # num of nodes in entire network\n",
    "    # Initialize adjacency matrix\n",
    "    A=np.zeros((N,N))\n",
    "\n",
    "    \n",
    "\n",
    "                \n",
    "    # %%%   Constructing the network   %%%\n",
    "    # Types of downward move: RRD, LLD, RDD, LDD\n",
    "    # \n",
    "    # Loop across entire chess board, starting from upper \n",
    "    # left corner and to the right.\n",
    "    for i in range(0,8):\n",
    "        for j in range(0,8):\n",
    "            k=board2ind(i,j)\n",
    "            \n",
    "            \n",
    "            # RRD\n",
    "            iaux=i+1\n",
    "            jaux=j+2\n",
    "            if (iaux<=7 and jaux<=7):\n",
    "                kaux=board2ind(iaux,jaux)\n",
    "                A[k][kaux]=1\n",
    "            \n",
    "            # LLD\n",
    "            iaux=i+1\n",
    "            jaux=j-2\n",
    "            if (iaux<=7 and jaux>=0):\n",
    "                kaux=board2ind(iaux,jaux)\n",
    "                A[k][kaux]=1\n",
    "            \n",
    "            # RDD\n",
    "            iaux=i+2\n",
    "            jaux=j+1\n",
    "            if (iaux<=7 and jaux<=7):\n",
    "                kaux=board2ind(iaux,jaux)\n",
    "                A[k][kaux]=1\n",
    "            \n",
    "            # LDD\n",
    "            iaux=i+2\n",
    "            jaux=j-1\n",
    "            if (iaux<=7 and jaux>=0):\n",
    "                kaux=board2ind(iaux,jaux)\n",
    "                A[k][kaux]=1\n",
    "            \n",
    "\n",
    "        # 2. Symmetrize and return\n",
    "    return A + np.transpose(A)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def join2Nets(A1,A2):\n",
    "    # \n",
    "    # Join two networks defined by \n",
    "    # adjacency matrices A1 and A2\n",
    "    #  ⎡A1 0⎤\n",
    "    #  ⎣0 A2⎦\n",
    "    #\n",
    "    N1=np.shape(A1)[0]\n",
    "    N2=np.shape(A2)[0]\n",
    "    # Ensure adjacency matrices are diagonal\n",
    "    if (N1 != np.shape(A1)[1]):\n",
    "        print \"join2Nets -- ERROR: A1 not diagonal\"\n",
    "        exit()\n",
    "    if (N2 != np.shape(A2)[1]):\n",
    "        print \"join2Nets -- ERROR: A2 not diagonal\"\n",
    "        exit()\n",
    "        \n",
    "    \n",
    "    # Construct block diagonal matrix\n",
    "    \n",
    "    # First construct the 01 and 10 rectangular\n",
    "    # zero matrices\n",
    "    Z01=np.zeros((N1,N2))\n",
    "    Z10=np.zeros((N2,N1))\n",
    "    \n",
    "    # Combine\n",
    "    Atop   =np.append(A1,Z01, axis=1)\n",
    "    Abottom=np.append(Z10,A2, axis=1)\n",
    "    A=np.append(Atop, Abottom, axis=0)\n",
    "    \n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def genLayNet(M,L,E):\n",
    "#\n",
    "# Generate layered network\n",
    "# Construct model single-product commercial distribution network.\n",
    "# The network is unweighted and undirected, so we will \n",
    "# work on upper triangle and symmetrize in the end.\n",
    "#\n",
    "# (1) Edges between layers 1 and 2: manufacturer-warehouse\n",
    "#     condition: each manufacturer only trades the product with one warehouse\n",
    "# (2) Edges between layers 2 and 3: warehouse-retail\n",
    "#     condition: each retailer only trades the product with one warehouse\n",
    "# (3)\n",
    "#\n",
    "# (4)\n",
    "\n",
    "# Variables:\n",
    "#    Nmnf: num of manufacturers\n",
    "#    Nwrh: num of warehouses\n",
    "#    Nshp: num of shops\n",
    "#    Ncst: num of costumers\n",
    "#\n",
    "#    M: number of layers\n",
    "#    L: np.array of length M containing num of nodes on each layer\n",
    "#    E: np.array of length M-1 containing num of edges between all layers\n",
    "#\n",
    "#\n",
    "\n",
    "    \n",
    "\n",
    "    if (M != L.size):\n",
    "        print \"ERROR: number of layers and size of array L don't match. EXIT\"\n",
    "        exit()\n",
    "\n",
    "        \n",
    "    N=sum(L)     # num of nodes in entire network\n",
    "\n",
    "    \n",
    "    # Initialize adjacency matrix\n",
    "    A=np.zeros((N,N))\n",
    "\n",
    "            \n",
    "    \n",
    "    # %%%   Constructing the network   %%%\n",
    "    \n",
    "    \n",
    "    # Since all nodes are labeled by their entry in A,\n",
    "    # get the Left and Right boundaries of each layer.\n",
    "    Lnodes=np.concatenate( ( np.array([0]), np.cumsum( L[0:M-1]) ) )\n",
    "    Rnodes=Lnodes + L - 1\n",
    "    \n",
    "    \n",
    "    # Loop over layers. We generate the nodes downstream so,\n",
    "    # iterate from first layer to second last one.\n",
    "    for iL in range(0,M-1):\n",
    "        \n",
    "        if (E[iL] > L[iL]*L[iL+1]):\n",
    "            print \"WARNING!! Too many edges for this layer have been requested\"\n",
    "            print \"          Number of nodes top layer       =\", L[iL]\n",
    "            print \"          Number of nodes bottom layer    =\", L[iL]\n",
    "            print \"          Number of possible edges        =\", L[iL]*L[iL+1]\n",
    "            print \"          Number of requested edges       =\", E[iL]\n",
    "            print \"          These two layers will have a max of \", L[iL]*L[iL+1], \" edges\"\n",
    "            print \" \"\n",
    "        \n",
    "        # Find left and right edges of top and bottom layers\n",
    "        iTL=Lnodes[iL]\n",
    "        iTR=Rnodes[iL]\n",
    "        iBL=Lnodes[iL+1]\n",
    "        iBR=Rnodes[iL+1]\n",
    "        \n",
    "        \n",
    "        # Loop inside top layer and assign edges downstream\n",
    "        # onto the bottom layer following a random distribution.\n",
    "        # STEPS:\n",
    "        #    0. shuffle top and bottom layer index arrays\n",
    "        #    1. assign one edge to each node sequentially, so that\n",
    "        #       all nodes have at least one edge. Start from a random\n",
    "        #       position on the layer.\n",
    "        #    2. Shuffle T and B index arrays again\n",
    "        #    3. Add aditional edges until run out. Draw random pairs\n",
    "        #       of integers from top and bottom layers, each pair\n",
    "        #       forming an edge.\n",
    "        #    4. Symmetrize A\n",
    "\n",
    "        # 0. \n",
    "        \n",
    "        EdgesRemaining=E[iL]\n",
    "        Tnodes = np.arange(iTL,iTR+1)\n",
    "        np.random.shuffle(Tnodes)\n",
    "        Bnodes = np.arange(iBL,iBR+1)\n",
    "        np.random.shuffle(Bnodes)\n",
    " \n",
    "        # 1. Wire all nodes with at least one edge\n",
    "        if (E[iL] < max(L[iL], L[iL+1])):\n",
    "            print \"ERROR -- not enough edges to make network fully connected. EXITING...\"\n",
    "            exit()\n",
    "        else:\n",
    "            for i in range(0,max(L[iL], L[iL+1])):\n",
    "                # If index gets larger than layer size, \n",
    "                # loop around and get back to beginning.\n",
    "                if (i//L[iL]>0):\n",
    "                    iT=Tnodes[i-(i//L[iL])*L[iL]]\n",
    "                else:\n",
    "                    iT=Tnodes[i]\n",
    "                \n",
    "                if (i//L[iL+1]>0):\n",
    "                    iB=Bnodes[i-(i//L[iL+1])*L[iL+1]]\n",
    "                else:\n",
    "                    iB=Bnodes[i]\n",
    "                \n",
    "                # Add edge\n",
    "                A[iT][iB]=1\n",
    "        \n",
    "                EdgesRemaining -= 1 # max(L[iL], L[iL-1])\n",
    "            \n",
    "\n",
    "        \n",
    "        \n",
    "        # 2. Shuffle again\n",
    "        np.random.shuffle(Tnodes)\n",
    "        np.random.shuffle(Bnodes)\n",
    "\n",
    "                \n",
    "        # 3. Include remaining edges\n",
    "        \n",
    "        # Find node indices\n",
    "        if (iTL==iTR):\n",
    "            Tind=np.array([iTL])\n",
    "        else:\n",
    "            Tind=np.random.randint(iTL,iTR, EdgesRemaining)\n",
    "        \n",
    "        if (iBL==iBR):\n",
    "            Bind=np.array([iBL])\n",
    "        else:\n",
    "            Bind=np.random.randint(iBL,iBR, EdgesRemaining)\n",
    "        \n",
    "        # Add edges\n",
    "        for i in range(0,EdgesRemaining):\n",
    "            A[Tind[i]][Bind[i]]=1\n",
    "        \n",
    "\n",
    "        # 4. Symmetrize and return\n",
    "    return A + np.transpose(A)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Create multilayer network\n",
    "L=np.array([10, 3, 10, 41])\n",
    "E=np.array([10, 20, 100])\n",
    "A=genLayNet(4,L,E)\n",
    "np.savetxt('4layer_network.dat', A, fmt='%.1i')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Create knight jump network\n",
    "A=genKnightNet()\n",
    "np.savetxt('knightjump_network.dat', A, fmt='%.1i')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Create star network (better known as star graph)\n",
    "A=genStarNet(64)\n",
    "np.savetxt('star64_network.dat', A, fmt='%.1i')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Create a broadcasters-receivers network\n",
    "# with Nb broadcasters and Nr receivers.\n",
    "Nb=4\n",
    "Nr=60\n",
    "A=genBrdcRcvNet(Nb, Nr)\n",
    "np.savetxt('4broadcasters_network.dat', A, fmt='%.1i')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Create multi-gang network based on \n",
    "# 2 Barabasi-Albert networks, often used\n",
    "# for simulating social networks. \n",
    "\n",
    "# In this example we have 3-gangs. We construct\n",
    "# 3 BA networks and then we join them. \n",
    "#\n",
    "# Each BA network can be modeled with 2 parameters:\n",
    "#    N: Number of nodes\n",
    "#    C: \n",
    "\n",
    "# Parameter choice. Ensure N1+N2+N3=64\n",
    "N1=20\n",
    "C1=7\n",
    "N2=16\n",
    "C2=C1\n",
    "N3=64-N1-N2\n",
    "C3=C1\n",
    "\n",
    "Gg1=nx.barabasi_albert_graph(N1,C1)\n",
    "Ag1=nx.to_numpy_matrix(Gg1)\n",
    "\n",
    "Gg2=nx.barabasi_albert_graph(N2,C2)\n",
    "Ag2=nx.to_numpy_matrix(Gg2)\n",
    "\n",
    "Ag12=join2Nets(Ag1, Ag2)\n",
    "\n",
    "Gg3=nx.barabasi_albert_graph(N3,C3)\n",
    "Ag3=nx.to_numpy_matrix(Gg3)\n",
    "\n",
    "Ag=join2Nets(Ag12, Ag3)\n",
    "\n",
    "Gg=nx.from_numpy_matrix(A)\n",
    "\n",
    "np.savetxt('3gangs_network.dat', Ag, fmt='%.1i')\n"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}