Large-Scale Network Reduction Towards Scale-Free Structure

This paper deals with a particular problem of graph reduction. The reduced graph is aimed to have a particular structure, namely to be scale-free. To this end, we define a metric to measure the scale-freeness by measuring the difference between the degree distribution and the scale-free degree distribution. The reduction is made under constraints to preserve consistency with the initial graph. In particular, the reduced graph preserves the eigenvector centrality of the initial graph. We study the optimization problem and, based on the gained insights, we derive an algorithm allowing to find an approximate solution. We also show that, if the initial network is a flow network, it is possible to design the algorithm such that the output remains a flow network. Experimental results are then presented to optimally choose the parameters of the algorithm suggesting that, by tuning a parameter, it is possible to speed up the algorithm with a comparable efficiency. Finally, the algorithm is applied to an example of large physical network: the Grenoble urban traffic network.