We investigate how the underlying graph of a network supports a flow between a source node and a destination node and propose to compute the expected number of nodes and links that contribute to transferring items in random graphs. Since the transportation is associated with a \quotes{ cost} or \quotes{ power dissipation}, we further address how to construct a graph given predetermined end-to-end power dissipation, which can be reduced to the \quotes{ inverse effective resistance problem} that asks for a weighted graph in which the effective resistance matrix equals a predetermined demand matrix. We propose a heuristic algorithm, \quotes{ Resistor Gap Pruning} (RGP), which provides sparse graphs closely approximating the demand effective resistance and which shows stable performance across different demand scenarios.

Categories: math-ph math.MP

Flow Subgraphs and Flow Network Design under End-to-End Power Dissipation Constraints