MM409/509 Course Work
The aim of this assignment is to further analyse some real world data using the techniques introduced
in the lectures. Some of the quantities you need to calculate, and the methods of presentation, will
involve some exploration of MATLAB.
For this work you will use the network you used in part one, designated as Network_1.
In the file Datasets and References you will find a short description of the source and context of the
networks and some associated references. It is VERY IMPORTANT that you do not constrain yourself
to this description and references. You should search for other relevant literature to support your
findings in this coursework. You are expected to work independently.
Each MM409 student should carry out one of the activities (as advised on Myplace). MM509 students
should carry out all 3 activities.
Activity 1
Compute the following statistic for the network: The network’s assortativity.
Measure the closeness centralities and the eigenvector centralities of every node in your network. For
each measure, identify the 10 nodes with the highest centrality and highlight these on a picture of your
network. Next compute two other centralities of your network and again highlight the most central
nodes. Comment on the differences/similarities of the rankings given by the measures.
Repeat the experiment on 10 random graphs with the same number of nodes and (approximate) edges
as your network and contrast the results.
Activity 2
Compute the following statistic for the network: Average path length.
1. Partition your network into two communities using the Fiedler vector and report the modularity
(see chapter 21 of the notes).
2. Use the Newman–Girvan algorithm to make a partition of your network into k = 2, 3, . . . , 6 com-
munities. Report the modularity of each partition and comment on your results. In particular,
compare the partition into two communities with the one provided by the Fiedler vector.
3. Successively rewire at random 10%, 25%, 50%, 75% and 100% edges of the network (given the
total number of edges in your network the actual percentage you use will be an approximation).
For each of the rewired networks, use the Newman–Girvan and Fiedler methods to divide the
nodes into two communities and measure the modularity.
Note that the MIT toolbox (see Appendix) contains command to perform the rewiring (as well as
code to perform the Newman–Girvan algorithm). For example, to rewire 10 edges you could use
the following MATLAB snippet on an adjacency matrix A.
1
edges =adj2edgeL(A);
new_edges = rewire(edges,10);
A_rewired=edgeL2adj(new_edges);
Activity 3
Compute the following statistic for the network: Clustering coefficients.
In this experiment you will investigate the returnability of a directed network. The first step is to
artificially turn your network into a directed network. Then use formula (17.16) in the notes to compute
the returnability. Note that to compute the exponential of a matrix you can use the command expm.
1. First make every edge in your network a directed edge. Start with the adjacency matrix A and
for each entry for which aij = 1 set one of aij or aj,i to equal zero.
2. Now randomly add the edges back one at a time. After each edge is added, record the new value
of the returnability.
3. Once you have done this, draw graph of the value of the returnability against the number of
edges you have added.
Repeat the experiment on 10 random graphs with the same number of nodes and (approximate) edges
as your network and contrast the results.
Reporting your Results
You are expected to produce a coherent report of your work of up to 5 pages in length (not including
any appendices). Any project that exceeds this length will be heavily penalised.
In order to report your results you must write a report containing the following,
• Introduction: a brief description of the network you are studying, general importance of network
theory and other general comments.
• Methods: describe all the mathematical definitions of any network parameter, model or method
to be used in your work.
• Results: a description of the numerical results obtained, tables and graphics that support your
calculations.
• Discussion: a brief analysis of the results obtained, based this discussion on the network you are
studying and try to interpret then in this context, you can use additional graphics to explain your
ideas.
• Conclusions.
• References: Cite any reference used in your work, not only those provided.
• Appendices (if relevant): This could include MATLAB files/commands you have used and raw
data/expanded results.
2
Notes
• You can either write your own codes to perform calculations or you can use pre-existing code.
Credit will be awarded for efficient computations. The appendix contains a list of web pages
where you can find useful MATLAB codes.
• You can use visualization programs to visualize the network as well as to support the discussion
of your results (think about you are writing a scientific paper). MATLAB has good visualisation
tools but there are other bespoke network tools you can explore such as Gephi and NodeXL.
• You can use any wordprocessing software you like but your final report must be submitted elec-
tronically as a PDF via Myplace.
• The deadline for submission of the final PDF is midday on Friday 3rd April.
Appendix
Here is a list of web-pages where you can find MATLAB codes and programs useful for this assign-
ment. This list does not pretend to be exhaustive and you are encouraged to search for more as well as
to write your own codes.
1. sites.google.com/site/bctnet/
2. www.levmuchnik.net/Content/Networks/ComplexNetworksPackage.html
3. strategic.mit.edu/downloads.php?page=matlab_networks
4. www.mathstat.strath.ac.uk/outreach/contest/toolbox.html