基于标签传播的社团检测算法研究

发布时间：2017-10-08 06:14

  本文关键词：基于标签传播的社团检测算法研究

  更多相关文章： 复杂网络 社团检测 归属度 节点相异性 节点相似性

【摘要】：近年来,随着互联网和计算机技术的快速发展,以社会关系网络、生物信息网络、语义Web网络等为代表的复杂网络迅速兴起,复杂网络的相关研究也得到了学术界和工业界的广泛关注。社团是复杂网络的重要特性,代表着网络中具有一定关系对象的集合。社团内部的节点之间连接紧密,不同社团节点之间连接相对稀疏。通过对复杂网络中社团结构的研究,可以得出复杂网络的功能、拓扑结构和性质等信息,这对于了解网络结构,充分发挥网络价值都很重要。社团检测就是利用复杂网络中已知的节点属性信息、节点连接关系信息以及拓扑结构信息等来发现网络中特定群体的潜在规律,进而挖掘其潜在价值。当前大部分的社团检测算法都是基于网络拓扑结构展开的,这类算法普遍存在着准确率低、时间复杂度高及聚类因素单一等不足。标签传播算法是常见的基于网络拓扑的社团检测算法,具有快速、简单、高效的特点,但也存在随机性、准确性和鲁棒性的不足。针对上述问题,本文综合考虑节点属性信息以及图的拓扑结构信息,提出了两种新的改进的基于标签传播的社团检测算法。首先,基于节点归属度的标签传播社团检测算法。该算法首先从未被分类的节点中选择一个度数最大且聚类系数符合条件的节点及其邻居节点作为初始社团,然后根据节点归属度吸引它的邻居节点加入,形成大致社团结构,最后运用标签传播算法思想进行完善,得出最终的社团结构。基于节点归属度的标签传播社团检测算法适用于中小规模网络,时间复杂度低,且能够准确的检测出复杂网络中的社团结构。其次,针对上述方法在顶点数量多,边数密集的复杂网络中社团检测准确性不足的情况,提出了基于节点相异性的标签传播社团检测算法。该算法首先通过节点度数、节点聚类系数和节点相异性进行核心点集合选取,然后从核心点集合中选择核心点,根据节点相似性公式,将符合条件的邻居节点加入到相应社团,形成大致社团结构,最后根据多数投票原则修改节点标签,以获得最后准确的社团结构。基于节点相异性的标签传播社团检测算法充分考虑了各节点间的直接联系和间接联系,使社团的检测效果更加完善,准确性得到了进一步的提升。最后,针对上述社团检测方法,本文运用大量实验进行了验证。通过对检测出的社团结构的有效性和社团检测的执行效率进行测试,充分验证了本文社团检测方法的可行性和优越性。
【关键词】：复杂网络 社团检测 归属度 节点相异性 节点相似性
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-6
• Abstract6-12
• 第1章 绪论12-17
• 1.1 研究背景与意义12-13
• 1.2 问题的提出13-15
• 1.3 研究内容15
• 1.4 本文组织结构15-17
• 第2章 相关技术17-28
• 2.1 社团检测相关概念17-19
• 2.1.1 复杂网络17-18
• 2.1.2 社团18
• 2.1.3 社团检测18-19
• 2.2 社团检测算法19-23
• 2.2.1 非重叠社团检测算法19-22
• 2.2.2 重叠社团检测方法22-23
• 2.3 社团检测质量评价标准23-27
• 2.3.1 模块度24
• 2.3.2 划分精度24-25
• 2.3.3 标准互25-27
• 2.4 本章小结27-28
• 第3章 基于节点归属度的标签传播社团检测算法28-38
• 3.1 相关概念28-31
• 3.1.1 节点归属度28-29
• 3.1.2 节点聚类系数29-31
• 3.2 社团检测算法31-37
• 3.2.1 构建大致社团结构31-35
• 3.2.2 完善大致社团结构35-37
• 3.3 算法时间复杂度分析37
• 3.4 本章小结37-38
• 第4章 基于节点相异性的标签传播社团检测算法38-50
• 4.1 相关概念38-42
• 4.1.1 最短路径38-39
• 4.1.2 节点相异性39-40
• 4.1.3 节点相似性40-42
• 4.2 社团检测算法42-48
• 4.2.1 核心点集合选取42-44
• 4.2.2 构建大致社团结构44-47
• 4.2.3 完善大致社团结构47-48
• 4.3 算法时间复杂度分析48
• 4.4 本章小结48-50
• 第5章 实验与分析50-55
• 5.1 实验环境与设计50-51
• 5.1.1 实验环境配置50
• 5.1.2 实验数据集介绍50-51
• 5.2 实验分析51-54
• 5.2.1 评价标准51
• 5.2.2 性能测试与分析51-54
• 5.3 本章小结54-55
• 第6章 总结与展望55-57
• 6.1 总结55
• 6.2 展望55-57
• 致谢57-58
• 参考文献58-62
• 攻读学位期间发表的学术论文及参加科研情况62-63

【参考文献】

中国期刊全文数据库 前2条

1 于戈;谷峪;鲍玉斌;王志刚;;云计算环境下的大规模图数据处理技术[J];计算机学报;2011年10期

2 武志昊;林友芳;Steve Gregory;万怀宇School of Computer and Information Technology,Beijing Jiaotong University;田盛丰;;Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J];Journal of Computer Science & Technology;2012年03期

，

本文编号：992437