Graph clustering based on optimization of a macroscopic structure of clusters

摘要: A graph is a flexible data structure for various data, such as the Web, SNSs and molecular architectures. Not only expressed naturally by graph, it also used which does not have explicit structures extracting implicit relationships hidden in e.g. co-occurrence of words text similarity pixels an image. By extraction, we can make full use many sophisticated methods graphs to solve wide range problems. In analysis graphs, clustering problem one most important problems, divide all vertices given into some groups called clusters. Existing algorithms typically assume that number intra-cluster edges large while inter-cluster absolutely small. Therefore these fail do case noisy extraction tends yield ones because subject definition relation among vertices. Instead assumption, introduce macroscopic (MS), clusters roughly describes graph. This paper presents algorithm which, clusters, tries find set distance between MS induced from calculated ideal minimized. other words, solves optimization problem. For m-clustering problem, defined m-vertex each vertex has self-loop. To confirm performance improvements exhaustively, conducted experiments with artificial different amounts noise. The results show our method handle very correctly existing completely failed clustering. Furthermore, even less noise, treats them well if difference edge densities those are sufficiently big. We did on transformed vector more practical case. From found algorithm, indeed, works much better than ones.