关键词: 滴水原理, 有符号图, 关联聚类, 整数线性规划

Abstract: With the development of various new media, there are many new issues popped up in data mining. Correlation clustering is one of these issues, that receives more and more attentions recently. It has been widely used in real applications such as image segmentation and spam filtering. Many methods have been proposed to process the issues. However, few of them can process large signed graphs which become common in practice. This paper proposes a novel algorithm based on the drop of water principle to tackle the problem of clustering large scale signed graphs. The algorithm is constructed according to the following procedures. Firstly, the signed graphs are shrank based on the drop of water principle. The points within a stream can be taken as a new point in the graph, the scale of signed graphs can be enormously decreased in this procedure. Secondly, some important points are chosen as seeds, and based on integer linear programming, the seeds can decide whether the neighbors joint the seeds or not. The experimental results show that the proposed method can cluster large scale graphs effectively and efficiently.

Key words: drop of water principle, signed graphs, correlation clustering, integer linear programming