MATH1070 Prac 4: RBNs

To complete this prac and the assignment you will need to download CXfiles2.zip from the MATH1070 Labs page. It should contain the files: ‘RBN.m’, ‘RBNperiod.m’, ‘RBNbasins.m’, ‘pajek.m’, ‘pajekrbn.m’, ‘componentsize.m’, ‘pathlength.m’, ‘clusteringcoeff.m’, ‘buildrand.m’, ‘buildlattice.m’, ‘buildsw.m’ ‘buttons.m’, ‘prac5.mat’, ‘ass2.mat’, ‘ass2.net’.

The m-files contain useful information and comments that can be read with the ‘help’ command in MATLAB or by opening the m-file. The two ‘.mat’ files contain adjacency matrices necessary to complete the prac and assignment and ‘ass2.net’ contains a network for the assignment.

Task 1:Generate an RBN with (N, K) = (10, 2)and its expression pattern from a random initial state

Task 2:Examine the structure of the RBN and generate a histogram of the in-degree and out-degree

Task 3:Repeat tasks 1 and 2 with (N, K) = (50, 10)

Task 4:Compare the structure of the state space for two N = 10 RBNs: one with K = 2, and one with K = 5 and a period > 20

To complete the tasks you will need to be able to perform the following operations outlined on the following pages:

  • Create the expression pattern for an RBN
  • Find the period of an attractor
  • Investigate the structure of an RBN
  • Generate the state space and export it to Pajek for visualisation

A reminder about the random number generator:

  • To set the state of MATLAB’s random number generator type rand(‘state’,12345)where 12345 could be replaced by a number of your choosing. To record the current state type randseed=rand('state');where randseedis simply the variable name. The random number generator can then be reset to this state by typing rand(‘state’, randseed).

To create the expression pattern for an RBN:

  1. Since RBN.m is a script you will need to edit the file to change the values of N and K and then save it. The other variable you may want to change is the number of iterations of the RBN, this is the variable its.
  2. When you run RBN.m you will notice it produces an expression pattern of an RBN with a random initial state. In fact the initial network state is specified by the line:

state(:,1)=rand(N,1) > 0.5;

To compute the period of an attractor:

  1. RBNperiod.m is almost exactly the same as RBN.m except that it includes commands that stop the iterations when it detects periodic behaviour. It does this by searching the expression pattern backwards through time from the current network state, looking for a pattern that has occurred before. RBNperiod.m then records and displays the length of the period and the length of the transient. The transient is the number of states the network passed through before it encountered the periodic attractor. If the behaviour is not periodic by the time the number of iterations equals itsthe program will stop.
  2. Set the values of N and K, specify the maximum number of iterations (try 500) and run RBNperiod. The period of the attractor will be displayed as the variable period.

To investigate the structure of an RBN:

  1. Run the file RBN.m or RBNperiod.m to create the variable inputs.
  2. Create the adjacency matrix from the variable inputs by typing the following into a new m-file:

Adj=zeros(N);

for i=1:N

Adj(inputs(:,i),i)=1;

end

  1. This creates the variable Adj and places K ones in each column corresponding to the inputs to each node.
  2. Try running your file and seeing what Adjlooks like by typing Adj Check that there are K ones in each column of Adj.
  3. Add the following lines to your m-file:

in = sum(Adj);

out = sum(Adj’);

in is a vector containing the in-degree for each node,outcontains the out-degrees.

  1. To create a histogram of the in-degree distribution type

hist(in,0:max(in));

at the prompt. Do the same with out for the out-degree.

  1. To view the actual network you can use Pajek by exporting the adjacency matrix to a ‘.net’ file that Pajek can read: type pajek(Adj,’RBN’); at the prompt.
  2. Start Pajek and open 'RBN.net' from the directory in which MATLAB was working. Draw the network.

To generate the state space and export it to Pajek:

  1. Make sure the values of N and K in the file RBNbasins.m are the same as those in RBN.m or RBNperiod.m and set the state of the random number generator to the same value as RBN.m or RBNperiod.m
  2. Note: The time RBNbasins.m takes to run increases exponentially with N.N should be no bigger than about 10 -12. Pajek will also have trouble displaying networks bigger than this.
  3. Run RBNbasins.m
  4. The entire state space will be stored in the sparse matrix S.
  5. Export the state space to a '.net' file by typing

pajekrbn(S,’statespace’);

  1. Start Pajek and open 'statespace.net' from the directory in which MATLAB was working.
  2. Compute the number of (weak) components in Pajek.
  3. Use draw-partition to visualise the network and change the layout using Layout – Energy – Kamada-Kawai – Free.
  4. Compute the partition-core-input to highlight the attractors.

MATH1070 Prac 5: Network Structure

Analysing Network Structure

  • Make sure the file ‘prac5.mat’ is in MATLAB’s present working directory. Load the variables from the file into MATLAB’s workspace by typing load prac5.
  • For each adjacency matrix answer the following questions:
  • How many nodes are there?
  • Are there any self-connections?
  • Is the network directed or is the adjacency matrix symmetric?
  • How many edges are there?
  • What do the in-degree and out-degree look like?
  • What is the longest shortest path in the network?
  • What is the average shortest path?
  • What is the clustering coefficient?
  • How many connected components are there?
  • How big is the largest component?
  • What does the network look like? (Draw in Pajek.)
  • Consider a network of 10 nodes that are joined in a circle with directed edges all going the same way. Label the nodes and write down the adjacency matrix.
  • Consider a network of 5 nodes joined with undirected edges to make pentagram (each node will have a degree of 2). Label the nodes and write down the adjacency matrix.
  • Consider a network of 7 nodes where the central node is connected to the other 6 with undirected edges. Label the nodes and write down the adjacency matrix.

Small World Networks

  • Use the m-file ‘buildsw.m’ to create a small world network with 100 nodes and, on average, 4 links per node.
  • Use MATLAB to investigate how the parameter p affects the following properties
  • The degree distribution.
  • The longest shortest path.
  • The average shortest path.
  • The clustering coefficient.
  • What does the network look like for different values of p? (Draw in Pajek.)

MATH1070 Complex Systems Assignment 2

This assignment consists of 3 sections and is worth 10% of your assessment for the course. It is due on Monday, October 4th at 10am.

To complete this assignment you need to have downloaded the file ‘CXfiles2.zip’ from the MATH1070 Labs webpage.

For additional information that may be useful in completing this assignment refer to Pracs 4 and 5 and the lecture notes.

  1. Random Boolean Networks (3 marks)
  2. State space in Pajek (1 mark). The file ‘ass2.net’ contains the entire state space for an RBN. Open the file ‘ass2.net’ in Pajek.
  3. How many attractors are there?
  4. What is the average period of the attractors?
  5. What is the length of the longest transient?
  6. How many nodes were in the RBN that created this state space?
  7. Period length in MATLAB (1 mark). You will need to use the file ‘RBN.m’ or ‘RBNperiod.m’ in MATLAB. Since this question requires generating multiple networks you may like to use a ‘for’ loop and record the important variables.
  8. Record the period of the attractor for 10 different RBNs starting from random initial states with N=10 and K=1.
  9. Calculate the average period.
  10. Continue to record the periods for 10 trials for different RBNs with N=10 and K=2, 3, 4, 5, 6, 7, 8, 9 and 10.
  11. Calculate the average for each case.
  12. Describe how the average period is affected by K.
  13. Number of attractors in MATLAB (1 mark). You will need to use the files ‘RBNbasins.m’ and ‘componentsize.m’. Since this question requires generating multiple networks you may like use a ‘for’ loop and record the important variables.
  14. For N=10 and K=1 record the number of attractors for 10 different RBN state spaces.
  15. Calculate the average number of attractors.
  16. Continue to record the number of attractors for 10 trials for different RBNs with N=10 and K=2, 3, 4, 5, 6, 7, 8, 9 and 10.
  17. Calculate the average for each case.
  18. Describe how the average number of attractors is affected by K.

  1. Network Structure (4 marks)

Load the variables in the file ‘ass2.mat’ by typing load ass2 at the MATLAB prompt. This file contains adjacency matrices called A and B.

Parts (a) and (b) are each worth 2 marks.

  1. This question requires you to analyse the network represented by A:
  2. How many nodes does the network contain?
  3. Is the adjacency matrix symmetric?
  4. How many edges are there?
  5. Are there any self-connections?
  6. What is the average degree?
  7. Which of the following does the in-degree distribution look like:

exponential, scale free, Poisson or all the same degree?

  1. Which of the following does the out-degree distribution look like:

exponential, scale free, Poisson or all the same degree?

  1. What are the sizes of the components?
  2. What is the longest shortest path between vertices for which a path exists?
  3. What is the average shortest path?
  4. What is the clustering coefficient?
  5. Can every node be reached from every other node?
  1. Answer the same questions as above for the network represented by B.

  1. Network Modelling (3 marks)

There are N buttons scattered on the floor. You choose two of the buttons at random and tie them together with a piece of string before replacing them. You continue to pick up two buttons at a time and, provided they are not already tied together, you connect them with a piece of string. After a while you will pick up a button that has other already attached to it, but provided it is not tied directly to your second button, you tie the two of them together. You stop connecting buttons after you have use exactly L pieces of string.

The result of this process can be represented by an N x N adjacency matrix, A, containing 2L nonzeros (every piece of string increases the degree of two nodes by one).

  1. Will A be symmetric?
  2. Will the diagonal of A contain any ones?
  3. On average, how many other buttons will each button connect to (in terms of N and L)?
  4. What is the maximum number of pieces of string that the final network could contain (as a function of N)?
  5. The m-file ‘makenet.m’ contains a quick method for generating the adjacency matrix of the resulting network. Use the help command in MATLAB to help you understand how it works. With N=100, determine the approximate critical number of links (Lcrit) for the formation of a totally connected component. Demonstrate this critical number by running 10 random trials with L ≈ Lcrit showing that the largest component can sometimes be completely connected connected and sometimes not. (The range of Lcrit may be quite large.)
  6. Find an empirical upper bound on Lcrit so that all 10 trials give completely connected networks for the lowest level of Lcrit.
  7. Theoretically, what is the minimum number of pieces of string that could be used to create a completely connected network (in terms of N)?

Each part is worth half a mark except (a) and (b) which are worth half a mark together.