论文部分内容阅读
复杂网络的社团结构,是复杂网络最普遍和最重要的拓扑属性之一,它具有社团内节点连接紧密、社团间节点连接稀疏的特点。发现复杂网络的社团结构,对复杂网络拓扑结构特点的认识、复杂网络功能模块的理解、节点间隐藏关系的分析以及复杂网络行为的预测都具有十分重要的作用。虽然目前已提出了很多复杂网络聚类方法,但如何进一步提高聚类精度,特别是在社团个数等先验知识未知的情况下如何发现合理的社团结构,如何快速完成大规模复杂网络的社团结构发现,都是极具挑战性的研究问题。蚁群聚类算法作为一种群集智能算法,通过模拟将蚂蚁尸体堆积成蚂蚁墓的行为,使蚂蚁所代表的数据动态、自组织地形成聚类。它具有快速高效、聚类质量好、无需先验知识等优点,较适合解决高维、复杂的聚类问题。借鉴蚁群聚类算法的思想,本文结合中小型和大规模复杂网络的特点,进行了如下工作:(1)将适应度局部感知和信息素扩散机制相结合,提出了一种发现复杂网络社团结构的蚁群聚类算法。新算法利用蚂蚁代表网络中的节点,初始时,将所有蚂蚁随机分布在二维网格中的不同位置。在进化过程中,蚂蚁通过适应度函数感知所处的生存环境,并决定自己是移动到一个新位置还是留在原位置保持不动。每一代移动完毕后会形成一个聚类结果,这个结果的质量会影响到节点信息素的更新,同时为了反映信息素扩散的特性,我们在信息素更新中引入了信息素扩散模型。进化过程不断重复,直到所有蚂蚁都找到了最舒适的位置为止,这时复杂网络的社团结构会在网格上凸现出来。在通用数据集上与一些经典算法的实验对比表明,新算法具有较好的聚类效果。(2)针对现实社会中复杂网络规模不断扩大、但聚类方法速度较慢的矛盾,提出了基于抽样的蚁群聚类算法来发现大规模复杂网络社团结构。新算法首先通过对网络节点的抽样,降低问题求解的规模;其次,利用上一工作提出的蚁群聚类算法对样本节点聚类,并融入标签传播的思想标记样本节点;再次,根据节点与社团的相似度,将非样本节点指派到已检测到的社团中;最后以模块度函数值为指标,对初始聚类结果进行合并修正。在通用数据集上进行的实验测试表明:新算法不仅能大大提高社团结构的发现速度,而且具有平衡获得高质量解和运行效率的能力。