'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
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.
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:
Downloads and Links
-
structurednodes.jar: jar file containing the evolutionaryprogram, modelnetwork and taskdispatcher programs. Run usingjava -jar structurednodes.jar -
structurednodesSource.jar: source code. -
taskdispatcherproject -
JavaDocfor the project. -
example properties files that generate networks similar to
-
the Escherichia coli protein-protein interaction network
[propertiesModelNet.txt] -
the Saccharomyces cerevisiae gene network
[propertiesModelNet.txt] -
the Methicillin-resistant Staphylococcus aureus gene network
[propertiesModelNet.txt]
-