Research On Agglomerative Graph Clustering Algorithm Based On Community Kernels

The complex networks are high abstraction of large networks in the real world. They don't have characters of regular networks and random networks which were researched in custom networks. In which, the most representational research is small-world properties, free-scale, clustering, network transfer and sociality structure. In recent years, it is becoming popular that modeling by interaction networks and finding the internal social structure from the complex networks by graph clustering method. Agglomerative clustering is one of most important methods. The course of agglomerative clustering is a granularity increasing course step-by-step which is start with complete discrete nodes in the network. A common agglomerative clustering algorithm is not direct-consider explicitly the existence of clustering centers of networks, which may affect the accuracy of clustering result.(1) Introduced a conception of reasonable community kernel of network in the real world. The network has the property of social community. The structure is compact in the same clustering and loose in different clustering. Based on this property, introducing the conception of kernels of network, which locating the compact nodes sets from structure, avoiding the efficient wastes which are caused by custom agglomerative algorithm.(2) Approves a similarity measures on the base of network structures. It could measure the similarity between nodes and community kernels accurately and could improve the agglomerative algorithm.(3) Designed and programmed the clustering algorithm on Visual Studio 2008+Matlab R2009a. Analyzed and tested a quality of classic date sets. It has been proved that the algorithm could improve the accuracy of clustering.In short, this paper researched the community structure, and approved a new graph clustering algorithm by defining a reasonable distance measure which generated by community kernels of networks. The experimental results and the examples both show that the algorithm could improve the accuracy of clustering.