Structured Nodes Model Network

'We present a network model in which words over a specific alphabet, called structures, are associated to each node and undirected edges are added depending on some distance measure between different structures. This model shifts the underlying principle of network generation from a purely mathematical one to an information-based one. It is shown how this model [...] can generate networks with topological features similar to biological networks: power law degree distribution, low average path length, clustering coefficient independent from the network size, etc. ' - from Frisco 2011

Description

Structured Nodes network model

The Structured Nodes (SN) network model is an algorithm that, given a set of input parameters, generates a network. The SN model operates by creating nodes which have a structure. The structure of a node is a string over an alphabet, and these strings are generated by mutating the structures of nodes that exist in the network. The nodes are connected together by edges based upon the differences in their node structures. The usual way of doing this is to take the Hamming distance of the two structures and only connect the nodes with an edge if it is below a certain threshold. This makes the network model information-based.

The SN model is able to generate networks with topological features that appear in many empirical networks that are found in biological processes. The features include a power law degree distribution, and the low average path length and high clustering coefficient that are the hallmarks of a /small world/ network.

The SN algorithm has been implemented as a Java program. The modelnetwork program implements the SN model and tools used to analyse networks. The modelnetwork program is also able to generate networks from the Erdos-Renyi and Watts-Strogatz model, as well as load in and analyse networks generated elsewhere.

Evolutionary Algorithm

The SN network model is able to generate networks with features that match empirical networks, but the parameters for the SN model may be hard to find. We have developed an Evolutionary Algorithm (EA) that takes as input the values of measurements that we wish to see in the generated network, and the EA will then try to developed a set of input parameters to the SN model that would generate networks with these targeted measurements.

EAs are an approach to finding solutions to difficult optimisation problems. EAs generate populations of solutions to an optimisation problem by performing mutation and crossover operations on an existing population. The elements of these populations must then be attempted as a solution to the problem, and given a score determining their fitness. The population members that are best able to solve the problem are kept on to become the population that the next generation is based on.

EAs are good at solving multi-objective optimisation problems, where there more than one target measurement that each solution will try and match. Network generation is such a problem, as there are many different measurements that taken from a network. The measurements that the EA program will try and match are the average degree, average path length, and the average clustering coefficient.

The EA program generates sets of parameters to the SN model and then uses the SN program to generate networks and take their measurements. As the EA may need to run for a couple of hundred generations and the time taken to generate and take measurements of a large network may be over 10 minutes (for ~3000 nodes) and there may be a population of hundreds for each generation, then it is best to evaluate solutions in parallel, or even on a cluster of computers. The EA program uses taskdispatcher to facilitate this.

How to use

To use the Structured Nodes program first download structurednodes.jar.

Running the jar (java -jar structurednodes.jar) will launch a graphical user interface, from which either the SN program or the EA can be configured and run.

Alternatively the program can be run headlessly by java -cp structurednodes.jar modelnetwork/Main for the SN program, or java -cp structurednodes.jar evolutionprogram/EvolutionProgramMain for the EA program.

A typical properties file for the program is seen below. A full explanation of all the fields that can be used in the properties file can be found in the Constants page of the JavaDoc.

propertiesModelNet.txt

#The output folder name and index to be appended to it.
Base_dir = xxx_
Counter = 0

#The files to output
File_network = network.log
File_clustCoeff = clust
File_edges = edges
File_path_length = length

#How to generate the network
Network_size = INCREMENTAL
Alphabet = A,B,C,D
Initial_node = CCBAC
Max_distance = 1
Unit_distance = 1
Num_runs_each_network = 229

#How the nodes are connected together
Direction = NONE
Bidirectional_Edges = TRUE
Type_distance = HAMMING

#How new nodes are generated
Prob_to_add = 0.0
Prob_to_delete = 0.0
Prob_to_mutate = 1.0
Prob_to_duplicate = 0.0

How to build (Linux)

  • You will need Java 7 or above and Apache Ant installed.

  • Download the sources: wget http://www.macs.hw.ac.uk/~gg32/projects/modelnetwork/structurednodesSource.jar
  • Extract the files: jar -xf structurednodesSource.jar

  • Step into the directory: cd structurednodes

  • Build using: ant

  • Run: java -jar structurednodes.jar

Papers

The Structured Nodes model has been used in the following papers:

A critical study of network models for neural networks and their dynamics - G. Govan, A. Xenos, P. Frisco
Journal of Theoretical Biology, In Press http://dx.doi.org/10.1016/j.jtbi.2013.07.005
Finding Biologically Plausible Complex Network Topologies with a New Evolutionary Approach for Network Generation - G. Govan, J. Chlanda, D. Corne, A. Xenos, P. Frisco
EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation IV, Advances in Intelligent Systems and Computing Volume 227, 2013, pp 59-73, http://dx.doi.org/10.1007/978-3-319-01128-8_5
Network model with structured nodes - P. Frisco
Physical Review E, Vol 84, Issue 2, 2011 http://pre.aps.org/abstract/PRE/v84/i2/e021931
Evolution Program for Network Model - A. O. Xenos
Master's Dissertation Heriot-Watt University, 2011 [PDF]

Downloads and Links