Research On Community Structure Discovery Algorithm Based On Dependence And Similarity

In recent years, the complex network has become one of the most popular research fields in complexity science, which has a significant contribution and sustained impact in the field of information science, physics, biology, mathematics, sociology and management. With the in-depth research of complex networks model and network dynamics, the researchers found that the real networks have the property of community structure:the nodes in the network tend to form clusters, and the nodes in the same cluster often have the similar functions and characteristics. Additionally, the relationship of nodes in the same cluster is closer while the relationship of nodes in different clusters is looser.At present, community structure detection is one of the principal research areas in complex networks and has important theoretical and practical significance. The definition of community structure given by researchers and the explanation of significance demonstrated by community structure property are different in different scientific fields, resulting in a series of community structure detection algorithms with different perspectives and strategies. However, many algorithms do not take full advantage of local features and global information of the complex networks, so these algorithms can't effectively partition the fuzzy nodes of the community, or they must be at the cost of high time complexity and complex partition constraints, which leads to the limited application range of the algorithm. Based on the above issues, this paper analyzes and studies the static statistical characteristics of complex networks and the algorithms of community detection. In general, the main works include the following three aspects:(1) We propose a community detection algorithm based on the node dependence and the fusion of similar communities (NDSF algorithm). In the algorithm, the concept of node dependence, node condition dependence, community similarity and community connectivity are defined. The algorithm firstly divides the whole network into several local networks with large average clustering coefficients, which constructs a skeleton for the complex networks. And then, according to the definition of the community connectivity, the algorithm will continuously absorb the community edge nodes and small communities into the backbone network until all the nodes have been accurately allocated to the community.(2) We construct an experimental simulation platform. In order to verify the correctness of NDSF algorithm, we designed and implemented a simulation platform, which mainly includes three modules:input module, algorithm execution module and evaluation indexes calculation module. Specifically, the input module includes four kinds of object converter, which is responsible for converting the text data to the memory object. The algorithm execution module includes three algorithms, namely, NDSF (algorithm in this paper), GN (Girvan-Newman) and NFA (Newman Fast Algorithm). The evaluation indexes calculation module includes three kinds of community detection evaluation indexes, namely, division correctness, algorithm accuracy and modularity.(3) The comparison experiment of NDSF algorithm is completed by our simulation platform. Compared the computer generated network with GN Algorithm and NFA Algorithm in division correctness and algorithm accuracy, NDSF algorithm also has a high accuracy for networks with obvious community structure; On the Zachary karate club network, the dolphin social network and the American college football network, compared with GN Algorithm and NFA Algorithm in modularity, NDSF algorithm can effectively classify fuzzy edge nodes for networks with unobvious community structure, and the partition results are better than GN and NFA algorithms.