M3C 2017 Homework 1

Due date/time: 2/11/2017, 11:59pm GMT

This project consists of a series of tasks related to a random-network growth model.

Getting Started: If needed, update your local copy of the course repo (sync and pull). The homework/hw1/ directory contains the file, hw1_template.py. Make a new directory outside of the course repo, and place a copy of the template file named hw1_dev.py in this new directory. Ultimately, the final file that you submit should be titled hw1.py. Browse through the dev file; there are a number of function headers, and you will have to add code for each of these functions as described below. First, however, you should add your name and 8-digit college id to the docstring at the top of the file.

We will consider a network generation model where a new node undergoes a two-dimensional biased random walk and sticks to an existing node when the distance between the two nodes is below a threshold, \(d^*\). You will develop code to simulate this model, and analyze the resulting networks. Further details are provided below.

0. (5 pts) You should develop your code in a new git repository. If using Bitbucket, the online repo must be private. You should make at least a few commits as you work through the assignment. Once you have completed the assignment, generate a text file, hw1.txt at the command line in a Unix terminal which contains the log for your repo. Edit the file so that the first line contains the command used to first generate the file.

1.(15 pts) One step of a 2-D biased random walk for a particle with position \(X_i,Y_i\) is defined here as:

\[ \begin{align}\begin{aligned}X_{i+1} = X_i + \mathcal{P}_i\\Y_{i+1} = Y_i + \mathcal{Q}_i.\end{aligned}\end{align} \]

\(\mathcal{P}_i\) is a random number which is either \(1+\alpha\) or \(-1\) with equal probability. Similarly, \(\mathcal{Q}_i\) is a random number which is either \(1-\beta\) or \(-1\) with equal probability. \(\mathcal{P}_i\) and \(\mathcal{Q}_i\) are independent of each other, and they are independent of \(\mathcal{P}_j\) and \(\mathcal{Q}_j\) when \(j \neq i\). The constants \(\alpha\) and \(\beta\) are integers which control the amount of bias in the X- and Y-directions, and we require \(\alpha \geq -1\) and \(\beta \leq 1\)

Complete rw2d so that it carries out M simulations of this model, each with Nt time steps. The initial position for each simulation should be \((X_0,Y_0) = (0,0)\). The function should return 5 quantities, \(<X>, <Y>, <X^2>, <Y^2>, \rm{and} <X Y>\) which are ensemble averages over the M simulations calculated at each time step (including the initial condition):

\[ \begin{align}\begin{aligned}<F>_i = \frac{1}{M} \sum_{j=1}^M F_i^{(j)},\\<F> = [<F>_0, <F>_1, <F>_2, ...]\end{aligned}\end{align} \]

and \(F_i^{(j)}\) is the ith time step of the jth simulation of F.

2. (30 pts) You will now develop code to simulate a new network generation model. First, a seed node is placed at (X,Y)=(0,0). Then, a new node is introduced at (X,Y) = (0,H) where H is a positive input parameter. This new node undergoes a biased 2-D random walk with \(\beta=1\), \(\alpha \in \{-1,0,1\}\) and which terminates when either: 1) the node reaches Y=0 or 2) the node passes within a distance, \(d^*=\sqrt{1 + (1+\alpha)^2}\) of the first node. In the latter case, node 2 will have linked to node 1. This process is then repeated with new nodes being introduced one at a time at (0,H) and linking when they pass within \(d \leq d^*\) of any other nodes in the network (and otherwise stopping at Y=0). Network generation stops when a node is added to the network at height, \(Y \geq Hf\) (with Hf specified as an input parameter). Notes: 1) You may assume that H and Hf are integers with \(1<Hf \leq H-3\); 2) A new node is introduced only when the previous node has completed its random walk and has thus been added to the network.

i) Complete the function rwnet1 and implement this model. The function should return the coordinates of the nodes in the final network in the variables X and Y. When the input variable display is True, a well-made figure should be created which displays the network. Typical parameter values to try are \(H=500\), \(Hf=300\) though you may wish to choose smaller heights while developing your code.

ii) Now consider a modified version of this model where vertical ‘walls’ are placed at \(X = \pm L\). During a random walk, any step attempting to take a node across a wall should be modified to place the node’s horizontal position at the wall. Add code to rwnet2 so that it implements this modified model, but whose functionality (input, output, figure generation) is otherwise identical to rwnet1.

3. (25 pts) Investigate and analyze the rate at which network height increases during simulations. Fix the heights to be \(H=200\) and \(Hf=150\). You should analyze the influence of bias with \(\alpha=0,1\) and the influence of walls with \(L=\infty,30,150\). Add code to the function analyze which generates 1-3 figures which clearly illustrate the most important trends. In the docstring for analyze, clearly and concisely explain: 1) what quantity/quantities are displayed in the figure(s), 2) the trends that you are displaying, and 3) the significance of these trends (i.e. what is causing them and how they effect the networks). Save your figures as .png files with the names hw11.png, hw12.png, hw13.png and submit them with your codes.

4. (25 pts) Now, you will develop a function which converts a set of ‘network coordinates’, \(X,Y\), into a conventional network with numbered nodes and links. Given a set of node coordinates stored in two numpy arrays, \(X\) and \(Y\), a link is placed between any two nodes that are within a distance, \(d \leq d^*\), of each other. The function, network, takes \(X\), \(Y\), and \(d^*\) as input. Nodes that do not link to any other nodes should be discarded. Add code to the function so that it generates the corresponding NetworkX graph and returns it. If the input variable display is true, a figure of the graph should be displayed. If degree is true, the degree distribution for the graph should be computed, displayed, and returned. In the function’s docstring, concisely explain how the graph is created.

This network model has a clear weakness in that the maximum degree is constrained to a small value. In the docstring for network, concisely describe how the model could be modified to alleviate this weakness. Also explain if your modification(s) require any substantial changes to rwnet2 or network

Note: All figures created by your code should be well-made and properly labeled. The title of each figure should include your name and the name of the function which created it.

Submitting the assignment

To submit the assignment for assessment, go to the course blackboard page, and click on the “Assignments” link on the left-hand side of the page, and then click on Homework 1. Click on “Write Submission” and add the statement: “This is all my own unaided work unless stated otherwise.” If you are a CDT student, add a 2nd line with “CDT Fluids”, or “CDT Neuro” as appropriate.

Click on “Browse My Computer” and upload your final files, hw1.txt, hw1.py, hw11.png, hw12.png, etc… . Finally, click “Submit”.