Gradient Network - The Congestion On Networks

The Congestion On Networks

The fact that topology of substrate network influence the level of congestion can be illustrated by simple example(Fig.6.) as following: if the network has a star-like structure, then at the central node, the flow would congeste because the central node should handle all flow from others nodes. On the contrary, if the network has a ring-like structure, since every node take same role for transportation there is no traffic jam of flow.

Under assumption that the flow is generated by gradients in the network, characterize efficiency of flow on networks can be characterized through the jamming factor(or congestion factor) defined as:

where N_receive is the number of nodes that receive gradient flow and N_send is the number of nodes that send the flow. The value of J is in the range between 0 and 1. J = 0 means no congestion, and J = 1 corresponds to maximal congestion. In the limit N → ∞,and the probability with which two arbitrary nodes are connected is constant, for random network, the congestion factor becomes

This result show that random networks are maximally congested in that limit. On the contrary, for scale-free network, J is always a constant for any N. This conclusion means scale-free networks are not prone to maximal jamming.