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

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