'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
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.
modelnetwork program implements the SN model and tools used to analyse networks.
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.
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.
#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:
- Extract the files:
jar -xf structurednodesSource.jar
- Step into the directory:
- Build using:
java -jar structurednodes.jar
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 using
java -jar structurednodes.jar
structurednodesSource.jar: source code.
JavaDocfor the project.
example properties files that generate networks similar to