Unveiling The Connectivity of Complex Networks Using Ordinal Transition Methods

Download as pdf or txt
Download as pdf or txt
You are on page 1of 9

Unveiling the connectivity of complex networks using ordinal transition

methods
Juan A. Almendral,1, 2, a) I. Leyva, and Irene Sendiña-Nadal
1)
Complex Systems Group & GISC, Universidad Rey Juan Carlos, 28933 Móstoles, Madrid,
Spain
2)
Center for Biomedical Technology, Universidad Politécnica de Madrid, 28223 Pozuelo de Alarcón, Madrid,
Spain
(Dated: 13 July 2023)
Ordinal measures provide a valuable collection of tools for analyzing correlated data series. However, using
these methods to understand the information interchange in networks of dynamical systems, and uncover the
interplay between dynamics and structure during the synchronization process, remains relatively unexplored.
arXiv:2307.05739v1 [physics.soc-ph] 11 Jul 2023

Here, we compare the ordinal permutation entropy, a standard complexity measure in the literature, and the
permutation entropy of the ordinal transition probability matrix that describes the transitions between the
ordinal patterns derived from a time series. We find that the permutation entropy based on the ordinal tran-
sition matrix outperforms the rest of the tested measures in discriminating the topological role of networked
chaotic Rössler systems. Since the method is based on permutation entropy measures, it can be applied
to arbitrary real-world time series exhibiting correlations originating from an existing underlying unknown
network structure. In particular, we show the effectiveness of our method using experimental datasets of
networks of nonlinear oscillators.

I. INTRODUCTION ordinal transition entropy has proven to be more robust


than standard permutation entropy when dealing with
Time series analysis has garnered significant research noisy signals10,11 . Furthermore, the statistics of self-
attention in recent decades. However, the exponential transitions within an OTN12,13 offers an effective means
growth in data generation from various social, techno- of characterizing diverse time series dynamics. Notably,
logical, and natural sources observed in the last years OTN complexity can accurately reproduce the results of
has posed a challenge for researchers seeking to extract Lyapunov exponents even for small embedding sizes14 .
valuable information from these datasets. Among the ar- The versatility of this method extends to various ap-
ray of new tools developed for this purpose, the ordinal plications, such as distinguishing between different con-
methods derived from the seminal work of Bandt and sciousness states15 , analyzing EEG data16 , investigating
Pompe1 have emerged as particularly intriguing. stock markets17,18 , and examining transportation data13 .
In this approach, the original data series undergoes a In combination with complex network techniques for non-
process of coarse-graining, wherein it is replaced by a re- linear time series analysis, such as visibility or recurrence
duced set of symbols representing the order permutations networks10,19–23 , this approach presents a valuable addi-
of consecutive data points. Statistical properties and cor- tion to the set of available tools.
relations of those ordinal permutation series effectively Ordinal methods offer good potential for various ap-
capture much of the dynamical information inherent to plications, particularly in finding correlations between
the original system. Moreover, its analysis is faster, com- time series. The multivariate extension of these meth-
putationally affordable and more robust to noise than ods enables the synthesis of information from multiple
raw data analysis. As a result, the applications of or- data sources, resulting in a unified set of symbols24–26 .
dinal methods continue to expand2 , encompassing di- This approach proves useful in detecting phase transi-
verse fields such as neuronal3 and brain dynamics4 , laser tions within the collective state of small groups of coupled
dynamics5 , and sports data analysis6 , among others. chaotic nodes. Furthermore, by incorporating delays into
Recently, the field of ordinal methods has advanced the analysis, multivariate ordinal methods can unveil the
to incorporate ”ordinal transition networks” (OTN). Ini- directionality of the coupling relationships27 .
tially proposed in Ref.7 , this concept introduces an addi- Recent developments have introduced the concept of
tional layer of temporal correlation to the analysis by ex- an ordinal network based on pattern co-occurrence be-
amining the statistics of ordinal patterns and their tran- tween time series28 . This approach facilitates the infer-
sitions. The time series is now represented as a network, ence of correlations between different time series. More-
where each ordinal pattern corresponds to a node, and over, the notion of ordinal synchronization29 demon-
the possible transitions among them are the links. strates the capability to detect phase and anti-phase syn-
This innovative tool has demonstrated its potential in chronization even in noisy real data.
detecting subtle dynamical changes8,9 , and its associated
These examples highlight the significant potential of
ordinal methods in studying dynamical ensembles and
networks. However, it is important to note that most of
a) Electronic mail: [email protected] these applications currently remain confined to proof-of-
2

concept studies involving small networks24,25 . In addi- In ordinal methods, how the raw data is projected into
tion, many of these approaches rely on multivariate pair- an ordinal series depends on the particularities of the
wise correlations to extract information4 . data, their sampling, or their continuous or discrete na-
Nevertheless, it is crucial to realize that each element ture, without affecting the rest of the procedure9 . In our
within a networked ensemble undergoes an information case, to extract information about the temporal organiza-
flux that alters its dynamics, effectively encoding valu- tion of each nodal dynamics xi (t), we first computed the
able information regarding its topological role and the two-dimensional Poincaré section P ≡ {[xi (tm ), zi (tm )] ∈
collective state. Ordinal methods serve as an ideal tool R2 | ẏi (tm ) = 0, ÿi (tm ) > 0}34 . This allows us to map the
for unveiling these dynamical changes, enabling the cre- whole attractor xi of node i into the one-dimensional
ation of centrality rankings for nodes without solely re- time series Si ≡ {yi (tm ), m = 1, . . . , M }, generated at
lying on pairwise correlations30,31 . the times tm the attractor crosses the section P. Then,
Building upon this premise, our work extends the ap- we construct the order relations of D successive data
plication of these methods to analyze the synchronization points in the sampled time series Si in the following man-
process in complex networks. Our findings demonstrate ner. Once the terms in the sequence Si are split into dis-
that ordinal transition methods outperform conventional joint blocks of size D, we create a symbolic sequence in
ordinal patterns’ statistics when it comes to detecting which each element is replaced by a number in [1, . . . , D],
subtle dynamical changes and discriminating nodes based corresponding to its relative ranking respect to its D − 1
on their topological roles. These initial results, using syn- neighbours in the block. Therefore, each block is mapped
thetic networks of chaotic Rössler systems and data from into one of the D! possible permutations in which D
experiments with nonlinear electronic circuits, illuminate different elements can be arranged. We refer to these
new possibilities for using ordinal methods in various permutations as ordinal patterns, using the notation πℓ
applications, including functional brain data analysis4 , with ℓ = 1, . . . , D!. As an example, let us consider the
power grids, mobility networks, or any other domains in- series {2.3, 3.4, −2.7, 0.4, 1.6, 2.9, −2.8, −0.5, 3.1, 2.4, . . .}.
volving the close interplay between structural and func- We first split the series into disjoint blocks of size D = 3:
tional relationships within large-scale dynamical ensem- {2.3, 3.4, −2.7}, {0.4, 1.6, 2.9}, {3.1, −0.5, 3.8}, {2.4, . . .}.
bles. Then, we derive the ordinal pattern for each block. It
can be done from maximum to minimum or the other
way around. In the first case, the ordinal patterns would
II. MODEL AND METHODS be {2, 1, 3}, {3, 2, 1}, {2, 3, 1}, . . ., which are arbitrarily
denoted as π5 , π1 , π2 , . . . (see Fig. 2 for our notation of
A. Model the six possible permutations).
Finally, we define the probability of occurrence of a
We consider a network of N identical Rössler dynam- given pattern πℓ as pℓ = #(πℓ )/L, being #(πℓ ) the num-
ical systems32 whose dynamics are governed by the fol- ber of times the ordinal pattern πℓ appears in the se-
lowing equations: quence Si and L = ⌊M/D⌋ the total number of blocks of
size D in which we divide the series Si (⌊ ⌋ is the floor
ẋi = f (xi ) − σ̃
X
Lij h(xj ), (1) function). Note that this procedure is only meaningful if
M ≫ D!.
with i = 1, . . . , N ; xi = (xi , yi , zi ) the vector state of
the node i; f (x) and h (x) : R3 → R3 , being f (x) =
[−y − z, x + ay, b + z(x − c)] the vector flow of the Rössler B. Methods
system, and h(x) = [0, y, 0]T the coupling function. We
set a = b = 0.2 and c = 9.0 to get a phase-coherent In this Section, we present the methods employed to
chaotic attractor. The coefficients Lij = ki δij − aij are characterize the statistical complexity of a nodal dynam-
the elements of the Laplacian matrix whose adjacency ics. Our ultimate objective is to establish a relationship
matrix A := (aij ) encodes the connectivity among the between the dynamical behaviour of each node and its
nodes of the network: aij = 1, if i and j are connected, structural connectivity within the network. To achieve
and aijP = 0 otherwise. Thus the degree of node i is this, we compare the ordinal permutation entropy based
σ on the probability distribution of ordinal patterns and
ki = j aij . The constant σ̃ = kmax is the coupling
strength normalized by the maximum degree present in the ordinal transition entropy based on the transition
the network, that is, kmax = max(ki ). This normaliza- probabilities between consecutive non-overlapping ordi-
tion is introduced to properly compare observables be- nal patterns.
tween different network realizations33 . The system of Permutation entropy has previously been identified as
N equations described by (1) has been numerically inte- a reliable indicator of the topological role of a node within
grated using a Runge-Kutta method of 4th order with a a dynamical network30,31 . However, our study reveals
time discretization of 0.005. In all simulations, the time that analysing the transition probabilities between ordi-
evolution is extended up to 12, 000 time units, discarding nal patterns offers a more effective and informative mea-
the first half, which is considered a transient. sure for assessing a node’s degree centrality.
3

1. Ordinal permutation entropy ment of the distribution of the Hπℓ values as in36
D!
Given the probability distribution of the ordinal pat- 1 X
HT = Hπℓ (5)
terns πℓ of size D, with ℓ = 1, . . . , D!, we define the D!
ℓ=1
normalized permutation entropy as the Shannon entropy
evaluated on the ordinal pattern probability distribution: or, alternatively, as defined in38 :
1 X D!
H0 = − pℓ ln pℓ , (2) X
ln D! ĤT = pℓ Hπl (6)

ℓ=1

with the criterion 00 = 1 to deal the case pℓ = 0. Ac- which characterizes the weighted average (over the sta-
cording to Bandt and Pompe1 , 3 ≤ D ≤ 7 values provide tionary probabilities pℓ of each pattern πℓ ) of the diver-
reliable information on the natural complexity of time sity of consecutive ordinal patterns. Other measures to
series coming from chaotic dynamical systems as long as characterize ordinal transition networks can be found in
M ≫ D!. However, unobserved ordinal patterns have Refs.22,39 .
been reported in chaotic dynamical systems, no matter
how large the time series is, due to the underlying tem-
poral correlations35 . 3. Synchronization measures

In addition to characterizing the nodal dynamics by


2. Ordinal transition entropy the randomness of the ordinal patterns and their tran-
sitions, we evaluate the dynamical network’s collective
In addition to the probability pℓ of each ordinal pat- state for increasing coupling values since the chosen net-
tern πℓ , the transition probability pℓm , from the ordi- worked system (1) is known to evolve from a totally in-
nal pattern πℓ to πm , may reveal information into the coherent state when σ = 0 to a regime where the phases
finer temporal organization of a dynamical system7 . We are locked while the amplitudes vary chaotically and un-
define the ordinal transition probability (OTP) matrix correlated, up to a regime of complete synchronization
T := (pℓm ) as for very large σ. We compute the time-averaged phase
order parameter
#(πℓ , πm )
pℓm = (3) N
#(πℓ ) 1 X iθj
R= ⟨| e |⟩t (7)
N j=1
being #(πℓ , πm ) the number of times the pair πℓ − πm
consecutively occurs in the time series. Note that, in case with the phase θj of the j-oscillator defined as θj =
#(πℓ ) = 0 for some pattern πℓ , we can define pℓm = 0. arctan(yj /xj )40 , and synchronization error
The total number of blocks L of size D must now be L ≫
D!2 so that the OTP matrix T is statistically significant. 2 X
Equation (3) is a proper stochastic matrix whose E= ⟨ ∥xi − xj ∥⟩t , (8)
N (N − 1)
i̸=j
weights encode an OTN among ordinal patterns, includ-
ing self-transitions, into which the time series of each which account for the level of phase (0 ≤ R ≤ 1) and
nodal dynamics can be mapped. Hence, the complexity total synchronization (E ≥ 0) respectively. When the
of this OTN will depend on the diversity of both ordinal network is in complete synchrony, R = 1 and E = 0.
patterns Pand transitions occurring among them. Here, ⟨⟩t stands for the time average along a sufficiently
Since m pℓm = 1, we can define the node permuta- large time series.
tion entropy Hπℓ associated with the ordinal pattern πℓ ,
a node of the OTN, which quantifies the randomness of
the local transitions from the ordinal pattern πℓ to any III. RESULTS
other pattern36,37 , as
D! A. Star network
1 X
Hπℓ =− pℓm ln pℓm . (4)
lnD! m 1 Let us start with a star configuration of N coupled
=
Rössler systems. This network topology has N − 1 nodes
We characterize the transitional complexity of the of degree kleaf = 1 connected to a central one, the hub,
OTN at the global level with a network permutation en- with khub = N − 1, thus, offering two types of nodal dy-
tropy obtained as the average of the node permutation namics with the maximum topological distance possible.
entropies given by Eq. (4). Depending on how the aver- Figure 1 illustrates the transition to synchronization
age is performed, we consider using either the first mo- of a N = 9 star as the coupling strength σ increases.
4

(a)
1

Phase order, R

Sync error, E
R 10
0.8 E
0.6
5
0.4
0.2 0
0 1 2 3
Coupling strength, <
<=0.00 <=0.40 <=1.20 <=3.00
(b) (c) (d) (e)
:1 0.8
:2
0.6
:3

Thub
:4 0.4

:5 0.2
:6
0
(f) (g) (h) (i)
:1 0.8
:2
0.6
:3

Tleaf
:4 0.4
:5 0.2
:6
0
:1 :2 :3 :4 :5 :6 :1 :2 :3 :4 :5 :6 :1 :2 :3 :4 :5 :6 :1 :2 :3 :4 :5 :6

FIG. 1. OTP matrices for a star graph of N = 16 identical Rössler systems along the route to synchronization. (Top panel)
Phase order R (left axis) and synchronization error E (right axis) as a function of the coupling strength σ. (Color panels)
OTP matrices T , with ordinal patterns πℓ (ℓ = 1, . . . , 6 since D = 3), of the hub (top row) and one of the leaves (bottom
row), for the coupling values marked with dotted lines in the top panel along the synchronization process. Ordinal transitions
with zero probability are marked with dots: in white, those caused for π1 being a forbidden ordinal pattern, and in red, the
transitions that, despite being between existing ordinal patterns, they actually do not occur. Time series length M = 1000.
Rössler parameters: a = b = 0.2 and c = 9.0.

Along this route, the initially identical dynamics exhib- initial states, red dots (for instance, a π3 pattern cannot
ited by the hub and the leaves start to differentiate due follow a π5 pattern).
to the coupling interaction. This differentiation becomes As soon as the hub and the leaf interact (panels c, g
evident when examining the OTP matrix T for D = 3, and d, h), the colormap changes differently for each of
which has six ordinal patterns (corresponding to the fol- them. New transitions appear while others disappear.
lowing permutations: π1 ≡ 321, π2 ≡ 312, π3 ≡ 231, Notably, all ordinal transitions become nearly equiprob-
π4 ≡ 132, π5 ≡ 213, π6 ≡ 123). able for the hub, which is indicative of noisy dynamics—a
The colormap panels depict the OTP matrices T of the characteristic feature.
hub (b-e) and one of the leaves (f-i), representing four To closely inspect how those transitions between ordi-
different values of σ corresponding to various synchro- nal patterns evolve along the synchronization process for
nization stages. When σ = 0 (panels b, f) and σ = 0.2 each type of node in a star graph, we plot in each panel of
(panels e, i), the hub and the leaves’ OTP matrices ex- the top row of Fig. 2 the node permutation entropy Hπℓ of
hibit the same color coding. This similarity arises be- each ordinal pattern πℓ for the hub and one of the leaves
cause they describe the transition probabilities between and the corresponding ordinal pattern frequencies pπℓ at
ordinal patterns of the same intrinsic dynamics, given by the bottom row as a function of the coupling strength σ.
the flow f in Eq. (1) when the systems are uncoupled or The most remarkable differences between hub and leaf
coupled but synchronized. In these panels, white and red come from those transitions starting at patterns π1 , π4 ,
dots indicate unobserved ordinal transitions (pℓm = 0). and π5 , since the gap between the node permutation en-
These transitions may be absent either because the cho- tropies Hπ between hub and leaf is the largest, while for
sen chaotic dynamics include one forbidden ordinal pat- the rest of patterns is less pronounced. In particular, the
tern, white dots (caused by the forbidden pattern π1 ), or pattern π1 , which is forbidden in the isolated dynamics,
because unreachable ordinal patterns exist from certain not only emerges due to the interaction but also becomes
5

H:
1 :1 1 :2 1 :3 1 :4 1 :5 1 :6

0.5 0.5 0.5 0.5 0.5 0.5


H:hub
H:leaf
0 0 0 0 0 0

p:hub 0.5
0.2 p:leaf 0.2 0.2
0.2 0.1
p:

0.1 0.1

0 0 0 0 0 0
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
< < < < < <

FIG. 2. Evolution of the node permutation entropies Hπℓ (top row) and the corresponding probabilities pπℓ (bottom row) of
each ordinal pattern πℓ , for D = 3, as a function of the coupling σ (crosses for the hub and dots for one of the leaves). Notice
that the scale is not the same for all the panels at the bottom row. In the upper right corner of the panels in the top row, it
is shown schematically with three black dots the permutation of the corresponding ordinal pattern (for instance, π2 is 312 and
π3 is 231). Data is for the same N = 16 star of Rössler systems and parameters as in Fig. 1.

much more entropic in the hub’s dynamics than in the as they have the same degree, kleaf = 1. This finding
leaves. In addition, note the differences in the probability implies that the network permutation entropy HT has
frequency pπ of each pattern that will have an effect on the potential for effectively discerning topological roles
the network permutation entropy of the OTN as defined within more complex ensembles, as we will explore in the
in Eq. (6). next Section.
The primary objective of this work is to evaluate
whether an entropic measure based on the information
encoded in the OTN can outperform the predictive power B. Scale-free network
of the entropic quantifiers based on just the probability
distribution of the ordinal patterns. To examine this, Once we have evidence that the network permutation
we compare in Fig. 3 how the ordinal permutation en- entropy HT can uncover the information stored in the
tropy H0 [Eq. (2)] and the network permutation entropies OTN and discriminate the different roles that nodes have
HT [Eq. (5)] and ĤT [Eq. (6)] differentiate between the in star networks, we move forward to test this measure
hub and leaf dynamics for two star networks of N =9 in the more challenging task of analyzing the synchro-
and N =31 nodes. The network permutation entropy nisation process of a scale-free network. Precisely, we
HT (panel (b)) effectively separates the hub and leaf dy- consider the network dynamics of N = 300 nodes, as de-
namics right from the onset of phase synchronization, scribed by Eq. (1), whose connectivity follows a scale-free
and maintains this distinction over a broader range of degree distribution41 .
coupling strengths compared to the two other entropies. Given a coupling value σ, for each node i we compute
(i)
This is linked to the results shown in Fig. 2, in which the corresponding ordinal permutation entropy H0 and
those patterns with the greatest differences between hub (i)
the network permutation entropy HT . Since we expect
and leaf node permutation entropies (π1 , π4 and π5 ) are that the nodes with the same degree k will have the same
those for which the probabilities of occurrence are smaller dynamical role within the network, we define a k-class
than for the rest (π2 , π3 , and π6 ). Note that the scale average for the network permutation entropies as30 :
is not the same for all the panels. Consequently, the
weighted version of the network permutation entropy, 1 X (i)
⟨HT ⟩k = HT , (9)
ĤT , is biased by the most frequent patterns π2 , π3 , and Nk
{i|ki =k}
π6 which are the ones with the most similar hub and
leaf node permutation entropies and there, less sensitive where Nk is the number of nodes with degree k and ⟨⟩k
to distinguish between the nodes’ different roles in the is just to denote how the measure has been obtained as
collective dynamics. an ensemble average of the given measure at the node
Furthermore, a noteworthy observation is that the dif- level restricted to nodes with the same connectivity k.
ferentiation in the HT of the hub is more pronounced, Similarly, we define a k-class average for the ordinal per-
and occurs at a lower coupling strength, in the case of mutation entropies of those nodes with the same degree:
the larger star with N = 31, compared to the smaller ⟨H0 ⟩k .
one with N = 9. On the other hand, the values for the The results are presented in Fig.4, which compares
leaf nodes in both stars are similar, which is expected ⟨H0 ⟩k (a,c) and ⟨HT ⟩k (b,d). It is clear that the net-
6

1 (a) 1 (b) 1 (c)


0.8 0.8 0.8

0.6 0.6 0.6

^T

HT
H0

H
0.4 0.5 N=31,hub 0.4 0.5 0.4 0.5

^Tj

j"HT j
j"H0 j

j"H
N=9,hub
N=31,leaf
0.2 0 N=9,leaf
0.2 0 0.2 0
0.01 0.1 0.01 0.1 0.01 0.1
</N-1 </N-1 </N-1
0 0 0
0 0.05 0.1 0.15 0 0.05 0.1 0.15 0 0.05 0.1 0.15
< < <
Coupling strength, N !1 Coupling strength, N !1 Coupling strength, N !1

FIG. 3. Comparison between (a) the ordinal permutation entropy H0 , and (b) the weighted ĤT and (c) unweighted HT network
permutation entropies along the route to synchronization, for the hub (blue crosses) and one of the leaves (red dots), of a star
graph of size N = 9 (dotted curves) and N = 31 (solid curves). Insets show, in a log-linear scale, the absolute difference
between the entropies of hub and leaf (∆H0 = H0hub − H0leaf , and the same for ∆ĤT and ∆HT ).

work permutation entropy surpasses the ordinal permu- N = 28 electronic circuits coupled in 20 different network
tation entropy in its ability to sort nodes according to configurations and monitored along their synchronization
their degree. Upon increasing the normalized coupling process for 100 coupling levels, ranging from disconnec-
strength σ/kmax , both entropies exhibit a distinct sepa- tion (isolated nodes) to values producing a network state
ration based on node degrees. However, the differences of complete synchrony. Please refer to the reference44 for
between k-classes are more pronounced in the case of a full description of the experiments.
⟨HT ⟩k . Therefore, these experimental datasets provide the
It is worth noting that, for weak values of the cou- ideal testbed for our inference method and to predict the
pling network, hubs exhibit higher entropy values, simi- circuits connectivity by means of the network permuta-
lar to the behavior of the central node of a star network. tion entropy of each timeseries’ circuit. In order to do so,
However, as the synchronization progresses further, the we choose a weak coupling condition (level 9 over 100)
ranking of the degree classes reverses. This change in be- and, for only one of the network configurations [the one
haviour throughout the synchronization process reflects that is used as a ground truth reference, plotted in Fig.
an interesting fact: in weakly coupled networks, highly 5 (a)], we calculate the average k-class network permu-
connected nodes perceive the information from the net- tation entropy ⟨HT ⟩k .
work as a source of noise, thereby increasing their entropy The output of this calibration procedure is a function
above that of the low-connected nodes. However, beyond that maps the node degree classes of the network used as
this point, the highly connected nodes take the lead in a ground truth and the corresponding assigned network
driving the transition to coherence, while the other nodes permutation entropies. One possible way is to produce
remain unsynchronized42,43 , resulting, as a consequence, a piecewise function ka (HT ) such that the sequence of
in an exchange of entropy trends. intervals are defined by interpolating the entropies mea-
sured in the experiment used as calibration for the de-
The results shown in Figs. 4(b,d) shed light on under-
grees k and k + 1, that is, TH (k) = [⟨HT ⟩k+1 − ⟨HT ⟩k ]/2
standing this entropy-based centrality ranking. We plot
for k = 1, . . . , kmax − 1. Now, for each node i in any
the ordinal permutation entropy (b) and the network per-
network different from the one used as a reference, we
mutation entropy (d) as a function of k for various cou-
blindly assign a degree ka as a function of their dynam-
pling values. The entropies of the degree classes demon-
ics using the following map:
strate a quasi-linear relationship with k, displaying a pos- 
itive slope for weak coupling (solid lines) and a negative 1 if HTi
< TH (1)
slope for coupling strengths close to the system’s synchro- i i
ka = k if TH (k) < HT < TH (k + 1); k = 2, . . . , kmax − 1
nization (dashed lines). Therefore, network permutation  i
kmax if HT > TH (kmax − 1)
entropy measures stand out as a superior choice. Con- (10)
sequently, a centrality ranking can be established solely Since the real degree kri of the node i is available in the
based on this entropy without prior knowledge of the un- dataset, we can compare the predicted value kai with the
derlying structure or costly pairwise computations of the real one. In Fig. 5(b), we plot the assigned degree versus
observed time series. the real one averaged for all the nodes in the 19 networks.
To assess the method’s validity in a more realistic envi- Notice that these networks are very small and relatively
ronment with available ground truth structural informa- sparse, with a maximum degree kmax = 7 and, there-
tion, we analysed the experimental datasets of networks fore, the degree sequence spans a much narrower interval
of nonlinear electronic circuits provided by Ref.44 . These than in the SF networks used in the simulations shown
datasets comprise the time series of the output voltage of in Fig. 4. Remarkably, even in this degree-constrained
7

E k=3 k=20

hH0 ik
R k=5 k=30
0.5 k=2 k=10 <=0 <=0.01
<=0.005 <=0.15
<=0.007 <=0.17
(a) (b)
0
1
hHT ik

0.5

(c) (d)
0
0 0.05 0.1 0.15 0.2 5 10 15 20 25 30
<
Coupling strength kmax Node degree k

FIG. 4. Comparison between the k-class ordinal permutation entropy ⟨H0 ⟩k (a,c) and the k-class network permutation entropy
⟨HT ⟩k (b,d) for heterogeneous scale-free networks of N = 300 nodes and mean degree 4: (a,b) as a function of the normalized
σ
coupling strength kmax , for several values of degree k class; (c,d) as a function of k, for several values of σ. In panel (d),
solid lines refer to weak coupling values while dashed ones refer to couplings favoring a state close to synchronization. The
synchronization error E (rescaled for clarity) and the Kuramoto parameter R have been added in panel (a) as a reference. Each
curve is the result of averaging over 50 network instances. Shaded bands indicate the confidence interval around the mean
value computed as three times the standard error of the mean.

scenario and despite the noise inherent to an experimen- IV. CONCLUSIONS


tal environment, we obtain that for the 91% of the nodes
|kri − kai | ≤ 1, constituting a very high confidence level. Ordinal measures provide a valuable collection of tools
for analyzing correlated data series. However, the use
of these methods to understand information interchange
in coupled networks and the interaction between dynam-
ics and structure during the synchronization process re-
7
(a)
mains relatively unexplored. In this study, using net-
(b)
works of coupled Rössler systems in chaotic regime, we
Average asigned degree ka

6
assessed the performance of the standard ordinal permu-
5 tation entropy H0 compared to the network permutation
entropy HT , which captures information about transi-
4
tions between ordinal patterns, and applied the proposed
3
methodology to infer the connectivity of experimental
datasets of networks of nonlinear circuits.
2 Whereas there exist other measures, such as statisti-
cal permutation complexity30 and ordinal structurality31 ,
1
1 2 3 4 5 6 7 which have demonstrated their usefulness as proxies for
Real degree kr degree distributions, our findings highlight the ordinal
transition entropy as a more effective method for distin-
FIG. 5. Inference of the nodes’ degree of networks of elec- guishing topological roles, and producing more satisfac-
tronic circuits based on the k-class network permutation en- tory outcomes, particularly for lower embedding dimen-
tropy ⟨HT ⟩k of the timeseries reported in Ref.44 . (a) Struc-
sions.
ture connectivity of the electronic circuit network used as a
ground truth. (b) Average assigned degree ka versus the real Many methods focused on the structure-function re-
degree kr obtained when using a single network as a training lationship are primarily intended to infer the detailed
reference. connectivity network, down to the level of the individual
links, from time series. However, in many cases, knowl-
edge of centrality roles alone is sufficient for designing
successful interventions in the dynamics. Therefore, we
8

anticipate that our results, which do not rely on pairwise 17 X. Wang, X. Han, Z. Chen, Q. Bi, S. Guan, and Y. Zou, “Multi-
correlations between timeseries, will be of particular in- scale transition network approaches for nonlinear time series
terest in the context of functional networks and other analysis,” Chaos, Solitons and Fractals 159, 112026 (2022).
18 K. Peng and P. Shang, “Characterizing ordinal network of time
scenarios in which the underlying structural information series based on complexity-entropy curve,” Pattern Recognition
is inaccessible. 124, 108464 (2022).
19 G. Nicolis, A. G. Cantú, and C. Nicolis, “Dynamical aspects of

interaction networks,” International Journal of Bifurcation and


Chaos 15, 3467–3480 (2005).
ACKNOWLEDGMENTS 20 J. Zhang and M. Small, “Complex network from pseudoperiodic

time series: Topology versus dynamics,” Phys. Rev. Lett. 96,


238701 (2006).
This research was supported by the Spanish Minis- 21 L. Lacasa, B. Luque, F. Ballesteros, J. Luque, and J. C. Nuño,
terio de Ciencia e Innovación under Project PID2020- “From time series to complex networks: The visibility graph,”
113737GB-I00. Proceedings of the National Academy of Sciences 105, 4972–4975
(2008).
22 Y. Zou, R. V. Donner, N. Marwan, J. F. Donges, and J. Kurths,
1 C. Bandt and B. Pompe, “Permutation entropy: A natural com-
“Complex network approaches to nonlinear time series analysis,”
plexity measure for time series,” Phys. Rev. Lett. 88, 174102
Physics Reports 787, 1–97 (2019).
(2002). 23 V. F. Silva, M. E. Silva, P. Ribeiro, and F. Silva, “Time series
2 I. Leyva, J. H. Martı́nez, C. Masoller, O. A. Rosso, and M. Zanin,
analysis via network science: Concepts and algorithms,” WIREs
“20 years of ordinal patterns: Perspectives and challenges,” Eu-
Data Mining and Knowledge Discovery 11, e1404 (2021).
rophysics Letters 138, 31001 (2022). 24 J. Zhang, J. Zhou, M. Tang, H. Guo, M. Small, and Y. Zou,
3 A. Tlaie, L. Ballesteros-Esteban, I. Leyva, and I. Sendiña-Nadal,
“Constructing ordinal partition transition networks from multi-
“Statistical complexity and connectivity relationship in cultured
variate time series,” Scientific Reports 7 (2017), 10.1038/s41598-
neural networks,” Chaos, Solitons & Fractals 119, 284–290
017-08245-x.
(2019). 25 Z. Shahriari and M. Small, “Permutation Entropy of State Tran-
4 K. Lehnertz, “Ordinal methods for a characterization of evolving
sition Networks to Detect Synchronization,” International Jour-
functional brain networks,” (2023).
5 J. Tiana-Alsina, C. Quintero-Quiroz, and C. Masoller, “Compar- nal of Bifurcation and Chaos 30, 2050154 (2020).
26 N. P. Subramaniyam, R. V. Donner, D. Caron, G. Panuccio, and
ing the dynamics of periodically forced lasers and neurons,” New
J. Hyttinen, “Causal coupling inference from multivariate time
Journal of Physics 21, 103039 (2019).
6 J. M. Buldú, M.-Á. Gómez, J. L. Herrera-Diestra, and J. H.
series based on ordinal partition transition networks,” Nonlinear
Dynamics 105, 555–578 (2021).
Martı́nez, “Nonlinear dynamics and networks in sports,” Chaos 27 Y. Ruan, R. V. Donner, S. Guan, and Y. Zou, “Ordinal parti-
Solitons Fractals 142, 110518 (2021). tion transition network based complexity measures for inferring
7 M. Small, “Complex networks from time series: Capturing dy-
coupling direction and delay from time series,” Chaos 29, 043111
namics,” Proceedings - IEEE International Symposium on Cir- (2019).
cuits and Systems , 2509–2512 (2013). 28 H. Ren, Q. Yuan, S. Semba, T. Weng, C. Gu, and H. Yang, “Pat-
8 X. Sun, M. Small, Y. Zhao, and X. Xue, “Characterizing system
tern interdependent network of cross-correlation in multivariate
dynamics with a weighted and directed network constructed from time series,” Physics Letters, Section A: General, Atomic and
time series data,” Chaos 24, 24402 (2014). Solid State Physics 384, 126781 (2020).
9 M. McCullough, M. Small, T. Stemler, H. Ho, C. Iu, and H. H. C.
29 I. Echegoyen, V. Vera-Ávila, R. Sevilla-Escoboza, J. H. Martı́nez,
Iu, “Time lagged ordinal partition networks for capturing dynam-
and J. M. Buldú, “Ordinal synchronization: Using ordinal pat-
ics of continuous dynamical systems,” Chaos 25, 53101 (2015),
terns to capture interdependencies between time series,” Chaos,
1501.06656.
10 A. A. Pessa and H. V. Ribeiro, “Characterizing stochastic time Solitons and Fractals 119, 8–18 (2019).
30 A. Tlaie, I. Leyva, R. Sevilla-Escoboza, V. P. Vera-Avila, and
series with ordinal networks,” Physical Review E 100, 42304
I. Sendiña Nadal, “Dynamical complexity as a proxy for the net-
(2019).
11 F. Olivares, M. Zanin, L. Zunino, and D. G. Pérez, “Contrast- work degree distribution,” Phys. Rev. E 99, 012310 (2019).
31 C. Letellier, I. Leyva, and I. Sendiña Nadal, “Dynamical com-
ing chaotic with stochastic dynamics via ordinal transition net-
plexity measure to distinguish organized from disorganized dy-
works,” Chaos 30, 063101 (2020).
12 J. B. Borges, H. S. Ramos, R. A. Mini, O. A. Rosso, A. C. namics,” Phys. Rev. E 101, 022204 (2020).
32 O. E. Rössler, “An equation for continuous chaos,” Physics Let-
Frery, and A. A. Loureiro, “Learning and distinguishing time
ters A 57, 397–398 (1976).
series dynamics via ordinal patterns transition graphs,” Applied 33 J. Gómez-Gardeñes, Y. Moreno, and A. Arenas, “Synchronizabil-
Mathematics and Computation 362, 124554 (2019).
13 I. Cardoso-Pereira, J. B. Borges, P. H. Barros, A. F. Loureiro, ity determined by coupling strengths and topology on complex
networks,” Phys. Rev. E 75, 066106 (2007).
O. A. Rosso, and H. S. Ramos, “Leveraging the self-transition 34 Z. Shahriari, S. D. Algar, D. M. Walker, and M. Small, “Ordinal
probability of ordinal patterns transition network for transporta-
poincaré sections: Reconstructing the first return map from an
tion mode identification based on GPS data,” Nonlinear Dynam-
ordinal segmentation of time series,” Chaos: An Interdisciplinary
ics 107, 889–908 (2022).
14 M. Huang, Z. Sun, R. V. Donner, J. Zhang, S. Guan, and Y. Zou, Journal of Nonlinear Science 33 (2023), 10.1063/5.0141438.
35 J. M. Amigó, S. Zambrano, and M. A. F. Sanjuán, “True and
“Characterizing dynamical transitions by statistical complexity
false forbidden patterns in deterministic and random dynamics,”
measures based on ordinal pattern transition networks,” Chaos
Europhysics Letters 79, 50001 (2007).
31, 33127 (2021). 36 C. Masoller, Y. Hong, S. Ayad, F. Gustave, S. Barland, A. J.
15 T. F. Varley, V. Denny, O. Sporns, and A. Patania, “Topological
Pons, S. Gómez, and A. Arenas, “Quantifying sudden changes
analysis of differential effects of ketamine and propofol anaesthe-
in dynamical systems using symbolic networks,” New Journal of
sia on brain dynamics,” Royal Society Open Science 8 (2021),
Physics 17, 023068 (2015).
10.1098/rsos.201971. 37 M. McCullough, M. Small, H. H. C. Iu, and T. Stemler, “Mul-
16 C. W. Kulp, J. M. Chobot, H. R. Freitas, and G. D. Sprechini,
tiscale ordinal network analysis of human cardiac dynamics,”
“Using ordinal partition transition networks to analyze ECG
Philosophical Transactions of the Royal Society A: Mathemat-
data,” Chaos 26 (2016), 10.1063/1.4959537.
9

ical, Physical and Engineering Sciences 375, 20160292 (2017). 42 C. Zhou and J. Kurths, “Hierarchical synchronization in
38 A. M. Unakafov and K. Keller, “Conditional entropy of ordinal complex networks with heterogeneous degrees,” Chaos: An
patterns,” Physica D: Nonlinear Phenomena 269, 94–102 (2014). Interdisciplinary Journal of Nonlinear Science 16 (2006),
39 M. Zanin and F. Olivares, “Ordinal patterns-based methodolo- 10.1063/1.2150381, 015104.
gies for distinguishing chaos from noise in discrete time series,” 43 T. Pereira, “Hub synchronization in scale-free networks,” Phys.

Communications Physics 4, 190 (2021). Rev. E 82, 036201 (2010).


40 S. Boccaletti, J. Kurths, G. Osipov, D. Valladares, and C. Zhou, 44 V. Vera-Ávila, R. Sevilla-Escoboza, A. Lozano-Sánchez,
“The synchronization of chaotic systems,” Physics Reports 366, R. Rivera-Durón, and J. M. Buldú, “Experimental datasets of
1–101 (2002). networks of nonlinear oscillators: Structure and dynamics during
41 A.-L. Barabási and R. Albert, “Emergence of scaling in random
the path to synchronization,” Data in Brief 28, 105012 (2020).
networks,” Science 286, 509–512 (1999).

You might also like