The Partition Method For Community Structure In Complex Networks

The rapid development of information technology makes human society a big step into the Internet age. There are networks such as electric power network and transportation network which we can't live without in the daily life. There are also other networks such as Internet, WWW and research cooperation network which we use to get information. People live in a world full of complex networks.These large-scale networks are widespread in the social system, which makes the research of complex networks necessary, so people launched a wide research on the topology and the dynamic behavior of networks. In recent years, as the WS small-world network model and the BA scale-free network model was proposed, the study on complex networks is achieving on a climax at home and broad now.Community structure is an important characteristic in complex networks. Seeking and analyzing communities is an invaluable tool of understanding the structure of networks. Finding community structure is a very popular issue in researches of complex networks. A lot of algorithms have been proposed to detect the community structure in networks. In this dissertation, we introduce the clustering analysis to complex networks in finding community structure. Main tasks are as follows:1. Introduce the basic concepts of complex networks and its basic properties: degree and degree distribution, clustering coefficient, shortest path, community structure, and the two kinds of complex network model. These properties and the complex network model is the premise of our research complex networks.2. Community structure research history and significance of the algorithm are introduced, especially several representatives algorithms which used to find community structure. These algorithms are divided into two categories:hierarchical clustering in Sociology and graph partition in computer Science. These methods will divide the whole network into a number of simple sub-networks, which let research more easily. In this dissertation, we give a brief introduction of the purpose of clustering, significance and current methods commonly used in clustering.3. The method of multi-community finding in complex networks using the spectral bisection method based on multidimensional eigenvector from normal matrix is provided. This algorithm combines information on multiple feature vectors and use clustering analysis in data mining to detect the community structure in complex networks. Clustering analysis algorithm is an important tool for community detecting, In this dissertation, several common clustering algorithm are used. We demonstrate the availability of our algorithms in two different kinds of network. We also make the comparison and analysis of the experimental results in initial sensitivity, time complexity, and accuracy. The algorithm enables the efficient division of many communities in relevant network where the clustering characteristics aren't very obvious. And the same time, the experiments find that the algorithm based on modularity function may not be able to find all of the real network community.