Correlation dimension of complex networks

Intrinsic dimension as a multi-scale summary statistics in network modeling

Complex networks are powerful mathematical tools for modelling and understanding the behaviour of highly interconnected systems. However, existing methods for analyzing these networks focus on local properties (e.g. degree distribution, clustering coefficient) or global properties (e.g. diameter, modularity) and fail to characterize the network structure across multiple scales. In this paper, we introduce a rigorous method for calculating the intrinsic dimension of unweighted networks. The intrinsic dimension is a feature that describes the network structure at all scales, from local to global. We propose using this measure as a summary statistic within an Approximate Bayesian Computation framework to infer the parameters of flexible and multi-purpose mechanistic models that generate complex networks. Furthermore, we present a new mechanistic model that can reproduce the intrinsic dimension of networks with large diameters, a task that has been challenging for existing models.

Does the brain behave like a (complex) network? I. Dynamics

Graph theory is now becoming a standard tool in system-level neuroscience. However, endowing observed brain anatomy and dynamics with a complex network structure does not entail that the brain actually works as a network. Asking whether the brain behaves as a network means asking whether network properties count. From the viewpoint of neurophysiology and, possibly, of brain physics, the most substantial issues a network structure may be instrumental in addressing relate to the influence of network properties on brain dynamics and to whether these properties ultimately explain some aspects of brain function. Here, we address the dynamical implications of complex network, examining which aspects and scales of brain activity may be understood to genuinely behave as a network. To do so, we first define the meaning of networkness, and analyse some of its implications. We then examine ways in which brain anatomy and dynamics can be endowed with a network structure and discuss possible ways in which network structure may be shown to represent a genuine organisational principle of brain activity, rather than just a convenient description of its anatomy and dynamics.

Correlation dimension in empirical networks

Network correlation dimension governs the distribution of network distance in terms of a power-law model and profoundly impacts both structural properties and dynamical processes. We develop new maximum likelihood methods which allow us robustly and objectively to identify network correlation dimension and a bounded interval of distances over which the model faithfully represents structure. We also compare the traditional practice of estimating correlation dimension by modeling as a power law the fraction of nodes within a distance to a proposed alternative of modeling as a power law the fraction of nodes at a distance. In addition, we illustrate a likelihood ratio technique for comparing the correlation dimension and small-world descriptions of network structure. Improvements from our innovations are demonstrated on a diverse selection of synthetic and empirical networks. We show that the network correlation dimension model accurately captures empirical network structure over neighborhoods of substantial size and span and outperforms the alternative small-world network scaling model. Our improved methods tend to lead to higher estimates of network correlation dimension, implying that prior studies could have produced or utilized systematic underestimates of dimension.

Detecting the ultra low dimensionality of real networks

Reducing dimension redundancy to find simplifying patterns in high-dimensional datasets and complex networks has become a major endeavor in many scientific fields. However, detecting the dimensionality of their latent space is challenging but necessary to generate efficient embeddings to be used in a multitude of downstream tasks. Here, we propose a method to infer the dimensionality of networks without the need for any a priori spatial embedding. Due to the ability of hyperbolic geometry to capture the complex connectivity of real networks, we detect ultra low dimensionality far below values reported using other approaches. We applied our method to real networks from different domains and found unexpected regularities, including: tissue-specific biomolecular networks being extremely low dimensional; brain connectomes being close to the three dimensions of their anatomical embedding; and social networks and the Internet requiring slightly higher dimensionality. Beyond paving the way towards an ultra efficient dimensional reduction, our findings help address fundamental issues that hinge on dimensionality, such as universality in critical behavior.

A scale-dependent measure of system dimensionality

A fundamental problem in science is uncovering the effective number of degrees of freedom in a complex system: its dimensionality. A system’s dimensionality depends on its spatiotemporal scale. Here, we introduce a scale-dependent generalization of a classic enumeration of latent variables, the participation ratio. We demonstrate how the scale-dependent participation ratio identifies the appropriate dimension at local, intermediate, and global scales in several systems such as the Lorenz attractor, hidden Markov models, and switching linear dynamical systems. We show analytically how, at different limiting scales, the scale-dependent participation ratio relates to well-established measures of dimensionality. This measure applied in neural population recordings across multiple brain areas and brain states shows fundamental trends in the dimensionality of neural activity—for example, in behaviorally engaged versus spontaneous states. Our novel method unifies widely used measures of dimensionality and applies broadly to multivariate data across several fields of science.

•

The scale-dependent dimensionality unifies widely used measures of dimensionality

•

Dynamical systems show distinct dimensionality properties at different scales

•

The scale-dependent dimensionality allows us to identify critical scales of the system

•

Fundamental trends in dimensionality of neural activity depend on the brain state

Data mining is based on the discovery of structure within data. However, such a structure is often complex. The fact that the properties of data distributions vary depending on the scale at which they are examined is a fundamental component of this complexity. For example, a manifold may appear smooth at small scales but jagged or even fractal at larger scales. This scale dependence is critical, yet it is commonly overlooked. We introduce a fundamental approach for analyzing the properties of data distributions at all scales. This single scale-dependent description enables simultaneous examination of how characteristics vary across all scales, offering insight into the structure of the data distribution. This will help us gain a better grasp of data structures and pave the way for future theoretical advances in data science.

Relative, local and global dimension in complex networks

Dimension is a fundamental property of objects and the space in which they are embedded. Yet ideal notions of dimension, as in Euclidean spaces, do not always translate to physical spaces, which can be constrained by boundaries and distorted by inhomogeneities, or to intrinsically discrete systems such as networks. To take into account locality, finiteness and discreteness, dynamical processes can be used to probe the space geometry and define its dimension. Here we show that each point in space can be assigned a relative dimension with respect to the source of a diffusive process, a concept that provides a scale-dependent definition for local and global dimension also applicable to networks. To showcase its application to physical systems, we demonstrate that the local dimension of structural protein graphs correlates with structural flexibility, and the relative dimension with respect to the active site uncovers regions involved in allosteric communication. In simple models of epidemics on networks, the relative dimension is predictive of the spreading capability of nodes, and identifies scales at which the graph structure is predictive of infectivity. We further apply our dimension measures to neuronal networks, economic trade, social networks, ocean flows, and to the comparison of random graphs.

Defining the dimension in bounded, inhomogeneous or discrete physical systems may be challenging. The authors introduce here a dynamics-based notion of dimension by analysing diffusive processes in space, relevant for non-ideal physical systems and networks.

Epidemic dynamics on higher-dimensional small world networks

Dimension governs dynamical processes on networks. The social and technological networks which we encounter in everyday life span a wide range of dimensions, but studies of spreading on finite-dimensional networks are usually restricted to one or two dimensions. To facilitate investigation of the impact of dimension on spreading processes, we define a flexible higher-dimensional small world network model and characterize the dependence of its structural properties on dimension. Subsequently, we derive mean field, pair approximation, intertwined continuous Markov chain and probabilistic discrete Markov chain models of a COVID-19-inspired susceptible-exposed-infected-removed (SEIR) epidemic process with quarantine and isolation strategies, and for each model identify the basic reproduction number R 0 , which determines whether an introduced infinitesimal level of infection in an initially susceptible population will shrink or grow. We apply these four continuous state models, together with discrete state Monte Carlo simulations, to analyse how spreading varies with model parameters. Both network properties and the outcome of Monte Carlo simulations vary substantially with dimension or rewiring rate, but predictions of continuous state models change only slightly. A different trend appears for epidemic model parameters: as these vary, the outcomes of Monte Carlo change less than those of continuous state methods. Furthermore, under a wide range of conditions, the four continuous state approximations present similar deviations from the outcome of Monte Carlo simulations. This bias is usually least when using the pair approximation model, varies only slightly with network size, and decreases with dimension or rewiring rate. Finally, we characterize the discrepancies between Monte Carlo and continuous state models by simultaneously considering network efficiency and network size.

An Extended Correlation Dimension of Complex Networks

Fractal and self-similarity are important characteristics of complex networks. The correlation dimension is one of the measures implemented to characterize the fractal nature of unweighted structures, but it has not been extended to weighted networks. In this paper, the correlation dimension is extended to the weighted networks. The proposed method uses edge-weights accumulation to obtain scale distances. It can be used not only for weighted networks but also for unweighted networks. We selected six weighted networks, including two synthetic fractal networks and four real-world networks, to validate it. The results show that the proposed method was effective for the fractal scaling analysis of weighted complex networks. Meanwhile, this method was used to analyze the fractal properties of the Newman–Watts (NW) unweighted small-world networks. Compared with other fractal dimensions, the correlation dimension is more suitable for the quantitative analysis of small-world effects.

Lifespan Changes in Network Structure and Network Topology Dynamics During Rest and Auditory Oddball Performance

Behavioral and physiological evidence suggests that developmental changes lead to enhanced cortical differentiation and integration through maturation and learning, and that senescent changes during aging result in dedifferentiation and reduced cortical specialization of neural cell assemblies. We used electroencephalographic (EEG) recordings to evaluate network structure and network topology dynamics during rest with eyes closed and open, and during auditory oddball task across the lifespan. For this evaluation, we constructed a hyper-frequency network (HFN) based on within- and cross-frequency coupling (WFC and CFC, respectively) at 10 oscillation frequencies ranging between 2 and 20 Hz. We found that WFC increased monotonously across the lifespan, whereas CFC showed a U-shaped relationship. These changes in WFC and CFC strengths coevolve with changes in network structure and network topology dynamics, namely the magnitude of graph-theoretical topology measures increased linearly with age (except for characteristic path length, which is going shorter), while their standard deviation showed an inverse U-shaped relationship with a peak in young adults. Temporal as well as structural or nodal similarity of network topology (with some exceptions) seems to coincide with variability changes, i.e., stronger variability is related to higher similarity between consecutive time windows or nodes. Furthermore, network complexity measures showed different lifespan-related patterns, which depended on the balance of WFC and CFC strengths. Both variability and complexity of HFNs were strongly related to the perceptual speed scores. Finally, investigation of the modular organization of the networks revealed higher number of modules and stronger similarity of community structures across time in young adults as compared with children and older adults. We conclude that network variability and complexity measures reflect temporal and structural topology changes in the functional organization and reorganization of neuronal cell assemblies across the lifespan.

Relationship between Entropy and Dimension of Financial Correlation-Based Network

We analyze the dimension of a financial correlation-based network and apply our analysis to characterize the complexity of the network. First, we generalize the volume-based dimension and find that it is well defined by the correlation-based network. Second, we establish the relationship between the Rényi index and the volume-based dimension. Third, we analyze the meaning of the dimensions sequence, which characterizes the level of departure from the comparison benchmark based on the randomized time series. Finally, we use real stock market data from three countries for empirical analysis. In some cases, our proposed analysis method can more accurately capture the structural differences of networks than the power law index commonly used in previous studies.

Power-Hop: A Pervasive Observation for Real Complex Networks

Complex networks have been shown to exhibit universal properties, with one of the most consistent patterns being the scale-free degree distribution, but are there regularities obeyed by the r-hop neighborhood in real networks? We answer this question by identifying another power-law pattern that describes the relationship between the fractions of node pairs C(r) within r hops and the hop count r. This scale-free distribution is pervasive and describes a large variety of networks, ranging from social and urban to technological and biological networks. In particular, inspired by the definition of the fractal correlation dimension D₂ on a point-set, we consider the hop-count r to be the underlying distance metric between two vertices of the network, and we examine the scaling of C(r) with r. We find that this relationship follows a power-law in real networks within the range 2 ≤ r ≤ d, where d is the effective diameter of the network, that is, the 90-th percentile distance. We term this relationship as power-hop and the corresponding power-law exponent as power-hop exponent h. We provide theoretical justification for this pattern under successful existing network models, while we analyze a large set of real and synthetic network datasets and we show the pervasiveness of the power-hop.

A new method to measure complexity in binary or weighted networks and applications to functional connectivity in the human brain

BACKGROUND

Networks or graphs play an important role in the biological sciences. Protein interaction networks and metabolic networks support the understanding of basic cellular mechanisms. In the human brain, networks of functional or structural connectivity model the information-flow between cortex regions. In this context, measures of network properties are needed. We propose a new measure, Ndim, estimating the complexity of arbitrary networks. This measure is based on a fractal dimension, which is similar to recently introduced box-covering dimensions. However, box-covering dimensions are only applicable to fractal networks. The construction of these network-dimensions relies on concepts proposed to measure fractality or complexity of irregular sets in [Formula: see text].

RESULTS

The network measure Ndim grows with the proliferation of increasing network connectivity and is essentially determined by the cardinality of a maximum k-clique, where k is the characteristic path length of the network. Numerical applications to lattice-graphs and to fractal and non-fractal graph models, together with formal proofs show, that Ndim estimates a dimension of complexity for arbitrary graphs. Box-covering dimensions for fractal graphs rely on a linear log-log plot of minimum numbers of covering subgraph boxes versus the box sizes. We demonstrate the affinity between Ndim and the fractal box-covering dimensions but also that Ndim extends the concept of a fractal dimension to networks with non-linear log-log plots. Comparisons of Ndim with topological measures of complexity (cost and efficiency) show that Ndim has larger informative power. Three different methods to apply Ndim to weighted networks are finally presented and exemplified by comparisons of functional brain connectivity of healthy and depressed subjects.

CONCLUSION

We introduce a new measure of complexity for networks. We show that Ndim has the properties of a dimension and overcomes several limitations of presently used topological and fractal complexity-measures. It allows the comparison of the complexity of networks of different type, e.g., between fractal graphs characterized by hub repulsion and small world graphs with strong hub attraction. The large informative power and a convenient computational CPU-time for moderately sized networks may make Ndim a valuable tool for the analysis of biological networks.

Analytical estimation of the correlation dimension of integer lattices

Recently [L. Lacasa and J. Gómez-Gardeñes, Phys. Rev. Lett. 110, 168703 (2013)], a fractal dimension has been proposed to characterize the geometric structure of networks. This measure is an extension to graphs of the so called correlation dimension, originally proposed by Grassberger and Procaccia to describe the geometry of strange attractors in dissipative chaotic systems. The calculation of the correlation dimension of a graph is based on the local information retrieved from a random walker navigating the network. In this contribution, we study such quantity for some limiting synthetic spatial networks and obtain analytical results on agreement with the previously reported numerics. In particular, we show that up to first order, the correlation dimension β of integer lattices ℤ(d) coincides with the Haussdorf dimension of their coarsely equivalent Euclidean spaces, β = d.

Time-series analysis of networks: exploring the structure with random walks

We generate time series from scale-free networks based on a finite-memory random walk traversing the network. These time series reveal topological and functional properties of networks via their temporal correlations. Remarkably, networks with different node-degree mixing patterns exhibit distinct self-similar characteristics. In particular, assortative networks are transformed into time series with long-range correlation, while disassortative networks are transformed into time series exhibiting anticorrelation. These relationships are consistent across a diverse variety of real networks. Moreover, we show that multiscale analysis of these time series can describe and classify various physical networks ranging from social and technological to biological networks according to their functional origin. These results suggest that there is a unified dynamical mechanism that governs the structural organization of many seemingly different networks.

Geometrical invariability of transformation between a time series and a complex network

We present a dynamically equivalent transformation between time series and complex networks based on coarse geometry theory. In terms of quasi-isometric maps, we characterize how the underlying geometrical characters of complex systems are preserved during transformations. Fractal dimensions are shown to be the same for time series (or complex network) and its transformed counterpart. Results from the Rössler system, fractional Brownian motion, synthetic networks, and real networks support our findings. This work gives theoretical evidences for an equivalent transformation between time series and networks.