IFN Lab: Premier Network

Brief Description

The usual ideal flow network would come from the stochastic matrix as shown in this page . If we don’t have the stochastic matrix, we assume stochastic matrix from the adjacency matrix (because based on Maximum Entropy Principle, if we don’t know the information, we can use the least assumption from what we already know) and as the result, the probability of turning direction on each node it would become uniform distribution (equal outflow IFN).

A Premier Network is a cardinal Ideal Flow Network (i.e., standard form of minimum integer IFN). Premier Network is developed based on sorted canonical cycles, which is the basic building block of premagic matrix. The premagic capacity would be useful for designing the network that balance the flow in all directions such that no single step scenario or policy would be able to make a better network in term of maximum congestion

Unlike the usual ideal flow network that requires total flow and stochastic matrix as input, the premier network is the unique minimum integer IFN that come purely from network structure (i.e, adjacency matrix). The total flow and stochastic matrix would be the output.

A strongly connected network (i.e., irreducible adjacency matrix) contains at least one cycle. A strongly connected network may contain many cycles. These cycles may be the same cycle, but writen in permutation ways. For example, cycle term `abc|a` may be written as `bca|b` or `cab|c`. We can shorten the cycle notation by removing the last node, which is the same as the first node anyway. Since it is clear that the first and the last element of a cycle is the same, `abc` = `abc|a`. Another example, cycle term `acdb|a` is now written as `acdb`. To avoid repetition of the same cycle, we write the cycles in canonical notation. Canonical cycle notation is a unique way of writing a permutation as a product of disjoint cycles. The set of the permutation is defined is orderable. The canonical cycle is the representation of a cycle when the smallest element of the cycle is written as the first element of the cycle. In above example, the canonical notation of the cycle become `abc`.

Suppose the adjacency matrix $ \mathbf{A} $ contains $ k $ canonical cycles. Let us define an assignment operation symbolized as $ \hat{c}_{i}, $ which is the same as cycle-plus-one. If the node in the cycle does not exist in the network, it would first expand the network by adding node. Similarly, if the link in the cycle does not exist in the network, the assign operator would first add the link to the network. After that, assignment operation will increase one unit flow to the links along the cycle. When the cycle term is repeated $ \alpha $ times, can be written as $ \mathrm{cycle_{i}(+1,\alpha)} $ symbolized by $ \alpha\hat{c}_{i}, $ for $ i=1,\cdots, k $ as the application of one unit flow to the existing network $ \alpha $ times along a canonical cycle $ c_{i} $. Similarly, we can also define the reduction of one unit flow to the existing network $ \alpha $ times along a canonical cycle $ c_{i} $, which is called cycle-minus-one or $ \mathrm{cycle_{i}(-1,\alpha)} $ symbolized by $ \alpha\check{c}_{i} $. When the repetition of all cycle terms are all one $ \alpha_{i}=1 $, we can simplify the notation of the operation cycle-plus-one as $ \hat{c}_{i} $ and cycle-minus-one as $ \check{c}_{i} $. Be careful, however, reduction of one unit flow along a canonical cycle $ \check{c}_{i} $ from a premier network would alter the original network structure. It is possible that the altered network structure may not be strongly connected network anymore.

The premier network $ \mathbf{F}^{*} $is obtained by the merging of operation cycle-plus-one from the canonical cycles once for each canonical cycle. The merging operation is symbolized by the $ + $ symbol. $$ \mathbf{F}^{*} = \sum_{i=1}^{n}\hat{c}_{i} $$ The premier network would have exactly the same network structure (i.e., the same adjacency matrix $ \mathbf{A} $) as the capacity matrix but the stochastic matrix is not necessarily the same.

The premier network is the initial building block for the integer IFN of the same network structure. All integer IFN of the same network structure, can be obtained by operation $ \alpha \hat{c}_{i} $ on top of its premier network. Any integer 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 understand the operation cycle-plus-one and cycle-minus-one
to understand the forming of premier IFN from cycle-plus-one operation to the canonical cycles
to understand the premagic IFN from cycle-plus-one operations on top of the premier IFN
to understand the network structure and stochastic matrix of premier IFN
to understand how random cycle can be used to form IFN

Instruction

Click to generate random irreducible capacity matrix
For each canonical cycle, apply operation cycle-plus-one . After all canonical cycles are in buffer, click . The result is the premier IFN, which has the exact network structure as the capacity matrix.
Alternatively, click to add set of premier cycles to the buffer and click to get the premier IFN.

Experiment and Discussion

Create Premier IFN.

Generate random Capacity matrix. Modify the capacity matrix manually if necessary. Add cycles to buffer to obtain premier IFN. Compare your cycle selection to the ones obtain by clicking button

Is changing the order of the canonical cycle produce different result?
Check the network structure (adjacency matrix) and the stochastic matrix between the capacity and the premier ideal flow. Is network structure change? Is the stohastic matrix change?
Using the same capacity matrix (use save and load CSV) buttons, apply your capacity matrix to the Capacity to Ideal Flow Lab. Compare the result of the ideal flow passing via stochastic matrix and the premier IFN. Is network structure change? Is the stohastic matrix change? What is the difference between Premier IFN and the ordinary IFN?

Investigate the characteristics of operation $ \mathrm{cycle(+1,\alpha)} $ and $ \mathrm{cycle(-1,\alpha)} $

Test whether each application of cycle-plus-one or cycle-minus-one above the premier IFN would always produce an Ideal Flow Network of the same network structure as the capacity matrix. How about the stochastic matrix?
What happen if you do cycle-plus-one operation and then cycle-minus-one operation on the same cycle (not necessarily cannonical cycle)? Will the +1 operation cancel the -1 operation?
From premier IFN, if you remove one canonical cycle using cycle-minus-one operation, will the network structure still the same as the original capacity matrix?

Challenge yourself

Start by adding set of the premier cycle operation into buffer. Experiment by add operation cycle-plus-one or cycle-minus-one of any cycle to reach the next and previous premagic capacity matrix. can you find the ideal flow that is the closest to the capacity matrix? What is the minimum total absolute change from capacity matrix to the flow matrix?
Use the same lab tool for testing random cycle above the premier IFN. Can you get the IFN that has the same maximum value as the capacity matrix?
Using the same capacity matrix (use save and load CSV) buttons, apply your capacity matrix to the Capacity to Ideal Flow Lab for a certain total flow $ \kappa$. Create random cycle above the premier IFN. Can you get the IFN that has the same total flow $ \kappa$?