Abstract: The time cost of traditional clustering algorithm is too high when using it to large scale information network. To solve this issue, based on the statistical characteristic of information network, this paper proposes a novel “divide and conquer” strategy on information network, which reduces the clustering size and time cost heavily without efficiency loss. The main contribution of this paper is three folds: (1) It proposes the idea that clustering in different layers separately after dividing the whole information network into several layers according to the clustering contribution rank; (2) Based on the rich-club phenomenon and hierarchical community feature which exists in information network, it designs the blueprint of layer dividing method of clustering algorithm; (3) It presents an iteration procedure to merge clusters in different layers. The experimental results show that the proposed algorithm has good clustering effect and can reduce time cost.

Key words: information network, adaptive clustering (AC), information layer

摘要： 为解决传统聚类算法在处理大规模信息网络中时间开销过大的问题，基于大规模信息网络的统计学特性，提出了一种将信息网络拓扑结构进行“分而治之”的思想，有效地减少了聚类问题规模和时间开销，并保持了相当的聚类效果。主要贡献包括：提出按照聚类影响力排名来对整个信息网络进行分层切割，然后分别聚类的思想；按照特定信息网络统计学意义上的结构特性，如信息网络的富人集团特性和分层社区结构特性，设计了一套将信息网络进行层次划分的粗略方案，并通过实验证明了其具有一定的合理性；提出了迭代的层级间聚类融合算法，可以实现不同层次聚类的融合。实验表明，该算法在兼具较好聚类效果的同时，非常明显地减少了运算开销。

关键词: 信息网络, 自适应聚类, 信息层