  Large real-world networks typically follow a power-law degree distribution.
To study such networks, numerous random graph models have been proposed.
However, real-world networks are not drawn at random. Therefore, Brach, Cygan,
{\L}acki, and Sankowski [SODA 2016] introduced two natural deterministic
conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and
(2) power-law neighborhoods, that is, the degree distribution of neighbors of
each vertex is also upper bounded by a power law (PLB-N). They showed that many
real-world networks satisfy both deterministic properties and exploit them to
design faster algorithms for a number of classical graph problems.
  We complement the work of Brach et al. by showing that some well-studied
random graph models exhibit both the mentioned PLB properties and additionally
also a power-law lower bound on the degree distribution (PLB-L). All three
properties hold with high probability for Chung-Lu Random Graphs and Geometric
Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As
a consequence, all results of Brach et al. also hold with high probability or
almost surely for those random graph classes.
  In the second part of this work we study three classical NP-hard
combinatorial optimization problems on PLB networks. It is known that on
general graphs with maximum degree {\Delta}, a greedy algorithm, which chooses
nodes in the order of their degree, only achieves an {\Omega}(ln
{\Delta})-approximation for Minimum Vertex Cover and Minimum Dominating Set,
and an {\Omega}({\Delta})-approximation for Maximum Independent Set. We prove
that the PLB-U property suffices for the greedy approach to achieve a
constant-factor approximation for all three problems. We also show that all
three combinatorial optimization problems are APX-complete, even if all
PLB-properties hold.
