IFN Lab: Equivalent IFN

By Kardi Teknomo, PhD

< Previous | Index | Next >

Brief Description

Two IFNs where each link flow of one network is a positive scaling of the other network are called equivalent IFNs. Suppose \( \mathbf{N_{1} = \) and \( \mathbf{N_{2} = \) are two ideal flow networks. The two IFNs are called equivalent if and only if each corresponding link flow of one network is a multiple of the other network by a positive global scaling ς. $$ \mathbf{N_{1}} \equiv \mathbf{N_{2}} \Leftrightarrow \mathbf{N_{1}}=\varsigma \mathbf{N_{2}}, \varsigma > 0 $$

Equivalent IFNs have characteristics that they share the same stochastic matrix, the same average-node-entropy and the same coefficient of variation of the flow.

If two ideal flow networks are equivalent then they have the same stochastic matrix. The converse is also true. If two ideal flow networks have the same stochastic matrix, they are necessarily equivalent IFNs. In fact, because the computation of ideal flow matrix from stochastic matrix is using Moore Penrose Inverse and the Moore Penrose Inverse is unique, then the ideal flow matrix is unique for each its stochastic matrix.

We can view the stochastic matrix as local information for each agent to select which link to go in the random walk on network. In this case, the basis ideal flow matrix (where the total flow is one) can be viewed as the global information on the probability of each link. Thus, conversion from stochastic matrix to ideal flow matrix and vice versa can be viewed as the transformation of local into global information and vice versa.

There are several standard forms of equivalent IFNs:

• Basis Network: the total flow in IFN is one (κ=1). Divide each link flow with the total flow to obtain this form. Obviously, the flow values would be between zero and one.
• Unit-Min Network: the minimum flow in network is one. Divide each link flow with the minimum flow to obtain this form.
• Unit-Max Network: the maximum flow in the network is one. Divide each link flow with the maximum flow to obtain this form.
• Cardinal Network: the link flows are all integer, which is minimum. Set the link flows into fraction, and then multiply each link flow with the least common multiple (LCM) of the denominator of all flows in the network to obtain this form.
• Unit-Std Network: the standard deviation of the flow is one. Divide each link flow with the standard deviation of the flow to obtain this form.
• Unit-Avg Network: the average flow in the network is one. Divide each link flow with the average flow to obtain this form.

Learning Objectives

• to understand the effect of scaling factor in converting equivalent IFN
• to understand the characteristics of equivalent IFN

Prerequisite

Read: Graph Theory and Linear Algebra

Instruction

1. Click to generate random ideal flow matrix
2. Select any standard equivalent IFN to find the scaling factor. You can also set your own positive scaling factor
3. Click the arrow in the Lab Tool below to convert the IFN (left) to the equivalent IFN (right) by setting the positive scaling factor.
4. Alternatively, click to generate random capacity matrix and modify manually into an ideal flow matrix (premagic and irrducible). The input ideal flow matrix must be a non-negative square matrix, irreducible and premagic. End each row separated by a semicolon. Separate each data in one row by comma or a space.

Experiment and Discussion

• Standard Form of Equivalent IFN.
1. Generate Random IFN of a certain size, find the equivalent standard form of IFN and its scaling factor from the basis network.
2. From cardinal network, set a positive scaling factor to get the equivalent IFN such that the total flow would be 1000.
3. From basis network, set the value into fraction, then guess the scaling factor in order to obtain cardinal network. What is the LCM of the denominator?
• Investigate the characteristics of equivalent IFN
1. Generate Random IFN of a certain size, compute the stochastic matrix, average-node-entropy, average flow, standard deviation of flow and the coefficient of variation of the flow
2. Set the scaling factor to generate the equivalent IFN. Which of the following has not change (invariant) by your scaling?
3. If your capacity matrix is irreducible (the network is strongly connected), what would happen to the stochastic matrix? stochastic matrix, average-node-entropy, average flow, standard deviation of flow or the coefficient of variation of the flow
• Challenge yourself
• Generate irreducible random capacity matrix. Can you manually change into integer ideal flow matrix?
• Integer Network tends to be very sensitive to small decimal variation. How do you get Cardinal network which has the minimum integer flows in the network?
• What other characteristics of equivalent IFN? Can you find the other invariances?

Lab Tool: Equivalent IFN

κ: size:

Ideal Flow matrix
Is Fraction: Accuracy: 1 2 3 4 5 6 7 8 9 10
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? List Cycles

Pattern of Ideal Flow Matrix

Standard IFN Equivalent:
--Select a format-- Basis Network Integer Network Unit-Min Network Unit-Max Network
Scaling:
Report: (below)
Sum of Flow
Average of Flow
Standard Deviation of Flow
Coef. Variation of Flow
Average Node Entropy
Stochastic Matrix

Equivalent Ideal Flow 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 Equivalent Ideal Flow Matrix

Ideal Flow Network

IFN Lab: Equivalent IFN

Index