Research On Community Detection In Complex Networks

If the entities are treaded as nodes and the relationships between them as edges, many systems in the world can be represented in the form of network. For instance, academic papers and their reference relationships can constitute the citation network, and numerous web pages can be connected with hyperlinks to form the World Wide Web. Since the relationship between entities in these systems (networks) are rather complex, demonstrating a lot of properties that the simple networks does not owned, such as small world, scale-free, self-organization or community structure, thus such systems are usually called complex networks. In complex networks, the cluster of nodes with features that the nodes in which are connected more closely with internal partners and sparser with external partners, is called as community. Detection of community structure is a research hotspot in the field of complex networks, which is of great significance in practical applications. For example, mining the community structure of citation network is helpful for recommending papers to the researchers with same interest, and detecting the community of World Wide Web is also useful in tracking hot topics. Currently, there are some algorithms proposed in the field of community detection,such as the algorithms based on betweenness division, modularity optimization, spectrum analysis etc. These algorithms are of great significance for the development of community detection. However, they have some problems such as high time complexity or resolution limit. In light of the significance of community detection and the deficiency of existing algorithms, the exhaustive study about the design of efficient and effective community detection algorithm is conducted in this dissertation. The main contributions include: (1) The enhancement mechanism of community structure is studied, and a methodfor this enhancement based on the similarity of information dissemination is proposed. The main purpose of community structure enhancement is to present a preliminary contour of community, which would be an effective basement for the future process of community detection. In the traditional methods, the enhancement of community is realized by taken the similarity between nodes as the weight of link of the same nodes. The traditional methods only consider the number of common neighbors, but not the relationship between nodes. In order to fully consider the effect of connection on similarity computation, we introduced the idea of information dissemination mechanism, and designed a model based on hierarchical structure for approximate evaluation. The experiments show that, the similarity calculated by our method is more effective than other traditional methods in the presentation of community contour.(2) In the respect of global community detection, a method which is able to control the levels of resolution by adjusting the strength of enhancement is proposed. In this method, the differential component of enhanced weights is firstly extracted, and then mixed with original weights of edges, making the enhancement of community structure adjustable. Because that the corresponding relationship exists between enhancement factor and legibility of community contour, the controllability of the resolution is realized by reach the maximum of modularity with different weight.Moreover, a theory about the corresponding relationship between community core and enhanced weight is also proposed. Based on this hypothesis, the cohesive subgroups with high cohesion are extracted, and then adjusted and merged with local modularity optimization. After these steps, the community structure can be easily detected. Experiments show that our proposed algorithm is more effective than some other classical algorithms.(3) In the respect of local community detection, two algorithms are proposed, which are based on the weakening of interference nodes and based on expanding of cohesion core respectively. For the first algorithm, the characteristic of missing source node in target community of CnllLocal algorithm is utilized. The communities that does not contain source node are firstly extracted, and then the interference of the nodes in these communities for community detection is reduced. For the second algorithm, the theory about the corresponding relationship between community core and enhanced weight is used. The cohesive cores are extracted at first, and then the source nodes are replaced with such cores. At last, the existing local algorithms are used for community detection based on the new source. Experiments show that, no matter for the source node located in the community core or the region, the proposed optimized algorithms are more effective than classical versions.The innovations are as follows:(1) A community enhancement method based on the information dissemination similarity is proposed. This method takes full account of the effect of links on the similarity between nodes and makes the community enhancement more reasonable.(2) For controlling the resolution levels, a method based on adjusting the degree of enhancement of community structure is proposed. This method can effectively alleviate the resolution limit.(3) A theory that the weight of edges after enhancement are corresponds to the centrality of community is proposed. According to this theory, the cohesive subgroups and community cores can be easily extracted, and the accuracy of global and local community detection can be improved accordingly.Overall, the research content of this dissertation is mainly concern the algorithm optimization of community structure enhancement, global and local community detection in complex networks. The algorithms proposed in our research are of low time cost and high accuracy, and they are of both theoretical and practical significance for obvious applications such as online education.