Abstract: Relational data can be abstracted as networks, and little background knowledge of these real networks is known in most cases. To evaluate the performance of graph clustering algorithms on real networks, a near-realistic network model is constructed. It infers the ability of a graph clustering algorithm to analyze real networks through its performance on model networks. To ensure rationality of this inference, the constructed model network has the same first-order statistical properties as the network under investigated. Meanwhile, the constructed model network can have any given community structure. It is equivalent to give the background knowledge, that is, the real classification information is known. An illustration example shows that the constructed model provides a way to evaluate graph clustering algorithms objectively.

Key words: data mining, graph clustering, cluster evaluation model

摘要： 关系数据可抽象为网络，在通常情况下，缺乏对这些现实网络背景知识的了解。为了评价图聚类算法在现实网络上的性能表现，构建了一种接近现实的网络模型，通过算法在模型网络上的性能表现来推断其分析现实网络的能力。为了确保此推断的合理性，构建的模型网络具有与所研究网络完全相同的一阶统计特征。同时，构建的模型网络可具有任意设定的集团结构，这就相当于给定了背景知识，即真实的分类信息是已知的。实例说明，构建的模型为客观评价图聚类算法提供了一条途径。

关键词: 数据挖掘, 图聚类, 聚类评价模型