基于SCAN算法的社区发现算法研究

发布时间：2017-08-20 21:33

  本文关键词：基于SCAN算法的社区发现算法研究

  更多相关文章： 社区发现 重叠节点 动态网络 结构相似度

【摘要】：社区发现是复杂网络研究领域的一个重要的研究方向。一个网络由若干社区组成,每个社区在内部节点之间联系相对紧密,在外部社区之间的联系相对稀疏。SCAN算法是近年来涌现出来的社区发现算法中比较优秀的算法,它是一种基于结构聚类的算法,这也是它名字的由来(Structural Clustering Algorithm for Networks)。它的优秀表现在线性的时间复杂度,精准的划分结果,并且可以识别社区结构之外的信息(枢纽节点和孤立节点)。虽然SCAN算法有很多的优势,但是缺陷也是很明显的。SCAN不能识别重叠社区,而社区的重叠现象是广泛存在于网络中的；由于在线社交网络的发展,网络结构的演进变化大大快于从前,能够动态地分析网络得出社区结构应该是研究的大趋势,而SCAN算法缺乏这方面的能力。另外,SCAN算法需要人工设置两个参数并且算法的精确度严重依赖参数的选择。结合以上内容,本文在SCAN算法的基础上改进扩展出两个算法,具体研究成果如下：(1) SCAN算法优化改进SCAN算法包含两个参数：ε和μ,我们主要对参数进行优化,一是参数的约减,二是降低算法对于参数的敏感度。首先,我们只保留了参数￡用于限定核心网络,并且采用一个循环删边的操作降低算法对于这个参数的依赖,使得阈值α在很大的选择范围内算法都能得到令人满意的社区划分结果。(2) SCAN算法功能扩展本文对SCAN算法进行重叠节点识别的扩展,提出了LED算法。循环删边过程促使社区分裂,在分裂的时候被删除的边的两个节点就是社区边缘的节点,是我们重叠节点检查的对象。我们采用社区平均度作为重叠节点的识别标准,在删除的边的节点中识别重叠节点。在LED算法的基础上扩充对于动态网络的处理能力,算法分为线上线下两个部分。线上部分保存网络数据和部分中间计算结果,并且根据网络的变化,分析出最大影响区域,在影响区域内局部更新网络数据和中间计算结果,从而最大限度的降低重复计算。线下部分负责从线上部分维护的数据中抽取社区结构,识别重叠节点。
【关键词】：社区发现 重叠节点 动态网络 结构相似度
【学位授予单位】：南京信息工程大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要5-7
• Abstract7-9
• 第一章 绪论9-18
• 1.1 研究背景及意义9-12
• 1.2 国内外相关研究与应用现状12-15
• 1.2.1 传统社区发现算法研究现状12-13
• 1.2.2 重叠社区的社区发现算法研究现状13-14
• 1.2.3 动态网络社区发现算法研究现状14-15
• 1.3 研究内容15-17
• 1.4 论文内容的组织17-18
• 第二章 社区发现理论算法和SCAN算法18-28
• 2.1 相关理论18-22
• 2.1.1 社交网络18
• 2.1.2 社区结构18
• 2.1.3 距离与相似度度量18-20
• 2.1.4 模块度Q20
• 2.1.5 人工合成网络20-22
• 2.2 SCAN算法22-27
• 2.2.1 结构连接聚类相关定义22-25
• 2.2.2 SCAN算法25-27
• 2.2.3 存在不足27
• 2.3 本章小结27-28
• 第三章 基于SCAN的重叠社区发现算法28-47
• 3.1 LED算法基础28-33
• 3.1.1 结构相似度28-29
• 3.1.2 循环删边操作29-32
• 3.1.3 重叠节点检测32-33
• 3.2 LED算法33-34
• 3.3 时间复杂度分析34-35
• 3.4 参数选取研究35-37
• 3.5 实验37-46
• 3.5.1 效率37-39
• 3.5.2 效果39-46
• 3.6 本章小结46-47
• 第四章 基于SCAN的动态社区发现算法47-58
• 4.1 研究背景47
• 4.2 LEDD算法47-52
• 4.2.1 影响区域47-49
• 4.2.2 LEDD算法描述49-52
• 4.3 时间复杂度分析52
• 4.4 实验52-57
• 4.4.1 人工生成网络52-54
• 4.4.2 真实网络54-57
• 4.5 本章小结57-58
• 第五章 结束语58-60
• 5.1 总结58-59
• 5.2 展望59-60
• 致谢60-61
• 参考文献61-64
• 作者简介64

，

本文编号：709018