Dissertation > Excellent graduate degree dissertation topics show

Research on Clustering Algorithm Based on Graph Coloring Theory

Author: FengShanShan
Tutor: ZhangYueQin
School: Taiyuan University of Technology
Course: Computer Science and Technology
Keywords: Graph clustering Greedy algorithm Graph coloring problem Quality evaluation index
CLC: TP311.13
Type: Master's thesis
Year: 2013
Downloads: 1
Quote: 0
Read: Download Dissertation

Abstract


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.

Related Dissertations

  1. Multi-attribute undirected weighted graph clustering method,O157.5
  2. Based on intelligent algorithm research dimensional cutting stock problem,TP301.6
  3. High-efficient Incomplete Search Method on Graph Coloring Problem,O157.5
  4. Web-based data mining for personalized Search Engine,TP391.3
  5. Research on Attributed Graph and Clustering Tree Based Large Datasets Image Retrieval,TP391.41
  6. Research on Graph-Clustering Algorithms Based on Node Structure Connectivity,O157.5
  7. Research on Video Summarization by Clustering and Mining,TP391.41
  8. Graph Clustering Algorithm Based on the Degree and the Number of Vertices,TP301.6
  9. Research of Spectrum Resource Optimization and Multi-channel Technology in Wireless Network,TN929.5
  10. Research on Computational Model of DNA Self-Assembly and Its Application in Graph Coloring Problem,TP38
  11. LDPC codes of girth enhance research,TN911.2
  12. Research on the Evaluation Index System of CPA’s Audit Quality,F224
  13. Research and Application of Association Rules Algorithm Based on Undirected Graph,TP311.13
  14. Research on Application of Mutation Testing,TP311.53
  15. Hybrid Genetic Algorithms for Graph Coloring Problems,TP18
  16. Earnings Quality Assessment for Listed Manufacturing Companies,F224
  17. Research on Power Allocation Mechanism in the OFDM-Based Cognitive Radio Systems,TN919.3
  18. Study on Gateway Placement Algorihtm in Wireless Mesh Network,TN929.5
  19. Medical Diagnosis System Based on the Integrate of RS and BP Neural Network Algorithm,TP399-C8
  20. The Study of College Course Dispatching System Based on Genetic Algorithm,G647
  21. Path Optimization Algorithm of NC Spraying,U671

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer software > Program design,software engineering > Programming > Database theory and systems
© 2012 www.DissertationTopic.Net  Mobile