Research On Structural Similarity Measurement Method And Application For Dynamic Networks

In recent years,complex networks have become one of the hot research fields of multi-disciplinary intersection,and many researchers have conducted intensive research.As a crucial research direction in the field of complex networks,the structural similarity measurement problem plays an important role in practical applications such as network clustering,hierarchical reduction and state division.Currently,most network structure similarity methods are proposed for static networks.However,the structure of the network tends to evolve over time and the scale of the network will gradually increase in actual scenarios.How to quickly and accurately measure the structural similarity of each time slice of the dynamic network faces enormous challenges.Although simply considering each time slice network as a static network,most of current network structure similarity metrics can be used.However,this method not only calculates the time consuming,but also does not take into account the structural characteristics of each time slice that are related to each other along the timeline in a dynamic network.Dynamic networks have significant characteristics of large scale and dynamic evolution.How to effectively use the information of each network layer to quickly and accurately measure the structural similarity between dynamic networks is the main difficulty of this research.Based on the full consideration of the characteristics of dynamic network structure,two methods for quickly and accurately measuring the similarity of dynamic network structures are proposed.First,the eigenvalues can extract important attribute information from the structure of the graph.Therefore,using the spectral features to characterize the structural properties of the graph is a good research view.However,the computational cost of graphical spectral features is very high in a large dynamic network.In order to address the problem,a dynamic network structural similarity measurement method based on matrix perturbation theory(PNSD)is proposed.By introducing the matrix perturbation theory and combining the network perturbation concept,the eigenvalues of each time slice network are quickly updated by the spectral features of the initial time slice network.The computational complexity is linearly related to the number of nodes and the number of changed edges since there is no need to recalculate the eigenvalues in each time slice network.Second,we found the important topological information in the evolution process of the dynamic network by analyzing the structural characteristics of the dynamic network,such as backbone topology information.Based on this discovery,a backbone topology information network containing important topology information of dynamic networks was introduced.Through theoretical derivation,a dynamic network structural similarity measurement method based on backbone structure perturbation(BPNSD)is proposed,which is beneficial to distinguish the importance degree of different structural changes in each time slice network.Finally,the experimental results on real datasets and artificial datasets reveal that the two methods not only have speed advantages in large-scale dynamic networks,but also have better quality results in actual analysis applications than existing benchmark methods.