Different models and concepts from Statistical Mechanics are increasingly exploited to study the structure and topology of complex networks. 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 information about network topology. Here, we propose the method of exploring complex networks by detecting the collective behavior of certain groups of oscillators. The information on collective behavior is extracted from the statistics of M¨obius transformations that govern oscillators dynamics on fixed time intervals. Due to rich geometric and algebraic structure of the group P SL(2; C) of M¨obius transformations, we can employ simple concepts from projective geometry (such as cross ratio of four points on the unit circle S1) in order to study collective dynamics.
Another idea for the same problem relies on phenomena of ferromagnetism and collective spin dynamics. These
methods employ the Potts model
In the past decade various modifications 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 difference 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 briefly 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 identification of influential nodes. In Section 4 we briefly 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
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: φ˙ j = ω +
N i=1 1 ∑N Kij sin(φj φi), j = 1, . . . , N.
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 sufficiently 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 8i, j) then in certain moment synchronization of all oscillators in the network will occur.
Underline that the model (1) differs 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 8i, j. On the other hand, intrinsic frequencies ωj are different for different oscillators.
Introduce the new variable zj (t) = eiφj(t). Then we can study dynamics on the unit circle since zj (t) 2 S1 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 M¨obius transformations in the complex plane form a group. We will work with the subgroup consisting of all M¨obius transformations that preserve the unit disc. The general M¨obius transformation that preserves the unit disc can be written in the following form: for some angle ψ 2 [0, π] and α 2 C, jαj < 1.
The main result of [Marvel et al., 2009] can be briefly formulated as follows:
M(z) = 1 + α¯eiψz ,
eiψz + α Proposition 1 The state of each oscillator evolves by the action of Mobius group. More precisely, the state zj (t) at each moment t is given by a certain Mobius transformation Mtj of the initial state zj (0), that is zj (t) = Mtj (zj (0)).
In addition, the evolution of parameters of the M¨obius 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, )); ψ˙j = (fj (t, )αj + 2ω + f¯j (t, )α¯j ). (3) 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 Mobius transformation Mtj 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 Mobius transformation. This can be simply written as:
αj (t) = Mtj (0).
Remark 3 Notice that in [Marvel et al., 2009] only the case of global coupling has been considered, i.e. Kij K for 8i, j. In this case the Mobius transformation acting on each oscillator is the same, i.e. the whole population evolves by the action of the same Mobius transformation at the xed time interval (0, t). 3
Consider the system (1). We know that zj (t) = Mtj (zj (0)), for some unknown disc-preserving M¨obius transforj mation Mt .
However, one can identify the exact M¨obius 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 M¨obius transformation preserves cross ratio of four points, see [Needham, 1999].
De nition 1 [Jacimovic & Crnkic, 2017] 1. We say that four oscillators i, j, k, l agree, if for all t 0 there exists Mobius 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 M¨obius transformations. Our algorithm is based on the above definition. 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, find the corresponding M¨obius transformation, i.e. find 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.
We also briefly 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 different 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).
De nition 2 [Jacimovic & 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 definition 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 (influential) nodes in the network. Indeed, one might expect that influential nodes do not participate in collective behavior and therefore have lower correspondence level then average in the network.
Proposition 2 In the typical network in uential nodes have signi cantly 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 influential ones, this requires additional verification. This will be illustrated in the next section.
complex plane 1.0 0.5 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 identification of influential (important, vital) nodes in the network.
As the first example, consider the random network consisting of two communities: each community is Erd¨osRenyi graph where each pair of nodes is connected with the probability 0.9, while the nodes belonging to different communities are connected with the probability of only 0.1, see Figure 1.
In the Figure 2 we depict the points that correspond to M¨obius 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 suffices to use one of known algorithms.
We also consider one more example to illustrate our method of identification of influential 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 significantly larger then B, which contains 50 nodes only. Clearly, one might say that nodes belonging to community B are influential in the network as they are essentially small group of mediators in the network.
In Table 1 we list correspondence levels of ten randomly chosen oscillators from each community. It is clear that nodes from B have significantly 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
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 fields and spin dynamics as well. In whole, our method relies on objects and ideas of Statistical Mechanics, but the approach presented here differs 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 different kinds of networks. For instance, one might use it to study the network with noisy or delayed interactions.