Research On Community Detection Algorithms In Complex Networks

Nowadays, the study of complex networks has become an important research direction in scientific research. There are a lot of community structures in complex networks. And detecting the community structures in complex networks is an important way to understand the structure and function of complex networks. With the amount of information rapid growth, classic community detection algorithms are unable to detect the community structures in large-scale complex networks because of their high time complexity. Therefore, researching a new community detection algorithm with high accuracy and low time complexity for large-scale complex networks is imminent. Due to the important node in the community has a great influence, detecting the important node in the community is of great significance for the security, control and regulation of the network. However, current common important nodes detection algorithms consider only one factor and detect important nodes in the whole network, so it’s necessary to explore an algorithm to detect important nodes in communities with all things considered.Classic community detection algorithms major research on the unweighted network. The unweighted network can’t reflect the connection strength between nodes and most real networks are weighted networks. It’s more reasonable to describe these networks by weighted network models, so we should model the weighted networks before detecting the community. Considering the influence of the connection times between two nodes, the number of common neighbors and the weight of nodes, this thesis proposes a weighted network model based on common neighbor nodes. This thesis respectively to three standard test data uses weighted network model based on common neighbor nodes to verify the degree and weight of nodes in the model meeting power-law distribution.Most community detection algorithms use global modularity to divide nodes and have high time complexity, this thesis proposes a local community detection algorithm based on adjacent sides. In combination with adjacent sides feature of local community, this thesis comes up with a judgment function to divide edges of weighted networks into communities. Then it defines an attribution judgment function on overlapped nodes to obtain non-overlapping communities. Then the local community detection algorithm based on adjacent sides used on three standard test networks and two large-scale complex networks, and compared with the classical community detection algorithms. The results of simulation show that the algorithm in this thesis has not only high accuracy but also low time complexity, which greatly improves the execution efficiency of the algorithm, and suitable for large-scale complex networks to detect communities.Based on the communities obtained in previous step, this thesis detects important nodes in every community. Contraposing current common important nodes discovery algorithms consider only one factor, this thesis proposes a algorithm to detect important nodes in communities connecting with the connection status, the location in the community, the weight and the neighbor of the node. It first defines the proximity factor, degree centrality factor and additional factors affecting by neighbor nodes of weighted network, and then it proposes a node importance function to detect the important node in the community. Through the simulation on three standard test network and two large-scale complex networks, it founds the important nodes in the community. Compared with common important nodes detection algorithms, the proposed algorithm is more reasonable and easier to distinguish the important node in the community, and suitable for large-scale complex networks.