论文部分内容阅读
现实中存在的很多复杂系统例如因特网、生物网络和社会网络等都可以建模为包含一些节点和其连接关系的网络。对这些网络拓扑关系的研究有助于我们发现一些不容易直接察觉到的网络构造特征,进而更深入地了解网络特性比如节点之间的相似性或者系统的组织方式。社区发现就是一种典型的网络拓扑关系聚类分析方法,通过社区发现算法对网络进行划分可以发现网络中节点之间的隐藏关系、分析信息流以及深入了解系统的组织和功能,社区发现的结果可以作为进一步数据挖掘工作的基础。综上所述对社区发现算法的深入研究是具有一定现实意义的。前人已经在社区发现算法的各个研究领域做过许多工作,然而已有算法还存在一些问题,比如已有局部社区发现算法准确率较低,已有全局重叠社区发现算法时间复杂度较高、准确度低和缺乏判断条件,现有相关矩阵社区发现算法没有考虑个体之间存在多种相关性关系等。考虑到已有算法存在上述不足之处,本文提出了几种改进算法。本文主要工作包括:针对已有局部社区发现算法存在初始点选取鲁棒性差等问题,本文提出了一种基于最大熵随机游走的两阶段局部社区发现算法。改进算法首先对于初始节点一定范围内的子图进行粗搜索,得到一些与初始节点关系较为密切的节点作为种子节点,然后以多个种子节点作为源节点进行局部社区发现细搜索。这样的两阶段算法一定程度上解决了已有局部社区发现算法存在的问题。改进算法的明显优势在于利用最大熵随机游走提高了种子选取的效率,而且在细搜索中引入了随机因素,提高了算法解的质量。仿真结果表明,本文基于最大熵随机游走的两阶段局部社区发现算法提高了已有算法的社区发现准确率。针对传统全局重叠社区发现算法时间复杂度较高,且已有基于种子的算法初始点选取不灵活和缺乏后处理步骤等问题,本文提出了一种利用局部核心扩展的并行社区发现算法,该算法包括网络的初始化过滤、局部核心搜索、局部核心扩展和局部社区后处理等步骤。改进算法通过初始过滤避免了后续的无用处理,通过局部核心搜索使得初始种子选取更加均匀而且数量自动适应网络规模,通过局部核心扩展和后处理使得改进算法能较为精确的找到重叠社区。改进算法还建立了全局模块度和局部模块度的相互联系,在此基础上给出了一个重叠点添加的准入条件。仿真结果表明,改进算法的社区发现准确率和质量优于已有算法。考虑到个体之间存在多种行为相关性,本文提出了一种基于多关系相关矩阵的社区发现算法。改进算法首先利用随机矩阵理论滤除相关矩阵的随机噪声,然后利用基于模块度的社区发现算法对单一相关矩阵进行社区发现得到社区数目,最后对多关系相关矩阵进行特征抽取,然后利用矩阵分解和聚类算法进行社区发现。改进算法利用随机矩阵理论使得对相关矩阵的社区发现是无偏的,又考虑了个体之间存在多种行为相关性使得社区发现结果更加接近真实划分。仿真结果表明改进算法使得相关矩阵社区发现准确率得到提升。