Research On The Algorithms Based On Max-clique For Community Detecting In Complex Networks

Since the complex networks exist in multiple scientific fields, the study of complex networks has become a hot research area involving biology, mathematics, physics, computer science and the complexity of sociology. The importance and significance of the study of complex networks can been seen evidently from its widely field of applications. In real life, the metabolic networks, food webs in biological systems, scientists writing and E-mail network of social system, science and technology system of the Internet, the world wide web, these networks can be abstracted as a complex network consisting of nodes and lines. In such network, nodes represent the entities, lines between two nodes represent the relationship between the two entities. Because of this, the study of complex networks has become one of the hot spots of research on the interdisciplinary research. After years of research, through statistical analysis of the various types of networks, basic statistical properties such as the small-world complex networks, scale-free line has been found. As another characteristic of this complex network, community structure has also attracted widely attention and became one of the popular content of the research.The concept of community structure was first proposed by Newman in2002. In the complex network which is abstracted into a diagram of nodes and lines, the community structure is a subgraph of the network. The characteristics of community structure is that the connections of nodes between communities are as less as possible, the connections of nodes inside the same community should be as many as possible. Because of the community structure is similar to the concept of "clusters" in data clustering, so the community structure characteristics is also called clustering features. The community structure has been found in a variety of complex networks, such as biological networks, technology networks and social networks and so on. The exploration of community structure can find the inner relations in complex networks. Community structure has important theoretical significance and practical value for analyzing and understanding the function of the complex network, and predicting the behavior of the network.Because of the detecting the communities is significant for the analysis of complex networks, nowadays there are many researchers try to design efficient algorithms for mining the community structure. Through the unremitting efforts, now there are already many different community mining methods proposed, such as the famous Girvan-Newman (GN) algorithm, label propagation algorithm, etc. How to evaluate the quality of the community structure detected is also one of the important problems in community mining research. Among the algorithms, different but similar measurements for evaluating the quality of the community mining results are proposed so as to enable the algorithms to detecting the right community as much as possible, and as far as possible to communities.In this paper, the main research work and research results are:(1) We propose a complex network algorithm for mining multilayer overlapping communities. There are many algorithms for detecting overlapping or multilayer communities in the networks, but most of these algorithms can separately detecting overlapping communities or multilayer communities. But in fact the communities in the complex networks are always both overlapping and multilayer. We propose an algorithm which can detect the overlapping and multilayer communities in the networks simultaneously. Experimental results on several networks demonstrate that the algorithm can effectively obtain the results with high accuracy.(2) We also propose a community detecting algorithm which combined the concept of clique and label propagation. Firstly, the algorithm identifies the clique in the network to generate initial communities, and then the nodes in the community marked as classified. Then the algorithm takes these classified communities as starting points for label propagation to detect the community structure of network. Since the algorithm uses the initial classification with high accuracy, it can get high quality label propagation results. Our the experimental results show that the algorithm is fast and efficient.(3) We also present a cross iteration algorithm to find community in bipartite graph. The first step of the algorithm is to find the initial communities by finding the cliques in the bipartite graph as the initial communities. Then, the algorithm detects the communities in the network by a cross-iteration. We propose a modularity based on density to evaluate the accuracy of community mining results in bipartite network. The cross-iterations will end when there is no change on the modularity. We test our algorithm on two classical bipartite graph data set, the experimental results show that our community mining algorithm based on cross iteration is fast and efficient.