Research On Clustering Algorithm Based On Graph Coloring Theory

In order to reveal the valuable information which hidden in the complicated structure, researchers put forward the thought of network structure. Figure is a method of network structure modeling. In a figure, entity is seen as nodes of the graph, and the relationship between the entities is seen as the edge, then, the analysis of the structure of complex networks is transformed into the analysis of the graph structure. Graph clustering as a kind of important data mining analysis technology, and the aim of using graph data clustering is to find those well-connected sub graphs in a large graph, and the vertexes in those sub graphs are strongly connected, but the vertexes between sub graphs are connected weakly.Nowadays> There are many graph clustering algorithms, such as Kernighan-Lin algorithm, split the traditional spectrum method based on Laplace matrix and designed, the GN algorithm and Newman algorithm, etc. However, these algorithms have some drawbacks. for example, only the figure can be obviously divided into two subgraph, Kernighan-Lin algorithm and split the traditional spectrum method based on Laplace matrix and designed can be used effectively.The GN algorithm will not stop until there are not have any edge, so it will not give the result of clustering directly. In short, graph clustering algorithms exist the following problems:(1) With the increase of amount of data, the algorithm running time will be very long;(2) The complexity of the figure will affect the clustering quality.Based on the above problems, this paper applies graph coloring theory in the graph clustering. Graph coloring problem is a widely research of combinatorial optimization problems, it is widely used in the division of administrative areas, the allocation of resources, the automatic detection of discrete programming, network, etc. There are many methods to solve the problem of graph coloring, such as blind search, heuristic algorithm and greedy algorithm, etc. This article uses greedy algorithm, this is because the running time of the greedy algorithm almost a few milliseconds when dealing with huge amounts of data, so it can reduce time complexity of the algorithm.This paper applies graph coloring theory in the graph clustering firstly. Firstly, it can obtain the preliminary clustering results through using graph coloring theory based on the greedy algorithm. Second, in order to achieve better clustering effect, the greedy algorithm was improved.The contribution of this paper is as follows:(1) We firstly systematically presented the research status of the graph clustering technology, and gave a comprehensive summary of characteristics, practical significance, as well as the current problems in real-life application.(2) Then, we presented the application of the graph coloring, and summarize three kinds of definition of graph coloring problem, respectively the vertex coloring, edge coloring and full coloring, in which the latter two can be turned into graph vertex coloring, therefore, this paper mainly discuss the graph vertex coloring.(3) Clustering results are also different using greedy algorithm for the same data set. So, how to evaluate the quality of the clustering results? We put forward to a quality evaluation index called DunnG.Meanwhile, the other quality evaluation index is raised---Distinctness, based on Dunne.(4) We use four different types of data which selected from UCI data set. The experimental results are compared with classical k-means algorithm method and ex-improved algorithm, and the algorithm proposed in this paper can achieve higher clustering quality.