Community Detection in Complex Networks Using Coupled Kuramoto Oscillators

摘要

Recently, complex networks have been used to represent natural and artificial agents and their relationships. A common feature in these networks is the presence of communities or modular structures in which a vertex related to a determined community is, proportionally, more densely connected to other vertices belonging to its own community than to the rest of the network. Several approaches have been proposed dictating a dynamic rule for the vertices based on the topology of the network, in other words, the dense connectivity of the vertices inside a community would provide similar values for the metric used in the dynamics, which could be used as a way to determine the eventual communities existing in the network. In this paper, the rule for the dynamics is the Kuramoto's synchronization model for coupled oscillators. In this scenario, the network is interpreted as composed of oscillators obeying this synchronization model. Since in its original form this model does not realize communities, a modified one is used, where phases within vertices of a same community evolve together to a final common phase value and vertices of different communities are forced to have their phases far different when the dynamic equilibrium is reached. To verify the correctness of this approach, the model has been tested on Girvan-Newman's benchmark networks, ranging the mixing parameter from a scenario in which the communities are completely isolated to one in which the community is structure is barely observed. These tests have provided good results on detecting the existing communities, even in the most difficult cases. Minor tests were also made on symmetrical and assymetrical Lancichinetti-Fortunato-Radicchi networks (LFR).