'

A network is a directed graph in which every edge or arc has been assigned a
label. Networks may be

*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*)*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 }_{є E}*f*(*v*,*w*).
A

*cut*in a network is a partition of its nodes*N*into two subsets*S*_{1}and*S*_{2}such that the source node*s*belongs to*S*_{1}and the sink node*t*belongs to*S*_{2}. The*capacity of the cut*is the sum of the capacities of the edges from*S*_{1}to*S*_{2}.
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