Research Of New Clustering Algorithms To Mine Community Structure In Complex Networks

Since the date when complex networks had been put forward, it has experienced only decade. So it's a very'young'science. In the first few years, this science attracted a large number of scientists and scholars, just because of the rise of complex networks theory and applications were just beginning. Under such an atmosphere, the outcomes of complex networks mushroomed in many journals and meetings at all levels, types, etc.The birth of complex networks has background of graph theory, complexity science and data mining technology. The origin of complex networks is the ER random graph theory established by Euler and Renyi. Their theory could still be good when applied in complex networks. Complexity science provides a methodology for complex networks research, and it's a guiding science. Data mining provides the algorithm tools for the discovery of the structure and the potential property. This background knowledge supports the theoretical system of complex networks. In addition, complex networks appeals scientists and scholars in various fields because of its universality in the real world. They bring new blood from their fields. For example, biologists bring genetic algorithm and ant colony algorithm, while sociologists bring hierarchical clustering algorithm.Initially, people use the model method to study complex networks. Doctor Watts and his teacher Strogatz proposed the small-world model firstly. Doctor Barabási and his teacher Albert proposed the scale-free model next year. They are the most important and typical models all along the time. By analyzing the nature of the two models, many scientists began to study the real networks. They provide many parameters by analyze the real networks which are of their filed, such as average distance, clustering coefficient and degree distribution. Their studies provide that the two model properties exist in lots of real networks. However, it is found that a certain model parameters are different between different real networks. In this way, people can't use one or two models to describe all the real networks. How to study the complex networks theory, how to deal with a variety of real networks becomes a problem. Complexity science gives us new suggest for the problem. Complexity science combines reductionism and holism, which can be called coherentism. Complex networks can be studied by the ways of coherentism of course. No longer to study the overall effect, people turn their direction to the internal. It is found that complex network has another property apart from the small-world property and scale-free property. That is community structure. A lot of real networks have this property.Community structure has many names, such as modules, classes, groups, cluster, etc. It is the cross-cutting that lets researchers from different disciplines and fields are interesting of it, and use it in their fields. Before the complex networks, many scholars had studied graph theory and social networks. At the same time, the knowledge tells us that the process of using clustering method to divide community structure is mining communities from complex networks. We can apply various knowledge and technology to complex networks.There are many algorithms to mine community structure, some of which can be got in Chapter III. However, more and more large-scale complex networks appear, tens of thousands of nodes calls for a lower time complexity. Also the complexity of networks made it difficult to mine community structure. A large number of scholars, propose new algorithms, or apply a typical algorithm to real networks to make such that the effect which is good or bad. You can see that, the current study of the community structure is no less than the models studies in the beginning.Based on the background, I try to put forward a new algorithm of mining community structure. First of all, for a network which has known communities number, this paper presents a new search algorithm---SBCC algorithm. SBCC algorithm has two strategies. Next to the algorithm, this paper gives the experiment validation. After this work, this paper gives two improved algorithms of the G-N algorithm and fast spitting algorithm. Then this paper proposed a new clustering algorithm---DBNS algorithm.Taking the limitations of the above-mentioned algorithm into account, this paper give expand algorithms to make them adapt to networks which has an unknown communities number. The max change is to divide the networks into two parts every time. At last, this paper apply expand improved G-N algorithm and expand DBNS algorithm to two real networks. The result provides that the two algorithms also have the same effect, though the Q value is a little shy of the value reported by G-N algorithm.Scientific discovery is often a process from quantitative change to qualitative change. Studying the clustering algorithm of community structure is also an amount of accumulation, whether this paper proposes a new algorithm, or just apply algorithm to real networks. We look forward to the rapid arrival of the qualitative change.