IFN Lab: Capacity to Ideal Flow Matrix

Brief Description

A capacity matrix $ \mathbf{C} $ is a nonnegative weighted adjacency matrix. An ideal flow matrix $ \mathbf{F} $ is a nonnegative matrix that is premagic and irreducible. Premagic matrix is a square matrix where the sum of rows is equal to the transpose of the sum of columns. To convert capacity matrix to an ideal flow matrix contains several steps. First the Capacity matrix is converted to stochastic matrix using the following formula: Let $ \mathbf{C} = [c_{ij}] $ be the capacity matrix, $ \alpha $ and $ \beta $ be the parameters, and $ \mathbf{S} = [s_{ij}] $ be the stochastic matrix. Then, each element $ s_{ij} $ of $ \mathbf{S} $ is given by $$ s_{ij} = \frac{c_{ij}^\alpha e^{\beta c_{ij}}}{\sum_{k=1}^{n} c_{ik}^\alpha e^{\beta c_{ik}}} $$ where $ n $ is the number of columns (or rows, since it's a square matrix) in $ \mathbf{C} $. A nonnegative matrix $ \mathbf{S} $ is called a stochastic matrix if all its row sums are one. From an irreducible stochastic matrix $ \mathbf{S} $, we can transform it into an ideal flow matrix $ \mathbf{F} $ whose total flow is $ \kappa $. Let $ \textbf{I} $ be the identity matrix, then the node vector $ \mathbf{\pi} $ is computed with parameter total flow $ \kappa $ as $$ \mathbf{\pi} =\begin{bmatrix} \mathbf{S}^{T}-\mathbf{I} \\ \mathbf{j}^{T} \end{bmatrix} \setminus \begin{bmatrix} \mathbf{0} \\ \kappa \end{bmatrix} $$ The notation $ \mathbf{x} = \mathbf{K} \setminus \mathbf{b} $ means $ \mathbf{x} = \mathbf{K}^{+} \mathbf{b} $ where $ \mathbf{K}^{+} = (\mathbf{K}^{T}\mathbf{K})^{-1} \mathbf{K}^{T} $ is the Generalized Left Inverse of the Moore Penrose Inverse.The notation $ \mathbf{x} = \mathbf{K} \setminus \mathbf{b} $ means $ \mathbf{x} = \mathbf{K}^{+} \mathbf{b} $ where $ \mathbf{K}^{+} = (\mathbf{K}^{T}\mathbf{K})^{-1} \mathbf{K}^{T} $ is the Generalized Left Inverse of the Moore Penrose Inverse. From the node vector $ \mathbf{\pi} $ and stochastic matrix $ \mathbf{S} $ we can compute the flow matrix . $$ \mathbf{F} = \left (\mathbf{\pi} \cdot \mathbf{j}^{T} \right ) \circ \mathbf{S} $$

Learning Objectives

to compute Ideal Flow matrix and network based on capacity matrix up to a scale.

to understand the effect of parameters in converting capacity matrix into ideal flow.

to comprehend the pattern of irreducible or irreducible matrix.

to comprehend the pattern of premagic matrix

to compare the ideal flow matrix from reducible or irreducible stochastic matrix

to demonstrate the premagic pattern of the ideal flow matrix

to compare various total flow of the ideal flow matrix

Instruction

Use the lab tool below to convert a Capacity matrix into an Ideal Flow matrix.

Generate random capacity matrix by clicking

. The matrix is not necessarily irreducible. Thus, you may check using available operations in the selection. You can also modify the matrix manually. End each row by a semicolon. Separate each data in one row by comma or a space.

Set total flow and click to convert the stochastic matrix into an ideal flow matrix. Your network must be strongly connected (it means you capacity matrix must be irreducible).

Alternatively, set total flow and click Forced to convert Capacity to Ideal Flow Matrix

to forcely convert the stochastic matrix into an ideal flow matrix. Your network can be weakly connected.

Experiment and Discussion

Try the effect of parameter $ \kappa $.

Set various value for $ \kappa $ and check the total flow on the matrix by hovering on the bottom right cell. What is the meaning of parameter $ \kappa $?
Change the value of $ \kappa $ such that the result ideal flow are all integers. Use fraction form and find the least common multiple of the denominators?

Try the effect of parameters $ \alpha $ and $ \beta $.

If you set $ \alpha = 1$ and $ \beta =0.0001 $, happen ideal flow matrix?
If you set $ \alpha = 0.5$ and $ \beta =0.1 $, happen ideal flow matrix?
What happen if you set $ \alpha = 1 $ and $ \beta = 1 $?
At what parameter values, the smaller capacity get flow and larger capacity get smaller flow?
At what parameter values, the smaller capacity will get much smaller flow and larger capacity get larger flow?

Investigate pattern of capacity matrix

Create random capacity matrix which is reducible. What happens to the pattern of the ideal flow?
Create random capacity matrix which is irreducible. What happens to the pattern of the ideal flow?
Create random capacity matrix which is premagic. What happens to the pattern of the ideal flow?

Challenge yourself

If your capacity matrix contains a source node, what would happen to the ideal flow matrix?
If your capacity matrix contains a sink node, what would happen to the ideal flow matrix?
If your capacity matrix contains a source component, what would happen to the ideal flow matrix?
If your capacity matrix contains a sink component, what would happen to the ideal flow matrix?
Check the cycles in the capacity matrix using the select operations. How can you create ideal flow matrix using these cycles?

Lab Tool: Capacity to Ideal Flow

Generate Random Irreducible Capacity Matrix

size

Capacity matrix
$\alpha$: $\beta$:
0, 0, 0.9, 0.1; 0, 0, 0.2, 0.8; 0.7, 0.3, 0, 0; 0.1, 0.9, 0, 0;

Pattern of Capacity Matrix

$ \kappa $:

Forced to convert Stocastic to Ideal Flow Matrix

Flow matrix
Is Fraction:

Pattern of Flow Matrix

How to use:

Run: click Convert Stocastic Matrix to Ideal Flow Matrix.
Matrix: click to generate random matrix of certain size and draw the network.
Matrix Visualization: click to increase the matrix cell or do right click to reduce the matrix cell.
Click to redraw the network from the matrix
Zoom: Use to zoom in, to zoom out, or to reset the zoom level
Pan: use CTRL and mouse to drag on one of the node to pan the whole network

IFN Lab: Capacity to Ideal Flow Matrix

IFN Lab: Capacity to Ideal Flow Matrix

Brief Description

Learning Objectives

Prerequisite

Instruction

Experiment and Discussion

Lab Tool: Capacity to Ideal Flow