Power law degree distributions alone imply that some nodes in
the tail of the power law must have high degree, but “hubs” imply something
more and are often said to “hold the network together.” The presence of a hublike
network core yields a “robust yet fragile” connectivity structure that has
become a hallmark of SF network models. Of particular interest here is that a
study of SF models of the Internet’s router topology is reported to show that
“the removal of just a few key hubs from the Internet splintered the system
into tiny groups of hopelessly isolated routers” [barab´asi and bonabeau 03].

Thus, apparently due to their hub-like core structure, SF networks are said to
be simultaneously robust to the random loss of nodes (i.e., error tolerance), since
these tend to miss hubs, but fragile to targeted worst-case attacks (i.e., attack
vulnerability) [albert et al. 00] on hubs. This latter property has been termed the
“Achilles’ heel” of SF networks, and it has featured prominently in discussions
about the robustness of many complex networks. Albert et al. [albert et al. 00]
even claim to “demonstrate that error tolerance... is displayed only by a class of
inhomogeneously wired networks, called scale-free networks” (emphasis added).
We will use the qualifier SF hubs to describe high-degree nodes that are so located
as to provide these “robust yet fragile” features described in the SF literature,
and a goal of this paper is to clarify more precisely what topological features of
graphs are involved.
There are a number of properties in addition to power law degree distributions,
random generation, and SF hubs that are associated with SF graphs, but
unfortunately, it is rarely made clear in the SF literature which of these features
define SF graphs and which features are then consequences of this definition.
This has led to significant confusion about the defining features or characteristics
of SF graphs and the applicability of these models to real systems. While
the usage of “scale-free” in the context of graphs has been imprecise, there is
nevertheless a large literature on SF graphs, particularly in the highest impact
general science journals. For purposes of clarity in this paper, we will use the
term SF graphs (or equivalently, SF networks) to mean those objects as studied
and discussed in this “SF literature,” and accept that this inherits from that
literature an imprecision as to what exactly SF means. One aim of this paper is
to capture as much as possible of the “spirit” of SF graphs by proving their most
widely claimed properties using a minimal set of axioms. Another is to reconcile
these theoretical properties with the properties of real networks, in particular
the router-level graphs of the Internet.