=Paper= {{Paper |id=Vol-1987/paper22 |storemode=property |title=Exploring Complex Networks by Detecting Collective Dynamics of Kuramoto Oscillators |pdfUrl=https://ceur-ws.org/Vol-1987/paper22.pdf |volume=Vol-1987 |authors=Aladin Crnkić,Vladimir Jaćimović }} ==Exploring Complex Networks by Detecting Collective Dynamics of Kuramoto Oscillators== https://ceur-ws.org/Vol-1987/paper22.pdf

Exploring Complex Networks by Detecting Collective
Dynamics of Kuramoto Oscillators

Aladin Crnkić Vladimir Jaćimović
University of Bihać University of Montenegro
Ljubijankićeva bb., Cetinjski put bb.,
77000 Bihać, Bosnia and Herzegovina 81000 Podgorica, Montenegro
aladin.crnkic@hotmail.com vladimir@jacimovic.me

Abstract
Diﬀerent models and concepts from Statistical Mechanics are increas-
ingly exploited to study the structure and topology of complex net-
works. For instance, famous Kuramoto model of coupled oscillators
has been successfully applied to analyze complex networks. It has been
shown that the gradual process of synchronization reveals essential in-
formation about network topology. Here, we propose the method of
exploring complex networks by detecting the collective behavior of cer-
tain groups of oscillators. The information on collective behavior is
extracted from the statistics of Möbius transformations that govern os-
cillators dynamics on ﬁxed time intervals. Due to rich geometric and
algebraic structure of the group P SL(2; C) of Möbius transformations,
we can employ simple concepts from projective geometry (such as cross
ratio of four points on the unit circle S 1 ) in order to study collective
dynamics.

1 Introduction
In many cases large amount of empirical data can be represented by the complex network of items and interactions
between them. This requires eﬃcient algorithms for investigation of large networks. In study of large complex
networks there exist a class of algorithms that are based on concepts and objects from Statistical Mechanics.
For instance, a classical problem in Graph Theory is community detection. Community in the complex networks
is deﬁned in diﬀerent ways and the deﬁnitions used in various literature usually depends on the method of
investigation of the network (for detailed survey see [Fortunato, 2010]). In any case, by community one means
the group of the nodes that are densely interconnected, while their connections to the remaining nodes in the
network are relatively sparse.
For the problem of community detection several algorithms based on ideas of Statistical Mechanics have
been proposed in 2000’s. The ﬁrst method employs the model of coupled phase oscillators (Kuramoto os-
cillators, [Kuramoto, 1975]) and well-known phenomena of synchronization. Indeed, since XVI century and
famous Huyghens’ letters ([Huygens, 1665]), it is known that oscillators that are weakly coupled tend to syn-
chronize, this is an universal phenomena observed in many variations in nature and technology. Arenas et al.

Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of
the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org

146
([Arenas et al, 2006]) proposed the algorithm of community detection that relies on observation that the process
of gradual synchronization in the network of coupled oscillators unveils the network topology. Consequently,
one might expect that the oscillators belonging to the same community will synchronize their oscillations be-
fore the synchronization in the whole network takes place. This is the basic idea standing behind this method:
observation of the process of gradual synchronization makes it possible to distinguish densely interconnected
communities in the network. Notice, that this is only the rough idea, Arenas et al. introduced mathematical
instruments to study this process.
Another idea for the same problem relies on phenomena of ferromagnetism and collective spin dynamics. These
methods employ the Potts model ([Reichardt & Bornholdt, 2004, Reichardt & Bornholdt, 2006]) or Ising model
([Son et al., 2006]) of ferromagnetism for community detection. This method is based on the choice of suitable
Hamiltonian for the network. In this way, the problem of community detection is approached by minimization
of the Hamiltonian.
In the past decade various modiﬁcations and extensions of the above mentioned methods have been proposed.
Algorithms based on Statistical Mechanics have several advantages. For instance, they are typically well-suited
for the networks with various kinds of interactions (including weighted graphs, repulsive interactions, delayed or
noisy interactions, etc.). The second advantage is that they allow to detect fuzzy or overlapping communities.
This paper is intended to propose new method for investigation of complex networks, that can be based on the
models studied in [Arenas et al, 2006], as well as in [Reichardt & Bornholdt, 2004, Reichardt & Bornholdt, 2006].
The diﬀerence is that our method is based on detection of collective behavior of nodes in complex networks. This
approach is inspired by the result of [Marvel et al., 2009] for the globally coupled population of oscillators. This
result enables us to use classical concepts of Projective Geometry and Complex Analysis. In the next section
we brieﬂy explain the main result of [Marvel et al., 2009] and some extensions necessary to apply the whole
concept to the investigation of complex networks. In Section 3 we explain in detail the application to two typical
problems related to complex networks: community detection and identiﬁcation of inﬂuential nodes. In Section 4
we brieﬂy illustrate the method by depicting results for some random networks. Finally, the paper is concluded
by the short outlook for the future research and some applications.

2 Coupled Oscillators
In this paper we consider the model of phase oscillators that are coupled through the complex network of pairwise
interactions as a paradigm for collective behavior in large systems. This model is written as the following
dynamical system:
1 ∑
N
φ̇j = ω + Kij sin(φj − φi ), j = 1, . . . , N. (1)
N i=1

Here, φj (t) is the phase of the j-th oscillator and ω is the frequency common for all oscillators. The coupling
network is given by the matrix Kij . Total number of oscillators N is assumed to be suﬃciently large (say,
N ≥ 500).
It is known that if the network is connected (i.e. there exists the path in the network between two arbitrary
nodes i and j) and all interactions are attractive (i.e. Kij ≥ 0 for ∀i, j) then in certain moment synchronization
of all oscillators in the network will occur.
Underline that the model (1) diﬀers from the one that was considered in the seminal paper [Kuramoto, 1975]
of Kuramoto. In [Kuramoto, 1975], the global coupling is assumed, that is Kij ≡ K > 0 for ∀i, j. On the other
hand, intrinsic frequencies ωj are diﬀerent for diﬀerent oscillators.
Introduce the new variable zj (t) = eiφj (t) . Then we can study dynamics on the unit circle since zj (t) ∈ S 1 for
all t ≥ 0. We call the variable zj (t) the state of oscillator j at the moment t.
Further, recall that the set of all Möbius transformations in the complex plane form a group. We will work
with the subgroup consisting of all Möbius transformations that preserve the unit disc. The general Möbius
transformation that preserves the unit disc can be written in the following form:

eiψ z + α
M(z) = , (2)
1 + ᾱeiψ z

for some angle ψ ∈ [0, π] and α ∈ C, |α| < 1.
The main result of [Marvel et al., 2009] can be brieﬂy formulated as follows:

147
Proposition 1 The state of each oscillator evolves by the action of Möbius group. More precisely, the state
zj (t) at each moment t is given by a certain Möbius transformation Mjt of the initial state zj (0), that is zj (t) =
Mjt (zj (0)).

In addition, the evolution of parameters of the Möbius transformation acting on the oscillator j is given by
the following system of ODE’s for parameters of (2):
{
α̇j = i(fj (t, ·)αj2 + ωαj + f¯j (t, ·));
(3)
ψ̇j = (fj (t, ·)αj + 2ω + f¯j (t, ·)ᾱj ).

for some coupling function f (t, ·) that depends on time and states of all oscillators z1 , . . . , zN at each moment t.

Remark 1 Since the function f depends on large number of variables, it is virtually impossible to specify the
exact Möbius transformation Mjt acting on the oscillator j on time interval (0, t) apriori.

Remark 2 The geometric meaning of the variable αj is quite transparent: it turns out that αj (t) is the image
of the zero (center of the disc) under the action of corresponding Möbius transformation. This can be simply
written as:
αj (t) = Mjt (0).

Remark 3 Notice that in [Marvel et al., 2009] only the case of global coupling has been considered, i.e. Kij ≡ K
for ∀i, j. In this case the Möbius transformation acting on each oscillator is the same, i.e. the whole population
evolves by the action of the same Möbius transformation at the fixed time interval (0, t).

3 Algorithm
Consider the system (1). We know that zj (t) = Mjt (zj (0)), for some unknown disc-preserving Möbius transfor-
mation Mjt .
However, one can identify the exact Möbius transformation acting on the j-th oscillator using the classical
concept from Projective Geometry: cross ratio. For that, it is not enough to measure only the state of oscillator
j, but at least three more suitably chosen oscillators. This is based on the fact that Möbius transformation
preserves cross ratio of four points, see [Needham, 1999].

Definition 1 [Jaćimović & Crnkić, 2017]
1. We say that four oscillators i, j, k, l agree, if for all t ≥ 0 there exists Möbius transformation Mt such that
zi (t) = Mt (zi (0)), zj (t) = Mt (zj (0)), zk (t) = Mt (zk (0)), zl (t) = Mt (zl (0)).
2. Coherence of the network is the probability that four randomly chosen oscillators agree.

In other words, four oscillators agree if they evolve by the action of the same one-parametric family of Möbius
transformations. Our algorithm is based on the above deﬁnition. It can be roughly explained in the following
steps:

1. Assume that the network with N nodes (oscillators) is given. Pick randomly four oscillators i, j, k, l from
the population 1, dots, N .
2. Check if i, j, k, l (approximately) agree. If they do not agree, go to the step 1.
3. If i, j, k, l agree, ﬁnd the corresponding Möbius transformation, i.e. ﬁnd parameters ψ and α in (2).
4. Parameter α is represented by the point in the unit disc.
5. Repeat the steps 1-4 until M points in the unit disc is found.
6. Obtain the ”cloud” of points in the unit disc. Using some of existing algorithms divide this ”cloud” into
clusters.
7. Each point corresponds to quadruple of nodes (oscillators). Find which nodes appear dominantly in which
cluster. In whole, this yields clusterization of the network.

148
Figure 1: Random graph with two communities.

We also brieﬂy introduce one more concept characterizing the position of the single node in the network. Fix
the node i in the network and pick randomly 3 nodes j, k, l diﬀerent from i. Denote by r the coherence of the
network. Denote by pi the probability that four oscillators i, j, k, l (approximately) preserves cross ratio at time
interval (0, t).

Definition 2 [Jaćimović & Crnkić, 2017] Correspondence level of the node i in the network is pri .

Notice that the concept of correspondence level is statistical and can be approximately computed using Monte
Carlo method. From the above deﬁnition it is clear that the average correspondence level in the network equals
1.
In particular, the concept of correspondence level can be used to identify important (inﬂuential) nodes in the
network. Indeed, one might expect that inﬂuential nodes do not participate in collective behavior and therefore
have lower correspondence level then average in the network.

Proposition 2 In the typical network influential nodes have significantly lower correspondence level then average
in the network.

On the other hand, marginal nodes have the same property, which means that nodes with low correspondence
level are not necessarily inﬂuential ones, this requires additional veriﬁcation. This will be illustrated in the next
section.
complex plane
1.0

0.5
Im

0.0

-0.5

-1.0
-1.0 -0.5 0.0 0.5 1.0
Re

Figure 2: Points in the unit disc obtained by applying our algorithm to the random graph depicted in Fig. 1.
Each point corresponds to 4 nodes. Two clusters of points corresponding to two communities are clearly visible.

149
Figure 3: Random graph with three communities. The central community is smaller and mediates between the
remaining two.

4 Examples
For the sake of brevity in this section we only consider two illustrative examples of the random networks. These
examples are chosen in such way to demonstrate use of our method to two classical problems in study of complex
networks: community detection and identiﬁcation of inﬂuential (important, vital) nodes in the network.
As the ﬁrst example, consider the random network consisting of two communities: each community is Erdös-
Renyi graph where each pair of nodes is connected with the probability 0.9, while the nodes belonging to diﬀerent
communities are connected with the probability of only 0.1, see Figure 1.

Figure 4: Nodes in the network with three communities are represented by circles. The area of each circle is
inverse proportional to the correspondence level of the node. It is visible that nodes from the central community
have smaller correspondence levels.

In the Figure 2 we depict the points that correspond to Möbius transformations that are found using the steps
1-5 algorithm explained in the previous section. The presence of two communities is clearly visible. Notice that
each point corresponds to the quadruple of nodes. For the remaining steps 6 and 7 it suﬃces to use one of known
algorithms.
We also consider one more example to illustrate our method of identiﬁcation of inﬂuential nodes. Consider
the network consisting of three communities, see Figure 3. Inside each community nodes are densely connected
with the probability 0.9. However, nodes belonging to communities A and C are directly connected only with
the nodes from the middle community B with the probability 0.1. In addition, communities A and C contain
250 nodes each and are signiﬁcantly larger then B, which contains 50 nodes only. Clearly, one might say that
nodes belonging to community B are inﬂuential in the network as they are essentially small group of mediators
in the network.

Table 1: Correspondence levels of randomly chosen nodes in the network consisting of three communities. It is
clear that nodes belonging to central community (community B) have smaller correspondence levels.

1 2 3 4 5 6 7 8 9 10 Mean
A 1.4825 1.2707 0.9177 1.4119 1.1295 0.7765 1.1295 1.4119 1.3413 1.0589 1.193
B 1.5039 0.5013 0.2507 0.7519 0.2507 1.2533 1.0027 1.5039 0 0.7519 0.777
C 1.1295 1.0589 1.553 0.9883 1.0589 1.2001 1.3413 1.1295 1.2001 1.411 1.2071

150
In Table 1 we list correspondence levels of ten randomly chosen oscillators from each community. It is clear
that nodes from B have signiﬁcantly lower correspondence level. This is depicted in Figure 4, where the nodes
are represented by the circles. The area of the circles is inverse proportional to the correspondence levels of
corresponding nodes. In other words, nodes with lower correspondence level are represented by larger circles.

5 Outlook
We have presented the method of investigation of complex networks based on detecting collective dynamics. Our
exposition is based on paradigmatic model of coupled oscillators (Kuramoto oscillators), however it could be
reinterpreted in terms of magnetic ﬁelds and spin dynamics as well. In whole, our method relies on objects and
ideas of Statistical Mechanics, but the approach presented here diﬀers essentially from the previous ones (see
Introduction). The base for our method is the result of [Marvel et al., 2009] that explains dynamics of coupled
oscillators in algebraic and geometric terms.
Furthermore, our method is essentially statistical and works well for large networks, consisting at least of
several hundreds nodes. For the real-life data it can be used in combination with other methods.
One advantage of this method is that it is applicable to diﬀerent kinds of networks. For instance, one might
use it to study the network with noisy or delayed interactions.

References
[Arenas et al, 2006] Arenas, A., Diaz-Guilera, A., & Pérez-Vicente, C. J. (2006). Synchronization reveals topo-
logical scales in complex networks. Physical Review Letters, 96(11), 114102.
[Fortunato, 2010] Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3), 75-174.

[Huygens, 1665] Huygens, C. (1665). Letter to de Sluse. In Oeuveres Completes de Christian Huygens (letters;
no. 1333 of 24 February 1665, no. 1335 of 26 February 1665, no. 1345 of 6 March 1665). (Societe
Hollandaise Des Sciences, Martinus Nijhoﬀ, La Haye).

[Jaćimović & Crnkić, 2017] Jaćimović, V., & Crnkić, A. (2017). Characterizing complex networks through statis-
tics of Möbius transformations. Physica D: Nonlinear Phenomena, 345, 56–61.

[Kuramoto, 1975] Kuramoto, Y. (1975). Self-entrainment of a population of coupled nonlinear oscillators. In H.
Araki(Ed.). International symposium on mathematical problems in theoretical physics. (pp. 420-422).
Berlin: Springer.
[Marvel et al., 2009] Marvel, S. A., Mirollo, R. E., & Strogatz, S. H. (2009). Identical phase oscillators with global
sinusoidal coupling evolve by Möbius group action. Chaos: An Interdisciplinary Journal of Nonlinear
Science, 19(4), 043104.

[Needham, 1999] Needham, T. (1999). Visual Complex Analysis. Oxford: Oxford University Press.
[Pikovsky et al., 2001] Pikovsky, A., Rosenblum, M., & Kurths, J. (2001). Synchronization: a universal concept
in nonlinear sciences. Cambridge: Cambridge University Press.
[Reichardt & Bornholdt, 2004] Reichardt, J., & Bornholdt, S. (2004). Detecting fuzzy community structures in
complex networks with a Potts model. Physical Review Letters, 93(21), 218701.
[Reichardt & Bornholdt, 2006] Reichardt, J., & Bornholdt, S. (2006). When are networks truly modular? Phys-
ica D: Nonlinear Phenomena, 224(1), 20–26.
[Son et al., 2006] Son, S. W., Jeong, H., & Noh, J. D. (2006). Random ﬁeld Ising model and community structure
in complex networks. The European Physical Journal B, 50(3), 431437.

151