Comparison And Analysis Of Quality Indexes For Evaluating Graph Clustering

There are many large systems in the real world. The network thought is introduced to the its analysis and research in order to better understand the structure, function and predict its behavior in particular case, and has achieved great success; Such as acquaintance networks, scientific collaboration networks, protein interaction networks, the Internet, the world wide web, etc. Network community structure is their common attributes. So we can put the network as an abstract graph constructed by nodes and edges, nodes represent the entity in the real world, and edges represent the relationship between entities, such as scientists in collaboration networks, the entity of scientists was abstracted as the node of the graph, and the collaboration relationship between scientists was abstracted as an edge. Discovering network community structure is to clustering process of the abstract graph. Graph clustering, the process of discovering groups of similar vertices in a graph, is a very interesting area of study, with application in many different areas.Clustering as data mining a key step plays an important role in many application. It has accumulated much mature clustering method, and each method has its own scope of application. Clustering results are also different using different clustering method for the same data set. So, how to evaluate the quality of the clustering results? In the specific application, in order to choose the most appropriate clustering method, people puts forward some clustering evaluation index from a different perspective. Graph clustering quality evaluation index is an important index of evaluating clustering algorithm whether the clustering result is good. It is important not only to dynamics of relationships in a given graph. One of the most important aspects of graph clustering is the evaluation of cluster quality. However, evaluation results different evaluation indexes are not the same for the same clustering results. Each evaluation index has its applicable scope and it will become failure beyond the scope of the index itself. How to ensure that the effectiveness of clustering and clustering evaluation become a key issue of clustering application. Much research has focused on comparison validity of clustering algorithm, and less comparison clustering evaluation index. However, comparing the clustering algorithm under the premise of not confirming the validity of clustering evaluation indexes is not reasonable. Many quality evaluation metrics for graph clustering have been proposed in the literature, but there is no consensus on how they compare to each other and how they perform on different kinds of graphs.Kleinberg advocates the development of clustering that will be "independent of any particular algorithm, objective function, or generative data model." and comes up with "three axioms"(Function Scale Invariance, Function Consistency, Function Richness) about clustering function aimed to define what a clustering function is. But these seemingly natural axioms lead to a contradiction—there exists no function that satisfies all three requirement. Ben-David change the primitive that is being defined by the axioms from clustering function to clustering-quality measures and reformulate the "three axioms" in term of clustering-quality measures and show that this revised formulation is not only consistent, but is also satisfied by a number of natural and effective clustering-quality measures. In addition, he extend the set of axioms by adding another axiom that is required to rule out some measures that should not be counted as clustering-quality measures.This paper, from the graph clustering on the frame structure (namely the similarity measure, clustering algorithm and clustering quality evaluation) conducted the analysis and research on the graph clustering quality evaluation indexes. Our result shows that the popular indexes have a difference in the ability of evaluating the clustering results including identifying the optimal cluster sensitivity and the effects of the choice similarity measures and clustering algorithms on evaluating indexes.