图聚类算法在现实网络中的性能分析

图聚类算法在现实网络中的性能分析

1图聚类算法的评价标准聚类分析是研究关系数据组织和结构的重要手段。将研究的数据对象划分为“自然”组后，使集团内成员的相似性（或关系度）更高，不同集团的相似性较低。图聚类方法是一类非常重要的聚类方法,近年来吸引了广泛关注,这是因为:首先是待研究对象间的相互关系可以表示为图,一般的聚类问题常常可转化为图聚类问题;其次是复杂网络,特别是复杂生物网络研究兴趣的急速增长,并且随着基因组学研究和高通量技术的飞速进步,大量生命系统组成元件以及它们之间相互关系数据的迅速积累为分析复杂生物网络奠定了基础,这些现状对图聚类方法提出了新的要求。多种基于不同优化准则的图聚类算法被提出,其中较为流行的有:基于模块性(Modularity)的图聚类算法、基于规范割(Normalizedcut)的图聚类算法、基于最小割(Minimumcut)的图聚类算法等。实际上,不存在一个统一的标准来评价这些图聚类算法的优劣。在实际应用中,对于同一个研究对象,不同的图聚类算法可能产生不同的聚类结果。这就要求对这些算法进行比较分析,并且评价哪个算法得到的聚类结果更具可靠性。最佳的标准是,看哪个算法得到的结果更能发现隐蔽的知识。例如,对复杂生物网络聚类分析时,看哪个算法从数据出发能挖掘新的生物学知识或找到某些生物学问题的明确答案,比如,能够预测某个蛋白质的功能,能够鉴定某个微生物所属的种属,能够获得某个代谢途径等。但是,这种基于生物学的评价方式非常困难。因为,聚类作为一种探索性的知识发现的重要手段,其结果是预测性的,而现有的生物学知识还非常不完备,很难从理论上给予证明;同时,在实验方面,现有的生物分析信息检测技术也存在很大局限性,很难验证预测结果的正确与否。最理想的情况是,对研究问题的背景知识充分了解,即数据的真实分类信息是已知的,这时只要分析算法得到的聚类结果与真实分类信息的一致性,就可以知道在对这个研究对象分析时哪个算法更优,但是,在大多数情况下很难得到可靠的真实分类信息。基于上述原因,本文提出的对图聚类算法进行评价的思路是通过算法在模型网络上的性能表现来推断其分析现实网络的能力。为了使这样的推断较为合理,构建的模型网络当然应该与所研究的对象有相同的重要特征;同时为了便于对聚类结果进行统计分析,构建的模型网络应该具有可任意给定的集团结构。因此,构建了一种接近现实的网络模型(near-realisticnetworkmodel,简称NR模型),模型网络中每个节点的度与所研究网络中相应节点的度完全一致,且模型网络的集团结构是可控的。构建的NR模型为客观地评价图聚类算法在分析某个研究对象时的性能表现提供了一条途径。2网络模型的构建借助于算法在模型网络上的性能表现,能够推断其分析现实网络的能力,但前提是构建的模型网络具有所研究的现实网络的某些重要特征。复杂网络的度分布作为一阶拓扑性质,与网络的许多重要特性紧密相关。例如,许多实际的复杂网络度分布具有幂律(Power-law)形式,由于幂律分布没有明显的特征尺度,即该类网络是无标度(Scale-free)的,正是这种无标度的拓扑组织方式增加了系统的稳健性,使得整个网络在部分组件出现问题或者环境改变甚至遭受外来袭击时,能够最大可能地保持稳定性。因此,在构建模型时,使模型网络中所有节点的度与所研究网络的相应节点的度完全一致。同时,构建的网络模型的集团结构应该是事先给定的且可控的。具体的构建过程如下:(1)对于研究的网络,为每个节点随机分配一个类别号,或者以其他规则来使每个节点有一个类别号。这就相当于为研究的网络赋予了集团结构,记此时的网络为Net0。(2)从Net0中随机挑出两条边,在保证节点的度不变的前提下,以一定的概率重搭这两条边,具体的实施方案见图1。如图1(a)所示,定义了两类边,属于同一集团的两个节点所连的边称为有利的边(Favoredlinks),来自不同集团的两个节点所连的边称为不利的边(Unfavoredlinks)。图1(b)详细地描述了所有可能出现的重搭情况。第一列表示从Net0中随机挑选的一对边,根据边的颜色可以判断出每条边对应的两个节点是否属于同一集团;第一行表示对于随机选择的一对边,经过重搭后可能出现的三种连接情况。以随机挑选的一对边属于同一个集团(图中第2行第1列)为例,具体说明对重搭后可能出现的每种情况的处理策略。如果重搭后这两条边仍然处于同一个集团(图中第1行第2列),以概率1实现此次重搭;重搭后只有一条边位于集团间(图中第1行第3列),这种情况是不可能出现的;如果重搭后这两条边都处于集团间(图中第1行第4列),则以概率β2实施此次重搭。用数学式子来表示就是,重搭概率为:其中k表示由于重搭导致的集团间的边增加的条数。从上式可以看出,β越大,重搭的概率就越大,则模型的集团结构变得越来越模糊。也就是说,参数β控制了模型的集团结构的强度。重搭的次数由人为设定。这样,建立一个具有可控集团结构的网络模型,且该模型中所有节点的度与要研究网络的节点的度完全相等。3示例模型的使用3.1数据预处理阶段假定待研究的对象是酵母蛋白相互作用网络,这也是NR模型建立的基础。相互作用数据来源于DIP数据库()。在数据的预处理阶段,去除了自相互作用和冗余的相互作用。原始的网络包含4963个节点,这些节点属于34个独立的分支,其中最大的分支(巨分支)含有4902个节点,去除这个巨分支的叶子节点,最终得到的网络包含了3700个酵母蛋白的16044个相互作用。该网络用无向图G(V,E)来表示,其中节点集合V={P1,P2,…,Pn},包含了每个蛋白作为节点,边集合E={(Pi,Pj)|蛋白Pi和Pj间具有相互作用}。对称的n维邻接矩阵用A表示,且3.2谱聚类算法本文涉及的两个图聚类算法是谱聚类算法(Spectralclustering)和CD算法,这两个算法优化的目标函数是不同的。下面对这两个算法做简要介绍。这里使用的谱聚类算法分成以下4个步骤来执行:(1)由数据集建立邻接矩阵A,再求得A的拉普拉斯矩阵L。(2)计算L的前k个最大的特征值机对应的本征向量。(3)将原始数据映射到由k个正交向量所撑成的空间Rk。(4)利用k均值算法或其他聚类算法在Rk空间上进行聚类。CD算法是作者开发的一种基于模块性优化的图聚类,其算法流程如下:(初始化)1.随机分配所有节点到cmax个集团中;在上面的算法流程中,NITER表示整个收缩和膨胀过程迭代的次数,表示使Δiα取最大值的变量α。3.3c中第k个集团所含的成员的编码为了量化模型的集团结构C与算法应用于模型网络得到的聚类结果C′之间的符合程度,定义了C与C′的符合率(CoincidenceRate,CR)。用nc和nc′分别表示C和C′中非空集团的个数,Ck表示C中第k个集团包含的成员,C′k′表示C′中第k′个集团包含的成员,定义混淆矩阵M,它的元素Mkk′=|Ck∩C′k′|表示既在Ck中又在C′k′中的成员的数目。显然,C中的每个集团都能在C′中找到匹配最好的集团。矩阵M中最大元素的Mab表示C中的集团a与C′中的集团b的是最好的匹配,依次类推,矩阵M中不位于第a行第b列的第二大的元素表示另两个集团的最好匹配。用match(k)表示C′中的第k′个集团与C中的第k个集团相匹配的编号,n表示数据集中成员(本文中为蛋白质)的数目,则符合率CR被定义为:当C与C′完全相同时,CR取到最大值1;当C与C′完全不同时,CR取到最小值0。3.4模型网络的集团结构对于3.1节构建的酵母蛋白质相互作用网络,假设其可以划分为15个集团,则为每个节点分配一个1到15的整数作为类别号,这样就生成了模型网络Net0。为了能清楚观察到网络的集团结构,对邻接矩阵A中的节点按类别进行重排,即将属于同一个集团的节点移动到相邻的位置。图2显示了重排后的矩阵A,图中的每个小方块代表一个集团,记此时的模型网络为Net1。图3(a)～(d)显示的是对Net1进行边重搭后的四个模型网络的例子,它们对应的参数β的取值分别为0.01,0.05,0.1和0.3。从图中可以看出,随着β增大,模型网络的集团结构越来越模糊。当β=0.3时,由于集团间边的数目增多,集团结构已经较难辨识。3.5实验结果和讨论为了评价谱聚类算法和CD算法在3.1节构建的质酵母蛋白相互作用网络上的性能表现(假定事先不知道关于此网络的任何背景知识),以此网络为基础构建NR模型,通过比较算法在模型上的性能表现来推断它们分析此酵母蛋白相互作用网络时的优劣。在本文实验中,所有的模型网络都是通过重搭50m(m是所研究网络的边数)次后得到的,也就是说,每条边平均重搭了100次。将谱聚类算法和CD算法应用于通过第2章的规则构建的NR模型网络。最初的没有经过边重搭的模型网络为Net1,此时对应的参数β的取值为0。在Net1的基础上,通过边重搭策略,构建了一组含有不同强度集团结构的模型网络,对应的参数β的取值范围是0到0.4(见图3)。图4总结了谱聚类算法和CD算法在这组模型网络上的性能表现。图中的每个数据点是算法应用于具有相同参数的50个模型网络后得到的实验结果的平均值,误差条是标准差。从图中可以看出,CD算法应用于这组模型网络得到的聚类结果始终与模型设定的划分的符合度较高,而此模型网络中所有节点的度与3.1节构建的酵母蛋白质相互作用网络中所有节点的