Computational complexity arising from degree correlations in networks

Abstract

We apply a Bethe-Peierls approach to statistical-mechanics models defined on random networks of arbitrary degree distribution and arbitrary correlations between the degrees of neighboring vertices. Using the NP-hard optimization problem of finding minimal vertex covers on these graphs, we show that such correlations may lead to a qualitatively different solution structure as compared to uncorrelated networks. This results in a higher complexity of the network in a computational sense: Simple heuristic algorithms fail to find a minimal vertex cover in the highly correlated case, whereas uncorrelated networks seem to be simple from the point of view of combinatorial optimization.

4 pages, 1 figure, accepted in Phys. Rev. E

Cited by in corpus (32)

• The structure and function of complex networks
• Mixing patterns in networks
• Critical phenomena in complex networks
• Dynamics of Rumor Spreading in Complex Networks
• Theory of Rumour Spreading in Complex Social Networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Epidemic Incidence in Correlated Complex Networks
• Self-similar disk packings as model spatial scale-free networks
• Characterizing the network topology of the energy landscapes of atomic clusters
• Immunization of Real Complex Communication Networks
• (Un)detectable cluster structure in sparse networks
• Disease Spreading in Structured Scale-Free Networks
• Message passing for vertex covers
• Distance-d covering problems in scale-free networks with degree correlations
• Generation of arbitrarily two-point correlated random networks
• Spreading dynamics on small-world networks with connectivity fluctuations and correlations
• Statistical mechanics of the vertex-cover problem
• Cavity analysis on the robustness of random networks against targeted attacks: Influences of degree-degree correlations
• Criticality on networks with topology-dependent interactions
• Non-Markov stochastic dynamics of real epidemic process of respiratory infections
• Properties of atypical graphs from negative complexities
• Network rewiring in the $r$-$K$ plane
• Generation of scale-free assortative networks via Newman rewiring for simulation of diffusion phenomena
• Research on Solution Space of Bipartite Graph Vertex-Cover by Maximum Matchings
• Typical Performance of Approximation Algorithms for NP-hard Problems
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Optimal Vertex Cover for the Small-World Hanoi Networks
• Ising Model on Edge-Dual of Random Networks
• Organization mechanism and counting algorithm on Vertex-Cover solutions
• Zero forcing number of graphs with a power law degree distribution
• Characterizing Information Spreading in Online Social Networks
• Diagonal degree correlations vs. epidemic threshold in scale-free networks