ID: 1305.7296

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

May 31, 2013

View on ArXiv
Kevin Judd, Michael Small, Thomas Stemler
Nonlinear Sciences
Computer Science
Physics
Adaptation and Self-Organizi...
Social and Information Netwo...
Computational Physics
Physics and Society

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 casts doubt on some previously claimed properties being due to a scale-free characteristic.

Similar papers 1

Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)

January 9, 2005

94% Match
Lun Li, David Alderson, Reiko Tanaka, ... , Willinger Walter
Disordered Systems and Neura...
Statistical Mechanics
Networking and Internet Arch...
Combinatorics
Molecular 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...

Find SimilarView on arXiv

Scale-free networks are rare

January 9, 2018

93% Match
Anna D. Broido, Aaron Clauset
Physics and Society
Social and Information Netwo...
Data Analysis, Statistics an...
Molecular Networks
Applications

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

Find SimilarView on arXiv

A surrogate for networks -- How scale-free is my scale-free network?

June 18, 2013

93% Match
Michael Small, Kevin Judd, Thomas Stemler
Physics and Society
Social and Information Netwo...
Adaptation and Self-Organizi...
Data Analysis, Statistics an...

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

Find SimilarView on arXiv

Scale-free Networks Well Done

November 5, 2018

93% Match
Ivan Voitalov, der Hoorn Pim van, ... , Krioukov Dmitri
Physics and Society
Social and Information Netwo...
Data Analysis, Statistics an...

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

Find SimilarView on arXiv

A statistical mechanics approach for scale-free networks and finite-scale networks

March 7, 2007

93% Match
Ginestra Bianconi
Disordered Systems and Neura...
Statistical Mechanics

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

Find SimilarView on arXiv

Degree distribution of complex networks from statistical mechanics principles

June 14, 2006

93% Match
Ginestra Bianconi
Statistical Mechanics
Disordered Systems and Neura...

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

Find SimilarView on arXiv

Characterizing the intrinsic correlations of scale-free networks

June 10, 2015

92% Match
Brito J. B. de, C. I. N. Sampaio Filho, ... , Andrade J. S. Jr
Physics and Society
Social and Information Netwo...

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

Find SimilarView on arXiv

Exactly scale-free scale-free networks

September 4, 2013

92% Match
Linjun Zhang, Michael Small, Kevin Judd
Physics and Society
Social and Information Netwo...
Adaptation and Self-Organizi...

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

Find SimilarView on arXiv

Scale-Free Networks beyond Power-Law Degree Distribution

October 12, 2023

92% Match
Xiangyi Meng, Bin Zhou
Physics and Society

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

Find SimilarView on arXiv

Problems with classification, hypothesis testing, and estimator convergence in the analysis of degree distributions in networks

March 31, 2020

92% Match
der Hoorn Pim van, Ivan Voitalov, ... , Krioukov Dmitri
Physics and Society
Social and Information Netwo...
Data Analysis, Statistics an...

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

Find SimilarView on arXiv