蛋白质复合物是由多个蛋白质相互结合在一起的组织。生命活动由这些复合物来推动,因此研究蛋白质复合物的具体作用在生物领域具有非常重要的意义。然而,目前的生命科学领域在对这些复合物的识别需要相当大的时间成本和机器成本。由于现在拥有丰富的蛋白质相互作用网络,复合物可以看成是该网络上的社区。在相互作用网络上使用数据挖掘中社区发现的一些算法能够辅助识别这些复合物,以达到减少成本的目的。因此,基于蛋白质相互作用网络的复合物识别是一项有意义的研究课题。现有的蛋白质复合物识别算法一般基于图的网络拓扑结构,结合子图挖掘或者特征学习等数据挖掘方法来识别这些复合物。但是这些算法往往很难完全考虑到蛋白质复合物的复杂性。有些算法只能考虑图密集区域的复合物而忽视稀疏区域的复合物,有些算法容易遗失部分复合物中的蛋白质或者产生冗余的蛋白质。因此,本文基于前人研究的这些缺陷,提出了两个更有效识别蛋白质复合物的算法:第一个算法基于基本的寻找初始聚类再向外扩张的思想。为了得到有效的初始聚类,基于重启型随机游走能够得到一个网络图中所有节点之间的相关联程度,本算法将那些与某个节点联系紧密的节点组合成一个初始聚类,并对这些初始聚类进行去冗余操作形成真正的初始聚类。然后从这些初始聚类出发向外扩张成最后的复合物。在这个过程中,为了解决蛋白质复合物中的某些特殊边缘蛋白质,本文结合其他扩张公式的优缺点,提出新的容易控制聚类大小的有益密度扩张公式比较方法。同时在扩张后的复合物基础上,过于相似的会合并在一起,但是会保留某些特殊的复合物。第二个算法同样基于初始聚类扩张的思想,基于重启型随机游走的结果,通过特定阈值的设计形成有一定规模的初始聚类,本算法认为某些区域内的最大的初始聚类一定程度上可视为这一部分的中心区域,将其他有相似节点的初始聚类都删去作为去冗余操作。最终得到一些互相正交的有代表性的真正初始聚类。在此过程中会产生很多剩余节点。由于重启型随机游走的结果节点之间的关联程度是一定的,因此可以根据这些剩余节点到真正初始聚类内所有节点的平均关联程度的大小来分配这些剩余节点以得到最终的复合物结果。实验在几个著名的酵母细菌蛋白质相互作用网络上进行,本文提出的两个算法都表现出了较好的复合物识别能力。