Research On Community Detection Algorithms In Complex Networks

Many complex systems in reality can be represented by complex networks such as social networks, biological networks, and technological networks and so on. Community structure is one of the important attributes in complex networks. There are some nodes clustering as communities that are subgroups of nodes where the edges between the nodes in the same groups are much denser than those in different groups. The complexity, diversity and dynamics of the network lead to research of discovering community structure more complex. Detecting community structures is a challenging task in analyzing networks. The task of detecting community structures contributes to analyze the structures and functions of networks, to find hidden mode, to understand and predict the dynamics laws of the network. It is of importance signification for the use of the network. Network community detection is also an essential part of the practical applications of all kinds of networks such as social relationship, wireless sensor, and mail interaction. Many algorithms have been presented to detect communities recently. However, it is research direction of community detection algorithm that how to get community detection result more accurately without any priori information and how to reduce complexity of the algorithm.The main research of this dissertation covers three aspects including community detection, overlapping community detection and dynamic community detection.The main achievements and innovation of our research are as follows:1. In order to solve the problem of resolution limit of modularity optimization methods, a multi-objective discrete cuckoo search algorithm with local search for community detection(MDCL) is proposed. To the best of our knowledge, it is first time to apply cuckoo search algorithm to community detection. Two objective functions termed as negative ratio association and ratio cut are to be minimized. In the proposed algorithm, the nest location updating strategy and abandon operator of cuckoo are redefined in discrete form. A local search strategy and a clone operator are proposed to obtain the optimal initial population. The experimental results on synthetic networks and real world networks demonstrate that MDCL algorithm has better performance than other algorithms and can discover the higher quality community structure.2. For solving overlapping community detection problem, we present an ant colony based overlapping community detection algorithm(Ant CBO) which mainly includes ants’ location initialization, ants’ movement and post processing phases. The strategy of ants’ location initialization is designed to identify initial location of ants and initialize label list stored in each node. During the ants’ movement phase, the entire ants move according to the transition probability matrix, and a new heuristic information computation approach is redefined to measure similarity between two nodes. Every node keeps a label list through the cooperation made by ants until a termination criterion is reached. A post processing phase is executed on the label list to get final overlapping community structure naturally. We illustrate the capability of our algorithm by making experiments on both synthetic networks and real world networks. The results demonstrate that the proposed algorithm has better performance in finding overlapping communities and overlapping nodes on synthetic datasets and real world datasets comparing with state-of-the-art algorithms.3. Link clustering method for overlapping community detection has attracted a lot of attention in the area of complex networks. However, it may cause the clustering result with excessive overlap. To solve this problem and improve the accuracy of detecting overlapping communities in networks, a density based link clustering algorithm(DBLC) for overlapping community detection is proposed in this study. It creates a number of clusters containing core edges only based on concept named as core density reachable during the expansion. Then an updating strategy for unclassified edges is adopted to assign them to the closest cluster. In addition, a new similarity measure for computing the similarity between two edges with a common node is presented. Experiments on synthetic networks and real networks have been conducted. The experimental results demonstrate that our method performs better than other algorithms in detecting community structure and overlapping nodes aspects.4. Identifying community structures in static networks misses the opportunity to capture the evolutionary patterns. Research on community detection in dynamic network can discover dynamic community structures effectively. Therefore, a multiobjective biogeography based optimization algorithm with decomposition(MBBOD) is proposed to solve community detection problem in dynamic networks. In the algorithm, the decomposition mechanism is adopted to optimize two evaluation objectives named modularity and normalized mutual information simultaneously, which represents the snapshot cost and temporal cost respectively. A novel sorting strategy for multiobjective biogeography based optimization is presented for comparing quality of habitats to get species counts. In addition, problem-specific migration and mutation model are introduced to improve the effectiveness of the new algorithm. Experimental results both on synthetic and real networks demonstrate that our algorithm is effective and promising, and it can detect communities more accurately in dynamic networks compared with DYNMOGA and Facet Net.5. Evolutionary clustering is a popular method for community detection in dynamic networks by introducing the concept of temporal smoothness. Some evolutionary based clustering approaches need an input parameter to control the preference degree of snapshot and temporal cost. To break the limitation of parameter selection and increase accuracy of detecting communities, we propose a multiobjective discrete cuckoo search algorithm to discover communities in dynamic networks. Firstly, ordered neighbor list method is used to encode the location of nest for population initialization. Secondly, a discrete framework of cuckoo search algorithm(DCS) is proposed with a modified nest location updating strategy and abandon operator. Finally, based on the proposed discrete framework, a multiobjective discrete cuckoo search algorithm(MODCS) is proposed by integrating the non-dominated sorting method and the crowding distance method. Experiments on synthetic networks and real networks have been conducted to test the proposed algorithm. The experimental results demonstrate that MODCS algorithm is effective to discover community structure at each time step.