Programming

Continuous Assessment 2

This continuous assessment (CA) comprises 25% of the overall module assessment.

This is an individual exercise and your attention is drawn to the College and University guidelines

on collaboration and plagiarism, which are available from the College website.

Note that both paper (BART) and electronic submissions are required.

This CA tests your knowledge of the programming in Python that we have covered so far. You

may not be able to do all of the exercises initially, but we will cover the necessary material over

the next weeks.

Make sure that you lay your code out so that it is readable and you comment the code appropriately.

Exercises

1 Logistic maps

The logistic map (1) has been created to model growth and death rates of species. It is a fully

deterministic map that depends on a single scalar parameter. If you are interested in knowing

more about the logistic map and its use in various applied sciences, please take a look here:

https://en.wikipedia.org/wiki/Logistic map.

Further studies highlighted the surprising behaviour of the map for specific configurations of its

control parameter. In particular, the series of real values generated with such map can vary from

a perfectly period behaviour (i.e., a series of numbers with very regular behaviour) to a chaotic

series, that is, a series with very disordered, apparently random behaviour. In formulas, the logistic

map reads:

yt+1 = pyt(1 − yt); (1)

where yt 2 [0; 1]; t = 0; 1; : : : ; T, being T > 0 the number of steps, and p is a positive, real-valued

parameter, whose range is limited to the (0; 4] interval (please note that 0 is excluded).

Write a Python program that implements the logistic map (1). Your code should contain a function

called logistic map(initial condition, steps=100, p=3.0) that returns a series and then do

the following:

1. Iterate the map for a given number of times T > 0 by using each of the following parametrizations: p 2 f3:0; 3:4; 3:6785; 3:84; 4g. For each

parametrization, initialize the map with a

random, uniformly distributed number in the unit interval, i.e., y0 2 [0; 1].

2. Plot the obtained series in a nice graph to visualize the differences of the generated series

with respect to the parametrizations taken into account.

HINT: Very nice plotting functionalities are available by importing import matplotlib.pyplot

as plt. You might need to install matplotlib. Please consult the online documentation to findECM1400 Programming Continuous Assessment 2

out how to plot a series of numbers (https://matplotlib.org/users/pyplot tutorial.html) or

take a look at what has been done during the workshops.

Your program should be in a file called logisticmap.py. You should submit:

• A copy of your logisticmap.py program (electronic submission).

• Hardcopy of your logisticmap.py program (paper submission, via BART).

• Hardcopy of the output of your logisticmap.py program and screen shots of the five related

trajectories (paper via BART).

[20 marks]

2 Horizontal visibility graph

A graph is typically described as a pair of vertices (also called nodes) and edges (also called links)

{ see Figure 1 for an example.

Figure 1: A sample graph with five vertices numbered from 0 to 5 and five (undirected) edges

describing their connections.

A graph can be described by a binary, square matrix called adjacency matrix, which we will denote

as A. If the graph possesses n vertices, then A is an n × n binary matrix (note that binary means

that A contains only of 0s and 1s). The adjacency matrix associated to the graph shown in Figure

1 is:

A =

266664

0 0 1 0 1

0 0 1 0 1

1 1 0 0 0

0 0 0 0 1

1 1 0 1 0

377775

(2)

Rows and columns are one-to-one mapped with the vertex identifiers. In our example above, the

first row/column is associated vertex with id 0; the second row/column with the vertex with id 1

and so on. Considering the first row, we notice that there is a 1 at the third and fifth columns of A,

indicating that vertex with id 0 is connected to vertices with id 2 and 4 (as in fact is shown in Figure

1). Each matrix element can be identified by using two indices, say i and j, indexing the rows and

columns of A, respectively. For instance, A[i; j] with i = 0 and j = 4 refers to element located in the

first row and fifth column, that is, 1 in our example above; on the other hand, when i = 1 and j = 3

we are pointing to 0. It is should be easy for you to recognize that such a matrix is symmetric”,

that is, if vertex 0 is connected with 2, then vertex 2 is also connected to 0. If you want to know more

about graphs, please read: https://en.wikipedia.org/wiki/Graph (discrete mathematics)

2ECM1400 Programming Continuous Assessment 2

Figure 2: A sample horizontal visibility graph with 10 vertices corresponding to the 10 numbers

composing the series. Edges connecting the vertices are shown as horizontal black lines with arrows.

A horizontal visibility graph (HVG) is a special type of graph that is used to describe series of

numbers (also called time series in many scientific disciplines). An HVG is associated with a finite

univariate series x = (xt)T t=1 of length T > 0, and is constructed by assigning a vertex/node vt to

each datum xt; t = 1; 2; : : : ; T , in the series. Its adjacency matrix A is computed according to the

following simple rule: two vertices vi and vj, i 6= j are connected by an edge (A[i; j] = 1) if and

only if the corresponding data satisfy

xi; xj > xp; for all i < p < j: (3)

A visual illustration of the above rule in shown in Figure 2, where a series of ten real-valued numbers

in [0; 1] is mapped to its corresponding HVG. Please notice that two adjacent elements on the series

are always assumed to be connected (e.g., the first one is always connected to the second one, the

second one to the third one and so on; see the example in Figure 2). Here, in order to improve

visualization and understanding of the rule, data points (i.e., the vertices of the horizontal visibility

graph) are visualized as vertical bars in red and their edges are shown as horizontal black lines.

A weighted HVG (wHVG) is a regular HVG that instead of having binary edge values, it contains

real values defined as follows:

A[i; j] = 1=q(j − i)2 + (xi − xj)2 2 [0; 1]: (4)

Since self-loops (i.e., edges connecting a vertices with itself) are forbidden in HVGs, edge weights

are always well-defined in Eq. 4. The use of weights permits to capture additional information, as

it accounts for distance along the sequence (j − i) and amplitude differences (xi − xj) of two data

points connected by the visibility rule (3).

Write a Python program implementing what follows:

1. Generate three series of numbers: (1) a monotonically increasing series, (2) an alternating

series, and (3) a sinusoid. For this task, write a function get series(n, stype=0) that takes

two arguments, the first specifying the length of the series and the second one identified the

3ECM1400 Programming Continuous Assessment 2

type of function to generate. The function should return the generated series. A monotonically increasing series of length four is, for

instance, 0, 1, 2, 3. A valid alternating series of

length seven can be defined as follows 1, 0, 1, 0, 1, 0, 1. Finally, a sinusoidal series yt should

be generated according to the following equation:

yt = sin(2π · f · xt=fs);

where sin(·) is the built-in sine function, f specifies the frequency of the sinusoid (in Hertz,

may be float), fs specifies the sampling rate (must be integer), · indicates standard multiplication operation between numbers, and finally, xt

is an integer value going from x0 = 0 to

xT −1 = T − 1 with unitary increments (T as usual denotes the desired length of the series).

In your program, use f = 500 and fs = 10000.

2. Compute horizontal visibility graphs associated to such functions. To this end, write a function horizontal visibility graph(series,

weighted=False) that takes as input a series

of real-valued numbers and returns the adjacency matrix associated to the HVG computed

according to (3). DO NOT use any scientific library for manipulating vectors and matrices,

such as numpy; use only built-in functionalities for constructing adjacency matrices.

HINT: Take a look at the way a list of lists works: it can easily used to implement a (square)

matrix.

3. Print the horizontal visibility graphs associated with the three series on the console as square

matrices. To this end, write a function print hvg(hvg) that takes an adjacency matrix and

prints out each row of the matrix to the console, printing either a space if an element of row is

0, else printing its value. Please, compute and print the weighted edges (weighted adjacency

matrix) only in the alternating function case.

4. Instantiate the logistic map (1) with the previous parametrizations (i.e., f3:0; 3:4; 3:6785; 3:84; 4g)

and construct related horizontal visibility graphs. Create a dictionary associating logistic

map parametrizations and related horizontal visibility graphs. To this end, write a function process logisticmap(params, steps=100) that returns

a dictionary containing the

aforementioned key/value pairs.

5. In the main of your program, print the key/value pairs in the dictionary by showing the

horizontal visibility graph (without weights) associated to each parametrization of the logistic

map.

Your program should be in a file called hvg.py. You should submit:

• A copy of your hvg.py program (electronic submission).

• Hardcopy of your hvg.py program (paper submission, via BART).

• Hardcopy of the output of your hvg.py program (paper via BART).

[40 marks]

3 Random walks on graphs

Let G be a graph with n vertices. As before, let us denote with A its adjacency matrix, encoding

the links (i.e., the edges) between the vertices of G. A walk in G is a sequence of vertices. For

instance, considering the graph shown in Figure 1, a possible walk of length four is (0; 2; 1; 4; 0)

as the graph G contains those four edges: f0; 2g; f2; 1g; f1; 4g; f4; 0g, allowing to perform the four

steps of the walk. This can be easily verified by visually inspecting the figure or by looking at the

4ECM1400 Programming Continuous Assessment 2

configuration of the 1s in the corresponding adjacency matrix (2). Please notice that (i) as before

vertex identifiers start from 0 and (ii) a walk does not need to start and end at the same vertex as

in the previous example (that’s actually called a cycle).

A random walk in G is walk where the transitions between two vertices are non-deterministic, that

is, they are governed by a probabilistic rule that can be fully inferred from the adjacency matrix.

Such rules of transition between vertices are encoded in another matrix, called transition matrix

T. Following the same example in Figure 1, the transition matrix of the sample graph G is:

T =

266664

0 0 0:5 0 0:5

0 0 0:5 0 0:5

0:5 0:5 0 0 0

0 0 0 0 1:0

0:33 0:33 0 0:33 0

377775

(5)

The transition matrix shown in (5) is easy to interpret. For instance, assuming we start from vertex

0 (corresponding to the first row of T), we have equal chances to moving to either vertex 2 or 4.

Said in other terms, there is a probability equal to 0.5 to transition to vertex 2 and 0.5 toward

vertex 4. The same holds for vertex 1; in fact, first and second rows are equal. On the other hand,

assuming we are in vertex 3, we are forced to deterministically move (i.e., move with probability 1)

toward vertex 4. Please notice that, differently from A in Eq. 2, transition matrices are not always

symmetric!

Each component Tij of the transition matrix (5) can be easily computed as follows:

Tij =

Aij

di ; (6)

where Aij is the related component in the adjacency matrix and di = Pn j=0 −1 Aij is called degree of

the ith vertex. In other terms, the degree of vertex i is given by the number of edges connected to

vertex i.

Now we know how to move around the graph by using the transition matrix. A reasonable question

would be where should we start our random walk?” The answer to such a question is given by

the so-called initial vertex distribution. The initial vertex distribution of a graph with n vertices is

a vector p of n components that encodes the a-priori probability of being in each vertex. Said in

other terms, the first component of p, denoted as p0 or p[0] in Python, contains the probability of

starting our random walk from vertex 0; the second component contains the probability of starting

from vertex with id 1 and so on. Something you should keep in mind is that, being p a distribution

over the vertices, the sum of its components should be 1; take it for granted for now, you will go

back to these things later on, probably during your second/third academic year as undergrad. How

do we compute p? The initial vertex distribution can be easily computed as follows:

pi =

di

Pn j=0 −1 dj : (7)

Everything we said so far is useful to perform the so-called unbiased random walks on graphs, which

is the standard” way to perform random walks. However, it is possible to bias the transitions

toward vertices having a high/low number of incident edges, i.e., with high/low degree. This can

be achieved by means of the so-called biased random walks. The underlying idea remains exactly

5ECM1400 Programming Continuous Assessment 2

the same. We just need to change the way we compute the transition matrix (6) and the initial

vertex distribution (7). Notably, in the biased random walks case, (6) is updated as follows:

Tij =

Aijdα j

Pn k=0 −1 Aikdα k ; (8)

where α is a parameter: when α > 0 we prefer vertices having a large number of edges; whereas

α < 0 indicates preference toward vertices with a low number of edges. When α = 0, it is easy to

understand that (8) becomes equal to (6). Please notice that the notation dα l indicates: the value

dl raised to the power of α. Finally, in the biased random walks case, (7) is updated as follows:

pi =

cidα i

Pn k=0 −1 ckdα k ; (9)

ci =

n−1

X j

=0

Aijdα j : (10)

Write a Python program implementing the following functionalities:

1. Define a function called get graph from series(length=25) that generates a numeric series

of length 25 from the logistic map with 0.1 as initial condition and its controlling parameter

set to 4. Such a function should then compute the horizontal visibility graph associated to

such a series and return its adjacency matrix.

2. Define a function called random walk(adj matrix, steps=1000, biased=False, alpha=1.0)

that allows to perform both standard and biased random walks on graphs encoded in the adjacency matrix passed as argument. Your function should

return a list of visited vertices

(i.e., their numeric identifiers). Perform both unbiased and biased random walks of 200 steps;

α = 5 as bias parameter on the adjacency matrix obtained in Question 3.1.

HINT: Here, you should probably use the choose vertex(probability) downloaded from

the module website. However, please feel free to re-implement the function from scratch if

you prefer.

3. Define a function called print triplets(visited vertices, k=20) that takes a list of visited vertices and prints triplets of them, limiting

this to the first k if there are more than k

to print. For instance, if visited vertices are 0, 1, 2, 3, then your function should print [0,

1, 2], [1, 2, 3]. Print the first 20 triplets from the biased and unbiased random walks

carried out in Question 3.2.

4. Write a function called verify equality(adj matrix) that performs a routine check (i.e., a

sort of debugging). In particular, it should evaluate whether the code you wrote for computing

a biased transition matrix produces a standard, i.e., unbiased transition matrix when α = 0.

5. Write a function that prints histograms of vertex degrees of the generated graph. So, for

example if we assume the following sample adjacency matrix, we would obtain:

>>> a = [[0 , 1, 1], [1, 0, 0], [1, 0, 0]]

>>> print_degree_histogram (a)

Vertex ID 0: **

Vertex ID 1: *

Vertex ID 2: *

Apply this function to the adjacency matrix generated in Question 3.1.

6ECM1400 Programming Continuous Assessment 2

6. Write a function count vertex occurrence(visited vertices) that counts the occurrences

of vertices in a random walk. Such a function should use a dictionary to store only the

occurrences of vertices visited during the random walks. Print the resulting vertex occurrences

for both the biased and unbiased random walks carried out in Question 3.2 and observe the

differences! In the biased case, vertices having high degree should occur much more than in

the unbiased case.

The main of you program should test all such functionalities and produce outputs accordingly.

Your program should be in a file called rw.py. You should submit:

• A copy of your rw.py program (electronic submission).

• Hardcopy of your rw.py program (paper submission, via BART).

• Hardcopy of the output of your rw.py program, (paper via BART).

[40 marks]

[Total 100 marks]

Submitting your work

The CA requires both paper and electronic submissions.

Paper You should submit paper copies of the code and any output for all the other questions to the

Harrison Student Services Office by the deadline of 12:00 Wednesday 15th November,

2017. Markers will not be able to give feedback if you do not submit hardcopies of your code

and marks will be deducted if you fail to do so.

Paper submissions should have the BART cover sheet securely attached to the front and

should be anonymous (that is, the marker should not be able to tell you are from the submission). If this is the first time you have used BART,

please make sure that you understand the

procedure beforehand and leave plenty of time as there are often queues close to the deadline.

Where you are asked for paper copies of the output of your code, please copy and paste the

output from the terminal rather than taking a screenshot, because the screenshot is often

illegible after printing. To cut and paste from a Windows Command window, highlight the

text you want to paste, right click in the Command window, click on Select all”, press Enter,

and past into your document (control-V or from the menu).

Electronic You should submit the files containing the code for each question via the electronic

submission system at http://empslocal.ex.ac.uk/submit/. You should use the category

2017~11~15~ECM1400~LorenzoLivi~CA2. Make sure that your code is in files with the names

specified in the questions. Use zip or rar or tar to compress these into a single file, and

upload this file using the submit system. You must do this by the deadline.

You will be sent an email by the submit system asking you to confirm your submission by

following a link. Your submission is not confirmed until you do this. It is best to do it

straightaway, but there is a few hours leeway after the deadline has passed. It is possible to

unsubmit and resubmit electronic coursework | follow the instructions on the submission

website.

7ECM1400 Programming Continuous Assessment 2

Marking criteria

Work will be marked against the following criteria. Although it varies a bit from question to

question the criteria all have approximately equal weight.

• Does your algorithm correctly solve the problem?

In most of these exercises the algorithm has been described in the question, but not always

in complete detail and some decisions are left to you.

• Does the code correctly implement the algorithm?

Have you written correct code?

• Is the code syntactically correct?

Is your program a legal Python program regardless of whether it implements the algorithm?

• Is the code beautiful or ugly?

Is the implementation clear and efficient or is it unclear and inefficient? Is the code well

structured? Have you made good use of functions?

• Is the code well laid out and commented?

Is there a comment describing what the code does? Are the comments describing the major

portions of the code or particularly tricky bits? Do functions have a docstring? Although

Python insists that you use indentation to show the structure of your code, have you used

space to make the code clear to human readers?

There are 10% penalties for:

• Not submitting hardcopies of your programs.

• Not naming files as instructed in the questions.

8