Distance-d covering problems in scale-free networks with degree correlations

Abstract

A number of problems in communication systems demand the distributed allocation of network resources in order to provide better services, sampling, and distribution methods. The solution to these issues is becoming more challenging due to the increasing size and complexity of communication networks. We report here on a heuristic method to find near-optimal solutions to the covering problem in real communication networks, demonstrating that whether a centralized or a distributed design is to be used relies upon the degree correlations between connected vertices. We also show that the general belief that by targeting the hubs one can efficiently solve most problems on networks with a power-law degree distribution is not valid for assortative networks.