January 15, 2019
We define the intrinsic scale at which a network begins to reveal its identity as the scale at which subgraphs in the network (created by a random walk) are distinguishable from similar sized subgraphs in a perturbed copy of the network. We conduct an extensive study of intrinsic scale for several networks, ranging from structured (e.g. road networks) to ad-hoc and unstructured (e.g. crowd sourced information networks), to biological. We find: (a) The intrinsic scale is surprisingly small (7-20 vertices), even though the networks are many orders of magnitude larger. (b) The intrinsic scale quantifies ``structure'' in a network -- networks which are explicitly constructed for specific tasks have smaller intrinsic scale. (c) The structure at different scales can be fragile (easy to disrupt) or robust.
Similar papers 1
June 27, 2024
Scale invariance profoundly influences the dynamics and structure of complex systems, spanning from critical phenomena to network architecture. Here, we propose a precise definition of scale-invariant networks by leveraging the concept of a constant entropy loss rate across scales in a renormalization-group coarse-graining setting. This framework enables us to differentiate between scale-free and scale-invariant networks, revealing distinct characteristics within each class. ...
June 6, 2001
Complex networks describe a wide range of systems in nature and society, much quoted examples including the cell, a network of chemicals linked by chemical reactions, or the Internet, a network of routers and computers connected by physical links. While traditionally these systems were modeled as random graphs, it is increasingly recognized that the topology and evolution of real networks is governed by robust organizing principles. Here we review the recent advances in the f...
We analyze about two hundred naturally occurring networks with distinct dynamical origins to formally test whether the commonly assumed hypothesis of an underlying scale-free structure is generally viable. This has recently been questioned on the basis of statistical testing of the validity of power law distributions of network degrees by contrasting real data. Specifically, we analyze by finite-size scaling analysis the datasets of real networks to check whether purported de...
May 16, 2017
The topology of any complex system is key to understanding its structure and function. Fundamentally, algebraic topology guarantees that any system represented by a network can be understood through its closed paths. The length of each path provides a notion of scale, which is vitally important in characterizing dominant modes of system behavior. Here, by combining topology with scale, we prove the existence of universal features which reveal the dominant scales of any networ...
March 25, 2003
Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment...
April 5, 1999
Small-world architectures may be implicated in a range of phenomena from disease propagation to networks of neurons in the cerebral cortex. While most of the recent attention on small-world networks has focussed on the effect of introducing disorder/randomness into a regular network, we show that that the fundamental mechanism behind the small-world phenomenon is not disorder/randomness, but the presence of connections of many different length scales. Consequently, in order t...
February 6, 2005
This article addresses the degree distribution of subnetworks, namely the number of links between the nodes in each subnetwork and the remainder of the structure (cond-mat/0408076). The transformation from a subnetwork-partitioned model to a standard weighted network, as well as its inverse, are formalized. Such concepts are then considered in order to obtain scale free subnetworks through design or through a dynamics of node exchange. While the former approach allows the imm...
August 3, 2000
Many complex systems, such as communication networks, display a surprising degree of robustness: while key components regularly malfunction, local failures rarely lead to the loss of the global information-carrying ability of the network. The stability of these complex systems is often attributed to the redundant wiring of the functional web defined by the systems' components. In this paper we demonstrate that error tolerance is not shared by all redundant systems, but it is ...
May 31, 2013
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...
January 9, 2005
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...