Graph Clustering Algorithm Based On The Degree And The Number Of Vertices

Clustering (or partition) is a hot research issue in mathematics, computer science, management science and other areas. It is also widely applied in the fields such as pattern recognition, data analysis, communication, biology and business. Graph clustering applies the graph theory method to graph classification, and it is a very important variant of data clustering. Different from ordinary numerical clustering, the clustering based on graph theory has its own particularity, the similarity between data objects in data set is often expressed by a graph.Generally, graph clustering clusters are groups with a high density of within-group edges and a lower density of between-group edges. In this paper, we analyze the graph-clustering algorithms based on the inter connection ratio (MV-ICR for short) proposed by Moussiades and Vakali (Clustering dense graph:A web site graph paradigm. Information Processing and Management,2010), develop the MV-ICR clustering algorithm, proposed a new clustering coefficient and a new clustering algorithm. The main works are as follows:(1) It proposes a clustering strategy based on ICR and improves the problem that several clusters of equal relation can't be classified at the same time as in ICR clustering algorithm. The improved algorithm makes clustering process quickly and clustering result clearly. It is more reasonable and effective to compared with MV-ICR algorithm.(2) It proposes a new clustering coefficient based on the number of connecting vertices within a cluster (called inter vertex connection ratio, IVCR) and proposes a new clustering algorithm based on IVCR. Some examples indicate that the new algorithm proposed is reasonable and effective.(3) It compares and studies the graph types applicable to ICR algorithm, improved ICR algorithm and IVCR algorithm.