Research On Spectral Partitioning Based On Improved Resistance Distance

Complex networks are abstract representations of complex systems in the real world,and community structure is a significant characteristic of networks.Dividing the network into communities is helpful to analyze the structure of the network,find the basic functional units of the network and discover the evolutionary law of the network.Therefore,the community detection of network has important theoretical significance and wide application prospects.The spectral partitioning algorithm based on the graph theory can be used to detecting communities in networks.It is widely used in community d etecting because the result of the division is highly reliable.The classical spectral partitioning method first constructs a similarity matrix according to a certain similarity measure,then calculates its Laplacian matrix,and selects some eigenvalues and eigenvectors of the matrix to cluster the points of the graph.In the process of spectral partitioning,constructing a reasonable similarity matrix can improve the accuracy of result.Resistance distance is a kind of distance on the graph,which can be used to measure the similarity of two points on the graph.In recent years,some scholars have proposed a spectrum division algorithm based on resistance distance and have achieved some important results,which provide important research content for spectrum division methods and have important research significance.The algorithm can achieve better division results,but in some cases there are still certain limitations.In this regard,this paper researches and analyzes this,and improves the resistance distance according to the limitation.The main contents are as follows:Firstly,considering the relative position between two points,this paper combines the adjacent relationship and the shortest distance of the points on the graph to improve the resistance distance,and gives a resistance distance function.Using the function,this paper constructs the similarity matrix.Moreover,the Cheeger constant is taken as the cost function,and the corresponding spectral bisection method is given.Secondly,from the point of view of the importance of the nodes,a resistance distance function is given by combining with the adjacency and the degree of the points on the graph to improve the resistance distance.The similarity matrix was constructed using this function,and the corresponding spectral partitioning method was given.Finally,this paper selects five real networks with real community structures,uses the method in this paper to conduct community division experiments,and compares with other spectral partitioning methods.The experimental results show that the improved resistance distance in this paper can effectively measure the similarity between points in the network,and the two spectral partitioning methods based on the improved resistance distance given by this paper can effectively detect the community structures of networks.