'The mystery of life begins with the intricate web
of interactions, integrating the millions of molecules within each organism.
The enigma of the society starts with the convoluted structure of the social
network. The unpredictability of economic processes is rooted in the unknown
interaction map behind the mythical market. Therefore, networks are the
prerequisite for describing any complex system, indicating that complexity
theory must inevitably stand on the shoulders of network theory' (A.-L.Barabási, Linked)
A network is a directed graph in which every edge or arc has been assigned a
label. Networks may be isotropic, or
otherwise. Isotropic networks do not have well-defined inputs and outputs. By
contrast, neural networks are examples of networks with well-defined inputs,
which they convert into certain desired outputs.
Networks can be of different types. A network with a
well-defined input and output may be formally defined as follows: A network is
a directed graph D in which there is
vertex s (called the source) and a vertex t (called the sink), and for which a function c
(called the capacity) is defined which assigns to each edge of the
network a nonnegative number. Such a network is relevant, for example, for
building a model for maximizing the flow of goods from one point to another in
a transportation system. Although I am assuming a
single-input single-output network here, such considerations can be generalized
to multiple sources and/or multiple sinks.
A flow on D is a function f from E(D) into nonnegative
numbers such that the following two conditions are satisfied. The first is that the flow
cannot exceed the capacity of an edge; i.e., for an edge e, f(e) ≤ c(e) for all e belonging to E (e
є E). The second condition is that the input into any intermediate
vertex must be equal to the output from that vertex. That is, for all vertices v belonging to the subgraph D – {s,t},
we must have ∑uv є E f(u,v)
= ∑vw є Ef(v,w).
A cut in a network is a partition of its nodes N into two subsets S1
and S2 such that the
source node s belongs to S1 and the sink node t belongs to S2. The capacity
of the cut is the sum of the capacities of the edges from S1 to S2.
An important theorem in the
theory of network-flows states that in a
network the value of a maximum flow is equal to the capacity of a minimum cut.
It is known as the max-flow min-cut
theorem, or the maximin theorem.
r-regular
networks
The notion of an r-regular graph, or regular graph, was introduced
in Part 102. An r-regular network is one
which has an underlying r-regular
graph. All vertices of an r-regular
network have the same degree r. In
other words, in a regular network all nearest-neighbour nodes are connected in
a regular manner. Such networks have local groups of highly interconnected
nodes. For them the number of edges per node has an approximately Gaussian
distribution, with a mean value that is a measure of the ‘scale’ of the network
(Bray 2003). The width (the 'full width
at half maximum') of the Gaussian-distribution curve is a measure of the scale.
The important thing is that such a scale is identifiable, unlike the situation
in a power-law distribution.
I consider an example from
systems biology to illustrate the notion of a network. The
processes occurring in a biological cell can be modelled in terms of a variety
of molecular networks (Alon 2008; Bray 2003). Transcription networks are an example. In a transcription network the
nodes or vertices are the genes, and the edges are the transcriptional
interactions (cf. Part 43). Consider two nodes u and v. If there is a transcription interaction between them, it is
represented by a directed edge or arrow: u → v. In
general, more than one arrows may point at a particular node in some networks,
in which case a suitable input function has to be defined (e.g. an AND or OR
function). Similarly, two nodes may be simultaneously involved in more than one
types of interaction (e.g. on different time scales). One can then use
different colours for the arrows
joining them. The strength of the interaction between two nodes is represented
by assigning a weight to the arrow joining them.
Network motifs
In spite of the fact that
evolutionary processes involve a fair amount of random tinkering, Nature has
zeroed-in again and again on certain recurring circuit elements, called network motifs (NMs). Each such motif in the molecular
network performs a specific information-processing job. Here are some examples
of such jobs in the case of the transcriptional networks of the cell comprising
the bacterium E. coli (cf. Alon 2003): filtering out spurious input
fluctuations; generating temporal programs of gene expression; accelerating the
throughput of the network. Similar NMs have also been found in the
transcription networks of yeast (Milo et al. 2002). Operational amplifiers and
memory registers in human-made electronic circuits are some of the equivalents
of NMs.
NMs are formally defined as
follows (Milo et al. 2002): Given a network with N nodes and E edges, one can construct a randomized
network or random network from it
which has the same single-node characteristics as the actual network (i.e. the
numbers N and E are unchanged), but where the connections between nodes are made
at random. In other words, we construct a spanning random network from the
actual network. NMs are those patterns that occur in the actual network
significantly more frequently than in the spanning random network.
There are a large number of
possibilities by which a given set of nodes can be interconnected. I shall
consider some of them in the next few posts.
No comments:
Post a Comment