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 an heuristic method that allows to find near-optimal solutions to the covering problem in real communication networks. The results show that the optimal allocation of resources strongly depends on the topology of the underlying networks. Whether a centralized or distributed design is to be used relies upon the degree correlations between connected vertices.

APS format. Version to appear in Physical Review E (Rapid Communication)

References in corpus (14)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Assortative mixing in networks
• Evolution of networks
• Dynamical and correlation properties of the Internet
• Immunization of complex networks
• Search in Power-Law Networks
• Efficient Immunization Strategies for Computer Networks and Populations
• Halting viruses in scale-free networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Computational complexity arising from degree correlations in networks

Cited by in corpus (20)

• Statistical physics of vaccination
• Multiple routes transmitted epidemics on multiplex networks
• The Evolutionary Vaccination Dilemma in Complex Networks
• Structure of Peer-to-Peer Social Networks
• Immunization of Real Complex Communication Networks
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Message passing for vertex covers
• Statistical Mechanics of the Minimum Dominating Set Problem
• Spreading dynamics on small-world networks with connectivity fluctuations and correlations
• Local Empathy provides Global Minimization of Congestion in Communication Networks
• Correlations in random Apollonian network
• Building Damage-Resilient Dominating Sets in Complex Networks against Random and Targeted Attacks
• Dominating Scale-Free Networks Using Generalized Probabilistic Methods
• Effect of degree correlations above the first shell on the percolation transition
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Scale-Free topologies and Activatory-Inhibitory interactions
• Generalized minimum dominating set and application in automatic text summarization
• Identification of intrinsic long-range degree correlations in complex networks
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Assortativity in Generalized Preferential Attachment Models