Spectral Coarse Graining Of Complex Networks And Its Optimization Algorithm

The framework of complex network can be used to describe a variety of complex systems consisting of large number of interactive units.Under this framework,a unit corresponds to a node of the network.If two units interact with each other,the two nodes are connected by edge.For example,computer network is a network formed by large number of computers connected by optical cables.Biological neural network is a network formed by a number of neurons through synaptic connections.With the advent of the big data era,more and more actual networks are beyond the imagination of people(About 1 trillion web pages on the Internet,and there are about 100 billion neurons in the human brain.).It’s generally difficult to handle these big complex networks,since the storage of these big networks has strong impact on hard disk usage,and the computation of them will be also time-costing.Therefore,coarse graining method complex network has been proposed to study and understand various dynamic behaviors occurring on large networks through reduced network.The coarse graining of complex networks is a promising research method for large-scale network analysis and visualization.It requires reducing the size of the network while maintaining some topological information or dynamic properties of the network.This paper focus on spectral coarse graining method based on network synchronization dynamics and its optimization algorithm.The main research contents are as follows:(1)A new spectral coarse-graining algorithm based on K-means clustering(KCSCG for short)is proposed.The algorithm uses K-means clustering method to cluster network nodes,merge nodes in clusters,and extract coarse-grained network.KCSCG not only reduces the amount of calculation,but also precisely controls the scale of the coarse-grained network.At the same time,KCSCG has an excellent effect in maintaining network synchronization capabilities.A large number of numerical simulations and Kuramoto model examples on several typical networks verify the feasibility and effectiveness of the proposed algorithm.(2)Optimization algorithm for coarse-grained networks are proposed to coarse the network size to a minimum scale while maintaining a certain accuracy of network synchronization capabilities.Based on the spectral coarse graining(SCG)method,two coarse graining optimization algorithms,called variable step size optimization algorithm(VSSOA)and variable scale optimization algorithm(VSOA),are proposed.Given the network synchronization capability with different precisions,calculate the corresponding coarse-grained optimal step size or optimal scale,and extract the optimal coarse-grainednetwork,and apply it to several networks with different network structures.(3)Based on the K-means clustering spectral coarse graining method,an extraction algorithm based on synchronization optimal coarse granulation network is proposed.Given the accuracy of the synchronization error,the optimal scale is calculated,and then the KCSCG is used to obtain the synchronous optimal coarse-grained network.The feasibility and effectiveness of the extraction algorithm are further verified by the phase synchronization of coupled Kuramoto oscillators on typical networks.Related research provides a new perspective to understand and analyze large-scale complex networks.