基于种子节点扩展的重叠社区发现方法的研究

发布时间：2020-08-21 08:22

【摘要】：现实生活中的许多复杂互联的系统可以被抽象为网络结构,通过这种抽象,我们可以更好的研究和分析这些系统。社区发现对了解整个网络的结构与特性具有重要意义,并且已经在许多的领域广泛应用。社区的重叠性质被认为是社区的重要特性,以往的非重叠社区发现已经难以满足当前应用的场景,重叠社区发现成为新的研究热点。传统的社区发现算法研究的内容是非重叠社区,对重叠社区发现算法的研究仍有许多的不足之处,因此发现网络中的重叠社区结构往往具有更加实际的意义。社区可检测性研究的是“社区能否检测”的问题。社区可检测性研究是社区发现算法的一个前提工作,现有的社区可检测性方法一般是在均匀社区的前提下工作的。针对非均匀条件下的社区可检测性的问题,本文提出了一种基于SBM的社区可检测性方法。该方法通过随机块模型(SBM)对网络进行建模,引入贝叶斯推论对参数模型进行分析,利用自由能理论的固定点确定模型参数状态变化,结合BP算法对模型参数进行迭代计算,得到最终的社区可检测性结果。通过仿真实验的进一步验证,本文提出的社区可检测性方法在非均匀社区的条件下可以完成社区可检测性的工作。社区发现算法研究的是“社区如何检测”的问题。随着重叠社区发现研究的不断深入,许多重叠社区发现算法已经被提出。但现有的算法仍然存在计算复杂度高和准确率低的问题。针对这些问题,本文提出了一种基于种子节点扩展的重叠社区发现算法(OCDSE)。本文通过对大量现实网络数据集的分析,发现网络中存在大量的边缘须图结构,这种结构不参与重叠社区发现,事先将这种结构排除可以有效的提高重叠社区发现的效率;另外,本文重点研究了节点重要性,以节点度数为基础,选取具有良好分布特性的节点作为种子节点,结合PPR算法对种子节点进行扩展,完成核心重叠社区发现;最后,通过传播算法将剔除的边缘须图结构重新加入。通过实验对比,此方法在准确性和效率上比起其他的重叠社区发现算法都有明显的提升。
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6

【参考文献】