Assignment 1 Solution

Description

• We will explore real networks throughout the course performing some key measurements introduced in Principles of Complex Systems.

• you are encouraged to use Python (along with, for example, NetworkX or graph-tools).

• Data is available in two compressed formats:

– Matlab + text (tgz): http://www.uvm.edu/pdodds/teaching/courses/ 2019-01UVM-303/data/303complexnetworks-data-package.tgz

– Matlab + text (zip): http://www.uvm.edu/pdodds/teaching/courses/ 2019-01UVM-303/data/303complexnetworks-data-package.zip

and can also be found on the course website (helpfully) under data.

• The main Matlab file containing everything is networkdata_combined.mat.

• For directed networks, the ijth entry of the adjacency matrix represents the weight of the link from node i to node j. Adjacency matrices for undirected networks are symmetric.

• For all questions below, treat each network as undirected unless otherwise instructed.

• For this assignment, convert all weights on links to 1, if the network is weighted.

• You do not have to use Matlab for your basic analyses. Python would be a preferred route for many.

• The supplied text versions may be of use for visualization using gml.

• The Matlab command spy will give you a quick plot of a sparse adjacency matrix.

• Real data sets used here are taken from Mark Newman’s compilation (and linked-to sites) at http://www-personal.umich.edu/~mejn/netdata/.

1. Record in a table the following basic characteristics:

1. • N, the number of nodes;

1. • m, the total number of links;

1. • Whether the network is undirected or directed based on the symmetry of the adjacency matrix;

   • k , the average degree ( k_in and k_out if the network is directed);

1. • The maximum degree k^max (for both out-degree and in-degree if the network is directed);

1. • The minimum degree k^min (for both out-degree and in-degree if the network is directed).

2. (3+3)

1. Plot the degree distribution P_k as a function of k. In the case that P_k versus k is uninformative, also produce plots that are clarifying. For example, log₁₀ P_k versus log₁₀ k.

(Note: Always use base 10.)

1. 2. See if you can characterize the distributions you find (e.g., exponential, power law, etc.).

3. Measure the clustering coefficient C₂ where

_{C =} 3 #triangles_:

₂ #triples

For directed networks, transform them into undirected ones first.

One approach is to compute C₂ as

					3	1	TrA3
C2 =						6		:
					∑
		1
				(	ij [A2]ij TrA2)
2

Note: avoiding computing A³ is important and can be done.

3