IFN Playground: Composition-Decomposition

Brief Description

In this page, we are dealing with integer IFN. IFN Composition is a transformation from network signature into an Ideal Flow Network. IFN Decomposition is a transformation from an Ideal Flow Network into network signature. The matrix of Ideal Flow Network (IFN) is irreducible premagic. Irreducible means strongly connected network. Premagic means the sum of rows is exacly the same as the corresponding sum of columns.

A strongly connected network (i.e., irreducible adjacency matrix) contains at least one cycle. These cycles can be shorten by removing the last node since it is clear that the first and the last element of a cycle is the same. To avoid repetition of the same permuted cycle, we write the cycles in canonical notation. A cycle represention is canonical when the smallest element of the cycle is written as the first element of the cycle.

Suppose the adjacency matrix $ \mathbf{A} $ contains $ k $ canonical cycles $ \hat{c}_{i} $. An assignment operator on a cycle is equal to the adding one unit of flow along the cycle. If the node in the cycle does not exist in the network, the network is expanded by adding that node. If the link in the cycle does not exist in the network, the assignment operator will first add the link to the network before adding one unit flow to the links along the cycle.

A network signature is a string code that build an ideal flow network (IFN). A network signature is in the form of the summation of terms. Each term contains a coefficient and a canonical cycle. The coefficient indicates the number of repetitions that the cycle would be assigned to form the network. The addition indicates merging operation between two networks.

A network signature need to pass irreducibility condition. Suppose each canonical cycle forms a term and the coefficient of the term represents how many times the cycle would be assigned to the network. To ensure irreducibility, in each term, there must be at least one node that overlap (i.e. the same node name) with at least one other term. The overlapping node is called pivot.

Network signature is not unique. The same IFN can be obtained by several network signature of different cycles.

An Ideal Flow Network can be obtained by the following network signature: $$ \mathbf{F} = \sum_{i=1}^{n}\alpha_{i}\hat{c}_{i} $$

Learning Objectives

to form an integer ideal flow network from network signature
to find network signature from integer ideal flow network
to understand reducible conditon
to understand canonical cycle term
to understand how random cycle can be used to form IFN

Instruction

Click to generate random signature
Click to form Ideal Flow Network from the signature

Experiment and Discussion

Create IFN from Network Signature.

Generate random coefficient.
Generate Random Cycle Terms. Do they pass irreduciblity condition?
Generate all possible combination of cycles for the given size of the network nodes. What make cycles valid or invalid to be used as network signature?
Decomposed the IFN by finding the network signature. Will the network signature the same as original signature? Why?

Investigate the characteristics of network signature

Test whether generated random cycle terms is valid for network signature. Canonize the terms and then check the irreducibility condition.
Test whether combining some of the possible combination of cycle terms produce valid for network signature. Check the irreducibility condition and canonization of the cycle.

Challenge yourself

Compute the indices such as the statistics of flow and various entropy. Which ones among them are invariant?
Can you create Cardinal Network, which is the minimum integer ideal flow for the given network structure?
How do you interpret pivots of merging two networks in daily life application of IFN?