What exactly are the properties of scale-free and other networks?

Although the ``scale-free'' literature is large and growing, it gives neither a precise definition of scale-free graphs nor rigorous proofs of many of their claimed properties. In fact, it is easily shown that the existing theory has many inherent contradictions and verifiably false claims. In this paper, we propose a new, mathematically precise, and structural definition of the extent to which a graph is scale-free, and prove a series of results that recover many of the clai...

A central claim in modern network science is that real-world networks are typically "scale free," meaning that the fraction of nodes with degree $k$ follows a power law, decaying like $k^{-\alpha}$, often with $2 < \alpha < 3$. However, empirical evidence for this belief derives from a relatively small number of real-world networks. We test the universality of scale-free structure by applying state-of-the-art statistical tools to a large corpus of nearly 1000 network data set...

Complex networks are now being studied in a wide range of disciplines across science and technology. In this paper we propose a method by which one can probe the properties of experimentally obtained network data. Rather than just measuring properties of a network inferred from data, we aim to ask how typical is that network? What properties of the observed network are typical of all such scale free networks, and which are peculiar? To do this we propose a series of methods t...

We bring rigor to the vibrant activity of detecting power laws in empirical degree distributions in real-world networks. We first provide a rigorous definition of power-law distributions, equivalent to the definition of regularly varying distributions that are widely used in statistics and other fields. This definition allows the distribution to deviate from a pure power law arbitrarily but without affecting the power-law tail exponent. We then identify three estimators of th...

We present a statistical mechanics approach for the description of complex networks. We first define an energy and an entropy associated to a degree distribution which have a geometrical interpretation. Next we evaluate the distribution which extremize the free energy of the network. We find two important limiting cases: a scale-free degree distribution and a finite-scale degree distribution. The size of the space of allowed simple networks given these distribution is evaluat...

In this paper we describe the emergence of scale-free degree distributions from statistical mechanics principles. We define an energy associated to a degree sequence as the logarithm of the number of indistinguishable simple networks it is possible to draw given the degree sequence. Keeping fixed the total number of nodes and links, we show that the energy of scale-free distribution is much higher than the energy associated to the degree sequence of regular random graphs. Thi...

Very often, when studying topological or dynamical properties of random scale-free networks, it is tacitly assumed that degree-degree correlations are not present. However, simple constraints, such as the absence of multiple edges and self-loops, can give rise to intrinsic correlations in these structures. In the same way that Fermionic correlations in thermodynamic systems are relevant only in the limit of low temperature, the intrinsic correlations in scale-free networks ar...

Many complex natural and physical systems exhibit patterns of interconnection that conform, approximately, to a network structure referred to as scale-free. Preferential attachment is one of many algorithms that have been introduced to model the growth and structure of scale-free networks. With so many different models of scale-free networks it is unclear what properties of scale-free networks are typical, and what properties are peculiarities of a particular growth or constr...

Complex networks across various fields are often considered to be scale free -- a statistical property usually solely characterized by a power-law distribution of the nodes' degree $k$. However, this characterization is incomplete. In real-world networks, the distribution of the degree-degree distance $\eta$, a simple link-based metric of network connectivity similar to $k$, appears to exhibit a stronger power-law distribution than $k$. While offering an alternative character...

In their recent work "Scale-free networks are rare", Broido and Clauset address the problem of the analysis of degree distributions in networks to classify them as scale-free at different strengths of "scale-freeness." Over the last two decades, a multitude of papers in network science have reported that the degree distributions in many real-world networks follow power laws. Such networks were then referred to as scale-free. However, due to a lack of a precise definition, the...