IFN Lab: Capacity to Stochastic Matrix

By Kardi Teknomo, PhD

< Previous | Index | Next >

Brief Description

A capacity matrix \( \mathbf{C} \) is a nonnegative weighted adjacency matrix. A stochastic matrix \( \mathbf{S} \) is a matrix whose all of its row sums are one, to represent the outflow probability in each node of the network developed based on the capacity matrix. An irreducible capacity matrix would produce irreducible stochastic matrix \( \mathbf{S} \). 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.

Learning Objectives

• to understand the effect of parameters in converting stochastic matrix based on capacity matrix.
• to comprehend the pattern of stochastic matrix
• to comprehend the effect of irreducible or irreducible capacity matrix.
• to comprehend the effect of pattern of premagic capacity matrix
• to compare the stochastic matrix from reducible or irreducible capacity matrix

Prerequisite

Read: Graph Theory and Linear Algebra

Instruction

You can use the program below to convert capacity matrix into a Markov stochastic matrix.

1. Click to generate random capacity matrix.
2. You can modify the input capacity matrix. It must be a non-negative square matrix and irreducible. End each row separated by a semicolon. Separate each data in one row by comma or a space. Your network must not contain any sink node.
3. Click the arrow to Convert Capacity to Stocastic Matrix.

Experiment and Discussion

The function below is a generalized model to convert capacity matrix to stochastic matrix. Each element of the capacity matrix is raised to the power of α and then multiplied by the exponential of β times the same element. The sum in the denominator is over all such transformed elements in the same row. In matrix form, this can be represented as follows: 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} \).

• Try the effect of parameters \( \alpha \) and \( \beta \).
1. If you set \( \alpha = 1\) and \( \beta =0.0001 \), will you would produces the same results as proportional capacity model without parameter? $$ s_{ij} = \frac{c_{ij}}{\sum_{k=1}^{n} c_{ik}} $$
2. If you set \( \alpha = 0.5\) and \( \beta =0.1 \), will the proportion go toward middle value, which will balance the probability? Use fraction format to see the probability distribution better.
3. What happen if you set \( \alpha = 1 \) and \( \beta = 1 \)? Will the probability distribution becomes more extreme than proportional capacity. Use fraction format to see the distribution better.
4. At what parameter values, the smaller capacity get larger probability and larger capacity get smaller probability compared to the proportional capacity?
5. At what parameter values, the smaller capacity will get much smaller probability and larger capacity get larger probability compared to the proportional capacity?
• Investigate pattern of stochastic matrix
1. What is the sum of each row in the stochastic matrix? Hover your mouse on the sum of each row
2. If your capacity matrix is premagic, what would happen to the stochastic matrix? Is there any efect?
3. If your capacity matrix is irreducible (the network is strongly connected), what would happen to the stochastic matrix?
4. If your capacity matrix is reducible (the network is weakly connected), what would happen to the stochastic matrix?
1. If your capacity matrix contains a source node, what would happen to the stochastic matrix?
2. If your capacity matrix contains a sink node, what would happen to the stochastic matrix?
3. If your capacity matrix contains a source component, what would happen to the stochastic matrix?
4. If your capacity matrix contains a sink component, what would happen to the stochastic matrix?
• Challenge yourself
• What pattern of capacity matrix would always produce doubly stochastic matrix where the sum of each row and each column are equal to one?
• Is doubly stochastic matrix always an ideal flow matrix?

Lab Tool: Capacity to Stochastic

size

Capacity matrix
\(\alpha\): \(\beta\):
5, 1, 1, 2; 0, 0, 1, 0; 2, 0, 0, 2; 2, 0, 0, 0;
--Select an operation-- Is Irreducible? Is Premagic? Is Stochastic? Is Ideal Flow?

Pattern of Stochastic Matrix

Stochastic matrix
Is Fraction: Accuracy: 1 2 3 4 5 6 7 8 9 10

--Select an operation-- Is Irreducible? Is Premagic? Is Stochastic? Is Ideal Flow?

Pattern of Stochastic Matrix

Network of Capacity Matrix

IFN Lab: Capacity to Stochastic Matrix

Index