Visibility graphs of random scalar fields and spatial data

We extend the family of visibility algorithms to map scalar fields of arbitrary dimension into graphs, enabling the analysis of spatially extended data structures as networks. We introduce several possible extensions and provide analytical results on the topological properties of the graphs associated to different types of real-valued matrices, which can be understood as the high and low disorder limits of real-valued scalar fields. In particular, we find a closed expression for the degree distribution of these graphs associated to uncorrelated random fields of generic dimension. This result holds independently of the field's marginal distribution and it directly yields a statistical randomness test, applicable in any dimension. We showcase its usefulness by discriminating spatial snapshots of two-dimensional white noise from snapshots of a two-dimensional lattice of diffusively coupled chaotic maps, a system that generates high dimensional spatiotemporal chaos. The range of potential applications of this combinatorial framework includes image processing in engineering, the description of surface growth in material science, soft matter or medicine, and the characterization of potential energy surfaces in chemistry, disordered systems, and high energy physics. An illustration on the applicability of this method for the classification of the different stages involved in carcinogenesis is briefly discussed.

Figure 1

Illustration of a sample time series and the construction of the associated horizontal visibility graph (HVG) and visibility graph (VG) following the definition and criteria given by Eqs. (1) and (2).

Figure 2

Illustration of two extension classes of visibility algorithms in a dimension $d=2$ data set (gray box matrix). In the canonical extension (a) for a given datum (green box) a visibility algorithm is evaluated along the vertical and horizontal directions. In the fcc extension (b) visibility is considered also along the diagonals crossing the green box.

Figure 3

Illustration of the ${\mathrm{IHVG}}_8$ construction. (a) Plots a sample square matrix, where the central entry in the matrix is selected (with value 0.5). Horizontal visibility criterion [Eq. (2)] along four lines (fcc extension class, blue arrows) is then applied to select visible data points over the image and field (red boxed pixels). (b) The connectivity pattern of the node associated to the selected entry is shown. By sequentially applying the algorithm to all the pixels in the matrix, the corresponding ${\mathrm{IHVG}}_8$ can be fully determined. To obtain the connectivity patterns of that node within ${\mathrm{IVG}}_8$ instead, one only needs to switch the linking criterion from Eq. (2) to Eq. (1).

Figure 4

(a) Semi-log plot of the degree distribution (ensemble averaged over 10 realizations) of ${\mathrm{IHVG}}_8$ associated to $N\times N$ matrices with i.i.d. uniform U[0,1]random entries, for $N=2^7,2^8,\cdots ,2^{12}$. The solid line is the theoretical value of $P\left(k\right)$ given by Eq. (3) for $n=8$. In every case we find excellent agreement for $k<k_0$, where $k_0$ is a cutoff value that denotes the onset of finite size effects. (b) Linear-log plot of the cutoff $k_0$ as a function of the system's size $N$ for the same data of (a), suggesting a logarithmic scaling $k_0\sim clogN$.

Figure 5

Gray scale plots of $200\times 200$ matrices describing (a) i.i.d. uniform U[0,1] random variables (uniform white noise); (b) a snapshot of a two-dimensional lattice of diffusively coupled chaotic logistic maps with coupling strength $\epsilon =0$ (effectively being uncoupled and therefore a snapshot of uncorrelated beta distributed white noise); (c) the same coupled map lattice for weak coupling $\epsilon =0.1$ for which the system displays fully developed turbulence (a state of spatiotemporal chaos with a high-dimensional attractor); (d) the same coupled map lattice for strong coupling $\epsilon =0.7$. In this latter case the system shows strong spatial correlations and is easily distinguishable from the rest.

Figure 6

(a) Semi-log plot of the degree distribution of ${\mathrm{IHVG}}_8$ associated to a two-dimensional uncorrelated random field of uniform random variables (black dots), and two-dimensional coupled map lattices of diffusively coupled fully chaotic logistic maps, for coupling constant $\epsilon =0$ (diamonds) and $\epsilon =0.1$ (crosses). The solid line is Eq. (3) for $n=8$. Deviations from the exponential law in the tail are due to finite size effects (in every case matrices are $200\times 200$). Note that the $\epsilon =0$ case is effectively a spatially uncorrelated field with i.i.d. entries (with marginal distribution equivalent to the invariant measure of an isolated logistic map, i.e., the beta distribution). For $\epsilon =0.1$ the system is weakly coupled and displays fully developed turbulence (spatiotemporal chaos with high-dimensional attractor, i.e., the snapshot is weakly correlated). All three snapshots [Figs. 5–5] look very similar and, expectedly, they all display apparently similar degree distributions. (b) Here we consider 20 realizations of each of the three systems, and in each case compute the ${\chi }_2$ statistic (see the text) measuring the deviation of the empirical degree distribution ($k<44$) from the theory for random fields. As expected, the i.i.d. cases (random field and snapshot of the uncoupled logistic maps) are indistinguishable, but the weakly coupled system is clearly distinguished, finding stronger deviations from Eq. (3) than those found due to finite size effects. (c) Principal component analysis (PCA) of the set of degree distributions for the 60 realizations explored in (b). Each degree distribution $P\left(k\right)$ has been projected in a two-dimensional space spanned by the first two principal components (this subspace accounts for $60\%$ of the variability). One does not need to apply any clustering algorithm as the nonrandom matrices are very clearly clustered together and apart from the i.i.d. cases.

Figure 7

(a) Scalar parameter $D$ (see the text) as a function of the coupling constant $\epsilon$, computed from the degree distribution of ${\mathrm{IHVG}}_8$ associated to $100\times 100$ CMLs of fully chaotic logistic maps. $D$ captures the spatiotemporal phases: fully developed turbulence (FDT), periodic structure (PS), coherent structure (CS), and a mixed phase. Snapshots characteristic of these phases are depicted in Fig. 9 in an Appendix. (b) Principal component analysis (PCA) of the degree distributions of ${\mathrm{IHVG}}_8$ associated to the same data of (a). The plot is a projection into the first two principal components (accumulating over $90\%$ of the data variability). The different heuristic phases are highlighted.

Figure 8

(a)–(c) Gray scale atomic force microscopy images of normal (a), immortal (premalignant) (b), and cancer (malignant) (c) cervical epithelial cells (extracted from [33] after permission from Sokolov). (d) Semi-log plot of the degree distribution of ${\mathrm{IHVG}}_8$ associated to the three images: normal (red dots), immortal (black triangles), and cancerous (black hollow squares) cells [33]. Normal cells display a distribution closer to an uncorrelated random field [Eq. (3) for $n=8]$, and this preliminary evidence suggests that the transition normal $\to$ immortal $\to$ cancer is paralleled by a systematic deviation from the random field case for most of the degrees $k$ in $P\left(k\right)$. (e)–(g) Analogous plot for the degree distributions in the case of ${\mathrm{IVG}}_8$. The distributions now have a clear exponential tail, and we have used least squares to fit exponential functions $\sim exp(-\lambda k)$ to the tails of the distributions, i.e., in the range $k\ge 30$ (dispersion is Gaussian distributed, a requirement to use least-squares minimization). Fitting suggests ${\lambda }_{\text{normal}}<{\lambda }_{\text{immortal}}<{\lambda }_{\text{cancer}}$, something that should be carefully validated in a larger study.

Figure 9

Gray scale snapshot plots of $100\times 100$ CMLs [Eq. (5)] for different values of $\epsilon$. From top left to bottom right, respectively: $\epsilon =0.05$ [fully developed turbulence (a)], $\epsilon =0.15$ and 0.25 [periodic structure (b) and (c), respectively], $\epsilon =0.4$ and 0.8 [coherent structure (d) and (e), respectively], and $\epsilon =0.95$ [coexistence state with both coherent and periodic structures intertwined (f)].