What is Ideal Flow Network?
What is IFN? In four words, IFN is irreducible premagic Markov equilibrium.
Ideal Flow Network (IFN) is special type of weighted directed graph (digraph) where two conditions are hold. First, the digraph is strongly connected and the weights must be positive and are called flow. Second, in each node, the flows are balanced. The total inflows must be equal to the total outflow. Since network graph is closely associated with matrix, we can define Ideal Flow matrix as a special type of non-negative square matrix where the binary (0,1) matrix structure is irreducible and the matrix is premagic. The vector sum of rows is equal to the transpose of the vector sum of columns. The values of the nodes and links in an IFN are special numbers because they represent the long-term equilibriums (i.e. steady state values) of Markov chain or random walk determined by the weighted of the directed graph.
To associate the graph theory and linear algebra, we know that irreducible matrix is equivalent to strongly connected digraph and premagic matrix is equivalent to preservation of flow in each node. Thus, the Ideal Flow network is equivalent to the Ideal Flow matrix. A strongly connected network is not necessarily premagic (i.e. to have balance flow between inflow and outflow for all nodes). However, premagic property can only happens when the network is strongly connected.
Ideal Flow on Network (IFN) is a strongly connected network with steady state relative link flow where the flows on each node are conserved. From Markov Chain theory, ideal flow network can also be seen as the limiting distribution of the relative flow on a simple strongly connected network subject to constraint of flow conservation. Another way to look at ideal flow network is through the perspective of random walk. In this case, ideal flow network is a flow aggregation of the trajectories of results of random walk over space and time on a network graph with a certain probability distribution on each node.
The main properties of IFN, which also the four axioms of IFN are as follow:
- Axiom 1: IFN is strongly connected (ideal flow matrix is irreducible)
- Axiom 2: the flows in IFN are conserved (the ideal flow matrix is premagic)
- Axiom 3: the flows in IFN represent steady-state equilibrium or limiting long-term distribution.
- Axiom 4: the decisions in each node of IFN follow Markov property (based on local information rather than global information)
IFN is purely mathematics. It is one of the laws of nature about closed system equilibrium. Irreducible means closed system. Premagic means equilibrium. The basic philosophy of IFN is this. If the each part (i.e. node) were in equilibrium, the whole system (i.e. network) would be automatically in equilibrium, as long as the system is closed.
IFN is not a panacea. When the network is not connected, or if the problem is not about a system in equilibrium, then we cannot represent it as flows in network. Similarly, IFN cannot be used if any of the four axioms of IFN is not satisfied.
In graph theory terminology, IFN is a special type of weighted directed graph where
- the digraph is strongly connected
- the weights (in nodes and links) are called flow
- in each node, the flow must be balanced: the total inflow must be equal to the total outflow.
- the link weights must be positive
Uniqueness of IFN
Given a strongly connected network (i.e. irreducible adjacency matrix), the IFN is not unique. However, given the stochastic matrix that is irreducible and aperiodic, then the IFN is unique up to a scale. Given the irreducible and aperiodic stochastic matrix and a total flow (i.e., total demand) in the network, then the IFN is unique.