基于节点相似度的社团结构检测算法研究

发布时间：2017-10-12 08:38

  本文关键词：基于节点相似度的社团结构检测算法研究

  更多相关文章： 社团结构检测 节点相似度 线性阶时间复杂度 算法稳定

【摘要】：针对目前社团结构检测算法计算量大,准确度低以及算法结果不稳定的问题,在经典Newman快速算法与LPAm算法的基础之上,各取它们的优点相结合,提出了一种基于局部信息的社团检测新算法。算法利用节点度和共享邻居数定义节点相似度,首先根据节点相似度和一个预设节点相似度阈值将网络划分为初始的社团结构,然后依据另一个预设社团数目参数阈值进一步优化社团结构,最后得到精确度较高的社团划分结果。性能分析证明,该算法有着近似线性的时间复杂度。实验结果表明,本文提出的算法相对于GN算法,Newman快速算法和LPAm算法有着更高的准确度,且它是一种结果稳定的算法,对于大型网络的社团结构预测,有着较好的效果,因此,有着较好的实用性。
【关键词】：社团结构检测 节点相似度 线性阶时间复杂度 算法稳定
【学位授予单位】：辽宁工程技术大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 致谢4-5
• 摘要5-6
• Abstract6-9
• 1 绪论9-21
• 1.1 课题研究的背景和意义9-12
• 1.2 国内外研究现状12-17
• 1.3 社团结构检测经典测试网络17-19
• 1.4 本文的主要工作19-21
• 1.4.1 本文的研究内容19-20
• 1.4.2 本文的结构安排20-21
• 2 社团结构检测基本概念与主要算法21-36
• 2.1 复杂网络基本概念21-23
• 2.1.1 网络图表示与度分布21-22
• 2.1.2 网络的平均最短路径与网络顶点的介数22-23
• 2.1.3 网络的簇系数23
• 2.2 社团结构检测基本概念23-27
• 2.2.1 节点相似度与模块度Q23-25
• 2.2.2 社团结构划分质量评价标准25-27
• 2.3 社团结构检测主要算法27-35
• 2.3.1 Kernighan-Lin算法27-28
• 2.3.2 普评分法28-29
• 2.3.3 GN算法29-30
• 2.3.4 Newman快速算法30-32
• 2.3.5 标签传播算法32-35
• 2.4 本章小结35-36
• 3 基于节点相似度的社团结构检测算法36-42
• 3.1 算法思想来源36-38
• 3.2 算法描述38-40
• 3.3 算法分析40-41
• 3.4 本章小结41-42
• 4 基于节点相似度的社团结构检测算法实现42-49
• 4.1 基于节点相似度的社团结构检测算法实验设计42-44
• 4.1.1 节点相似度阈值的选取42-43
• 4.1.2 最小社团节点数的选取43-44
• 4.2 基于节点相似度的社团结构检测算法实验结果与分析44-48
• 4.3 本章小结48-49
• 结论49-50
• 参考文献50-54
• 作者简历54-56
• 学位论文数据集56

【参考文献】

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

1 牛建伟;戴彬;童超;霍冠英;彭井;;基于Laplace矩阵Jordan型的复杂网络聚类算法[J];通信学报;2014年03期

2 徐杨;蒙祖强;;基于GN算法的微博社区识别方法[J];广西大学学报(自然科学版);2013年06期

3 李木梓;徐柱;李志林;张红;怓鹏;;基于层次随机图的道路选取方法[J];地球信息科学学报;2012年06期

4 蔡泽祥;王星华;任晓娜;;复杂网络理论及其在电力系统中的应用研究综述[J];电网技术;2012年11期

5 林超;曾小清;董德存;;小世界网络理论在公交线网中的优化方法研究[J];交通科技;2012年02期

6 姜雅文;贾彩燕;于剑;;基于节点相似度的网络社团检测算法研究[J];计算机科学;2011年07期

7 张翼;刘玉华;许凯华;骆珍荣;;一种基于互信息的复杂网络节点重要性评估方法[J];计算机科学;2011年06期

8 王银年;葛洪伟;;求解TSP问题的改进模拟退火遗传算法[J];计算机工程与应用;2010年05期

9 赵凤霞;谢福鼎;;基于K-means聚类算法的复杂网络社团发现新方法[J];计算机应用研究;2009年06期

10 杨博;刘大有;金弟;马海宾;;复杂网络聚类方法[J];软件学报;2009年01期

，

本文编号：1017743