Synchronization reveals topological scales in complex networks

In this document we show the result of applying Kuramoto dynamics to complex networks. In this case there is a complex pattern of interaction between the oscillators and not just an all-to-all coupling as is usually assumed. We present our results in the form of a table for each network. The contents of each cell of the table is explained in the next table and in the following we can get the results according to these explanations.

The network:
Here we draw the network using Pajek software. Nodes are numbered or colored (depending on the size of the network) according to the community they belong to.
Eigenvalue spectrum of the Laplacian matrix of connectivities:
From the connectivity matrix, we can compute the Laplacian matrix. We plot the eigenvalues spectrum of this matrix in the following way: in the horizontal axis we represent the inverse of the eigenvalue, which in a dynamical process accounts for the time, and in the vertical axis we represent the index of the eigenvalue which accounts for the number of groups along the dynamics. This picture is useful because it can be compared with the way groups (clusters or communities) are formed along the synchronization process (see article). 
Dendogram of the synchronization process:
In this picture we show how the groups (labels are those of the nodes and colors are those of the communities) merge according to the synchronization dynamics along time (vertical axis)		 Relative time to achieve synchronization for each pair of oscillators:
Here we show the time needed for each pair of oscillators to reach synchronization. This synchronization is understood as a correlation being larger than some threshold value. The characterization is completely independent of the threshold, as is shown in our published paper PRL, since it only changes the absolute time scale not the relative one. Nodes are ordered in the same way than in the picture of the dendogram just to get toghether those nodes that synchronize earlier.
Girvan-Newman 1 (published): These authors proposed a set of networks as a benchmark for their community detection algorithms. Later on it has been widely used in order to compare the accuracy of algorithms detecting communities in small/medium networks. There are 4 communities of 32 nodes each. In general, the number of links per node is fixed to 16 and the number of links within the community and external to the community are varied. In the current case zin=15 and zout=1.



Girvan-Newman 2 (published): In the current case, zin=12 and zout=4. The community structure is less well defined. 


Two hierarchical levels 1 (published): We introduced several generalizations of the ad-hoc networks proposed by Girvan and Newman (see above). The first one consists in networks with two hierarchical levels. There are 256 nodes such that there are 4 groups of 128 and within each group 4 groups of 32 nodes each. Keeping the total number of links per node equal to 18, we vary the number of links per node at the different levels of the hierarchical distribution of groups. In this case we have z2=15 (innermost) and z1=2 (middle); we use the notation 15-2.

The network:
Here we draw the network using Pajek software. Nodes are numbered or colored (depending on the size of ht entwork) according to the community they belong to.


Two hierarchical levels 2 (published): Another case of the particular generalization discussed in the previous set of graphics. In this case we have z2=13 (innermost) and z1=4 (middle); we use the notation 13-4.

The network:
Here we draw the network using Pajek software. Nodes are numbered or colored (depending on the size of ht entwork) according to the community they belong to.


Three hierarchical levels  (Physica D): We have introduced a further generalizations consisting of three levels of hierarchy. In the present case we have 64 nodes within 2 groups at each level. The average number of links per node are 0.3-0.7-1.0-7.0 (from the more external to the more internal grouping).





One hierarchical level with a inhomogeneous distribution of community sizes  (cond-mat): In this paper we showed some of the algorithms to detect the commnity structure fail when dealing with inhomogeneous networks. For this reason we constructed ad-hoc networks in such a way.


Hierarchical networks proposed by Ravasz and Barabasi (2 levels) (published): These authors introduced a model of hierarchical network. The main difference with respect to our proposals is that in their case networks are inhomogeneous as far as the number of links per node is concerned.

Two alternative construtions of the network




Hierarchical networks proposed by Ravasz and Barabasi (3 levels) (published): These authors introduced a model of hierarchical network. The main difference with respect to our proposals is that in their case networks are inhomogeneous as far as the number of links per node is concerned.


For more information or the source codes contact albert.diaz@ub.edu
Albert Díaz-Guilera
Darrera actualització 29/03/2006