Pages

Saturday, October 26, 2013

103. Networks and Network Flows

'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.