Research Of Community Detection's Algorithm Based On Complex Networks

Nowadays, research on complex networks has integrated into the social sciences, life sciences, communications science and electrical science and many other important scientific fields, with the in-depth of research on complex networks, scientists gradually discovered many important properties of complex networks: small world, scale-free, community structure and so on. Community Structure means: nodes in the same community are linked closely and nodes in different communities are linked sparsely. Detecting community structure of complex networks contributes to analyze the topology structure and characteristic of complex networks, also to understand the functions of them, and can found the hidden disciplines of complex networks and forecast the behaviors of them. Therefore, research on detecting community structure in complex networks has become a hotspot in recent years and formed an important research direction.Clustering analysis is an important research area on data mining, it is a analysis process that the physical or abstract objects are divided into many classes or clusters composed by similar objects. Objects in the same cluster have great similarity and objects in different clusters have great dissimilarity. Clustering analysis is widely used in data mining, statistics, machine learning, spatial database technology, biology, marketing and many other fields.The community detection on complex networks is very similar to the clustering analysis. Based on the in-depth study of community detection's algorithms on complex networks, we mainly applied clustering analysis method to community detection on complex networks. First, we transform the network into a data structure suitable for clustering analysis, and then cluster these data according their similarity, thus obtain the community structure of the network.The works done in this paper are as follows:(1)We proposed a community detection algorithm based on signaling process and hierarchical clustering (SHC algorithm): based on signaling process on complex networks, we got influence vectors of each node, translate topological structure of each node into geometrical relationships of vectors in algebra spaces, each node was expressed by corresponding influence vector, and then by the aid of hierarchical clustering modularity method, we detected communities effectively.(2)We proposed a community detection algorithm based on dissimilarity coefficient and spectral method (DSC algorithm): based on the standardization matrix of network, we computed the eigenvalues and projected the network into eigenspace. We raised the definition of dissimilarity coefficients, where moving steps of Brownian particles was replaced by Euclidean distance, and then we calculated the dissimilarity coefficient of each pair node and used hierarchical clustering method to detect the community structure of the network. The Luca Donetti algorithm was based on the Laplacian matrix, and used angular distance to measure the similarity of nodes. Experiments proved that two kinds of algorithm worked well, but run-time of DSC algorithm has been improved than Luca Donetti's.(3)With data simulations on the network generated by computer and real networks, SHC algorithm and DSC algorithms have received relatively good results. And two kinds of algorithm were applied to weighted networks, also received a high accuracy rate of community classification. Finally, the two algorithms were compared to the traditional classical algorithm.