The Truth about Power Laws: Theory and Reality

We draw attention to a clear dichotomy between small-world networks exhibiting exponential neighborhood growth, and fractal-like networks where neighborhoods grow according to a power law. This distinction is observed in a number of real-world networks, and is related to the degree correlations and geographical constraints. We conclude by pointing out that the status of human social networks in this dichotomy is far from clear.

The degree distributions of complex networks are usually considered to be power law. However, it is not the case for a large number of them. We thus propose a new model able to build random growing networks with (almost) any wanted degree distribution. The degree distribution can either be theoretical or extracted from a real-world network. The main idea is to invert the recurrence equation commonly used to compute the degree distribution in order to find a convenient attachm...

The concept of scale-free networks has been widely applied across natural and physical sciences. Many claims are made about the properties of these networks, even though the concept of scale-free is often vaguely defined. We present tools and procedures to analyse the statistical properties of networks defined by arbitrary degree distributions and other constraints. Doing so reveals the highly likely properties, and some unrecognised richness, of scale-free networks, and cast...

Degree distribution models are incredibly important tools for analyzing and understanding the structure and formation of social networks, and can help guide the design of efficient graph algorithms. In particular, the Power-law degree distribution has long been used to model the structure of online social networks, and is the basis for algorithms and heuristics in graph applications such as influence maximization and social search. Along with recent measurement results, our i...

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...

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...

Complex networks have recently aroused a lot of interest. However, network edges are considered to be the same in almost all these studies. In this paper, we present a simple classification method, which divides the edges of undirected, unweighted networks into two types: p2c and p2p. The p2c edge represents a hierarchical relationship between two nodes, while the p2p edge represents an equal relationship between two nodes. It is surprising and unexpected that for many real-w...

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...

It is commonly believed that scale-free networks are robust to massive numbers of random node deletions. For example, Cohen et al. study scale-free networks including some which approximate the measured degree distribution of the Internet. Their results suggest that if each node in this network failed independently with probability 0.99, the remaining network would continue to have a giant component. In this paper, we show that a large and important subclass of scale-free net...

What makes economic and ecological networks so unlike other highly skewed networks in their tendency toward turbulence and collapse? Here, we explore the consequences of a defining feature of these networks: their nodes are tied together by flow. We show that flow networks tend to the power law degree distribution (PLDD) due to a self-reinforcing process involving position within the global network structure, and thus present the first random graph model for PLDDs that does n...