updated *October 28, 2007*

(completed text for
scale-free networks)

# Topologies for Artificial Gene Networks

One of the objectives of this research is to study the importance of network topologies in the behavior of gene networks. Additionally it is also important to know how several reverse engineering methods behave against diverse topologies.

Our artificial gene networks follow several topologies:

- Erdös-Renyi-like random networks
- Regular lattices
- Watts-Strogatz (small-world) networks
- Albert-Barabási (scale-free) networks

## Random networks

Starting with the work of
Erdös
and Renyi.
Such networks have the characteristic that, on average, each gene is
much like any other gene. The Kauffman networks (also known as
*nk* systems) contain *n* genes that each have the same
number *k* of inputs from other genes. **Our random networks have a fixed number of inputs and
each gene has equal probability of affecting each other gene.**

## Regular lattices

Regular lattices are the opposite to random networks. Here each gene receives
inputs from a small number of nearest neighbors. One dimensional lattices are
rings, two dimensional ones are square grids. In regular lattice
networks there is a well marked notion of neighborhood for each gene.
Note that genes on the opposite sides of the lattice are very distant
from each other (*i.e.* perturbations on one will take a long
time to propagate to the other).

## Small-world networks

Watts and Strogatz studied small-world networks and showed that these are
intermediate between regular lattices and random networks. Small world networks
reproduce the famous "6 degrees of separation" effect, where each node
in the network can be reached from another through a small number of
connections. The algorithm of Watts and Strogatz first starts by
constructing a 1D regular lattice, where each gene is connected to
*k* nearest neighbors; then it proceeds to rewire each
connection randomly with a certain probability. **Our software uses the Watts-Strogatz algorithm
to generate small-world gene networks.**

## Scale free networks

Albert and Barabási made popular the concept that many networks
have the property that the majority of their nodes have a small number
of connections while a small number of nodes have a very large number
of connections. The distribution of numbers of connections (degree
distribution) is a power law, usually with a low exponent. Several
researchers have shown evidence that real gene networks
are scale free, though others disagree. Albert and Barabási
argue that such networks are natural if they form in a historical way,
with new nodes being linked to the network such that the probability
to link to an existing node is proportional to the number of nodes
that one is already linked to. **Our software uses the Albert-Barabási
algorithm to generate scale-free gene networks.**