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. UsetheNewman–Girvanalgorithmtomakeapartitionofyournetworkintok=2,3,…,6com- 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.
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.
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