Research On Complex Network Community Detecting Algorithm Based On Node Similarity

Complex networks are abstract representation of many complex systems.Their nodes represent individuals in complex systems,and their edges contain some intrinsic relationships among many individuals of the systems.With the in-depth study of the physical meanings and mathematical properties of complex networks,a common property in some actual networks,namely the community structure,has aroused the widespread concern of lots of researchers.The study found that the entire network is composed of several “communities”,and the nodes in each community are closely connected,but the connections among communities are relatively sparse.The research of community finding has very important theoretical significance and application value for analyzing the topological structure and hierarchy,understanding the formation process of communities,predicting the evolving trend,and finding the regular features of complex networks.The key to successfully detecting all complex network communities is to design a suitable and efficient community finding algorithm based on the characteristics of network nodes or edges.In this paper,two indexes of cosine similarity and simple dissimilarity between network nodes are chosen respectively as the criterion to divide the community nodes,and the corresponding algorithms for community finding are proposed.Based on several other important similarity indexes,the optimal combinations of these indexes are obtained.Moreover,several real networks,such as Zachary karate network,dolphin relationship network,American football network,and power network,are detected their community structures according to two new algorithms.The concept,basic methods and research significance of complex networks and their community finding are briefly introduced in this paper,firstly.On this basis,some important types of community finding algorithms are their division principles are discussed,such as K-L algorithm,spectral dichotomy,GN algorithm,Newman fast algorithm,and so on.Then,the cosine similarity between nodes is selected as the criterion to divide the community nodes.By means of the global similar information between communities,the results of community detecting are obtained by iteratively aggregating the two communities with the maximum similarity.The optimal number of communities is automatically obtained by the maximum value of the modularity in the iterative process.Using the new algorithm,the optimal number of community and the maximum modularity of real networks,such as Zachary karate network,dolphin relationship network,American football network,and power network,are obtained.Additionally,the optimal combination results of several similarity indexes are investigated through empirical analysis.Furthermore,the measure ofdissimilarity between nodes is defined based on the different characteristics of nodes belonging to different communities.By means of the principle of splitting algorithm,a new community detecting algorithm is designed with the dissimilarity measure between nodes.The empirical results show that the time complexity and the accuracy of community detecting of this algorithm are slightly better than GN algorithm.Finally,the conclusion is summarized and the further research work is prospected.