Assignment 1 (CS 4984: Computing the Brain)
Deadline: 11:59pm, February 27, 2018

1. Write a function generate_watts_strogatz_graph to generate randomised ring graphs using the Watts-Strogatz model. The function should take three parameters: \(n\), \(k\), and \(p\). Here \(n\) is the number of the nodes in the network, \(k\) is the degree of each node, and \(p\) is a probability between \(0\) and \(1\). The parameters \(n\) and \(k\) are integers and \(k\) can be even. A single call to this function should create an undirected, regular, ring graph with \(n\) nodes and \(nk/2\) edges, and then rewire every edge with probability \(p\), as described in the caption of Figure 1 of Collective dynamics of 'small-world' networks. Recall that in a regular graph, all nodes have the same degree. Therefore, in this graph, each node has degree \(k\). Implement this function yourself. Do not use a ready-made implementation in some other package or library.
2. You will need two other functions that compute the average shortest path length \(l(n, k, p)\) and the clustering coefficient \(c(n, k, p)\) of an undirected graph with these parameters. You can use existing implementations of these methods or their building blocks, e.g., a function that computes the shortest path between a pair of nodes or all-pairs shortest paths, e.g., in the NetworkX library in Python. Be careful about blindly using these methods without considering the running time.

3. Invoke this function with 20 different values of \(p\) and the following values of \(n\) and \(k\):

   1. \(n=100\), \(k=20\).
   2. \(n=1,000\), \(k=20\).
   3. \(n=5,000\), \(k=20\). This graph will require about \(12.5\times 10^6\) shortest path computations. If you develop some heuristics for estimating the average shortest path length efficiently, provide some evidence convincing me that your estimates are good.

   Experiment with two different sets of choices of values of \(p\): (a) \(0.05 \times l\), where \(l\) takes the value of every integer between \(1\) and \(20\) and (b) \(x^l\), where \(x\) is suitably chosen between 0 and 1 and \(l\) has the same range as before. Make a sensible choice of \(x\) and justify it.

4. For each value of \((n, p, k)\), try at least 10 runs. Your goal is to regenerate Figure 2 of Collective dynamics of 'small-world' networks for each \((n, k)\) pair, while also plotting the average and standard deviations of \(l(n, k, p)/l(n, k, 0)\) and \(c(n, k, p)/c(n, k, 0)\). The paper did not plot the standard deviations.

In this problem, you will analyze specific brain connectomes for their small-world properties. The networks you will consider are the following. The first five networks are from the Brain Connectivity Toolbox:

• the coactivation graph from "Cognitive relevance of the community structure of the human brain functional coactivation network", Crossley et al, PNAS, 2013.
• Macaque cortex, abbreviated "MC" in The small world of the cerebral cortex.
• The fve30 version of the macaque visual cortex, abbreviated "MVC" in The small world of the cerebral cortex.
• Macaque large-scale visual and sensorimotor area corticocortical connectivity from Network structure of cerebral cortex shapes functional connectivity on multiple time scales by Honey et al.
• The cj.all version of the connectome of the cat cortex abbreviated "CC" in The small world of the cerebral cortex.
• The weighted and directed interareal connectome for the macaque cerebral cortex used in Cortical High-Density Counterstream Architectures. Parsing this dataset and creating a graph from it will require some thought and specific decisions. Feel free to discuss using the class mailing list on Canvas.

1. For each of these graphs, compute the average shortest path length and the average clustering coefficient. Display both values for all six networks on a single plot.
2. Separately for each network, plot a histogram of the average shortest path length from each node (to every other node) and the clustering coefficient of each node. You can show two plots here, two for each network. Alternatively, you can show one plot for each network, where you show both distributions in a nice way.
3. For each graph \(G\), compute the values \(\sigma(G)\) and \(\omega(G)\). You will have to make decisions on how to compute the relevant values in the formulae for random E-R graphs and random lattices. Explain your procedure for these calculations.

Turn in a typeset (not handwritten) report describing your results and plots for each problem. Mention any difficulties you encountered and how you addressed them. Were there any surprises, i.e., results or trends you did not expect? I am also curious to find out what you learnt from this assignment.