Evolving the attribute flow for dynamical clustering in signed networks

In real networks, clustering is of great value to the analysis, design, and optimization of numerous complex systems in natural science and engineering, e.g. power supply systems ,modern transportation networks, and real-world networks. However, the majority of them simply pay attention to the density of edges rather than the signs of edges as the attributes to cluster, which usually suffer a high-level computational complexity. In this paper, a new rule is proposed to update the attributes flow, which can guarantee network clustering reach a state of optimal convergence. The positive and negative update rule we introduced, represent the cooperative and hostile relationship, and the attribute configuration will convergence and one can identify the reasonable cluster configuration automatically. An algorithm with high efficiency is proposed: a nearly linear relationship is found between the time complexity and the size in sparse networks. Finally, we conduct the verification of the algorithmic performance by a representative simulations on Correlates of War data.