基于不确定图的层次聚类算法研究

李俊辉

[摘要] 传统的基于图论的层次聚类算法都是对确定图进行分割，然而实际中，很多网络的图结构都是不确定的，边是以概率存在的。因此，本文提出了基于不确定有向加权图的层次聚类算法。该算法首先求出不确定图的可能强连通子图作为聚类中心，再对剩余节点进行层次聚类。算法主要考虑边的权重和存在概率。最后以一个例子说明算法的流程。

[关键词] 不确定图； 有向加权图； 聚类中心； 层次聚类

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 24. 048

[中图分类号]TP311[文献标识码]A[文章编号]1673 - 0194（2012）24- 0079- 02

图的聚类算法是从节点开始的，一般的过程是：先是把图中的每一个节点都初始化成一个子图，图中有多少节点，就形成多少子图，设计一种子图间相似度或距离计算方法，定义子图之间的相似度或距离，以及凝聚过程的结束条件[1]。首先计算每个子图对之间的相似度，合并相似度最高，距离最近的子图成一个新的子图，再重新计算所有子图对之间的相似度或者距离数值，将此过程不断重复，直到达到过程结束条件，最终得出整个图的层次结构。聚类结果可以用树状图来表示，这种方式可以清晰看出各种不同需求下得到的划分结果。

主要的层次聚类算法包括Girvan和Newman[2]提出的基于边的介数的聚类算法，Newman[3]为解决大规模网络提出的快速算法，以及CURE算法[4]和Chameleon算法[5]等，近年来，许多研究者改进了传统的层次聚类算法。例如，王小黎[6]等对相似度度量和时间复杂度进行改进，提出了基于相异度度量的凝聚聚类方法，采用曼哈坦距离作为节点相似性度量，并且证明了该方法的有效性。……