基于节点重要性的复杂网络社团挖掘算法研究

发布时间：2017-08-15 01:18

  本文关键词：基于节点重要性的复杂网络社团挖掘算法研究

  更多相关文章： 复杂网络 社团挖掘 重要节点 蛋白质相互作用网络

【摘要】：复杂网络在现实世界中普遍存在,社团结构是网络的一个重要拓扑特征。社团结构的挖掘已成为复杂网络学科下的热点研究方向,对理解分析网络功能与性质,发现网络中的隐藏规律以及预测网络行为等方面至关重要,具有重要理论研究意义和应用价值。近年来,越来越多的社团结构挖掘算法相继被提出,而面对扩大的网络规模,社团挖掘结果常受初始节点位置影响、需事先指定社团规模大小、时间复杂度高等问题在目前算法中显得尤为突出。如何在寻找到的重要节点基础上展开复杂网络的社团结构挖掘,相关研究工作才刚刚起步。本文的研究是在对复杂网络节点重要性评价分析的基础上,探究基于重要节点的社团挖掘算法,试图解决或部分解决目前经典算法中的常见问题,并将所提出的算法应用于现实网络中。本文研究工作的主要贡献如下:(1)在网络节点重要性评价方面,研究了当前主流的四种单一中心性评价指标,以及一种基于主成分分析的综合性评价指标计算方法,给出了基准网络上的不同评价指标下的节点重要性分布;(2)提出了一种种子节点非重叠社团挖掘算法。根据中心性评价指标确定种子节点,利用深度优先搜索策略进行全局社团划分,对于重叠节点利用社团间的连边数解决其归属问题。与经典社团聚类算法相比,基准网络上的实验结果表明该算法取得了较好的社团划分结果,且算法的计算复杂度较低;(3)提出了一种基于核心节点的局部社团挖掘算法。将网络中的重要节点作为初始社团的核心节点,通过计算核心节点与其邻居节点的相似度进行局部社团划分,再对相似的局部社团合并以得到最终的社团结构。与经典社团聚类算法和所提出的种子节点社团挖掘算法相比,基准网络上的实验结果表明该算法在划分性能方面具有明显的优势;(4)将所提出的局部社团挖掘算法应用于蛋白质相互作用网络的功能模块检测,并结合基因本体数据库对模块的生物学意义进行了分析。与CPM算法和MCODE算法相比,实验结果表明所提出的算法在节点丢失率较低情况下,可挖掘到的匹配率=50%的蛋白质模块数比例较高。
【关键词】：复杂网络 社团挖掘 重要节点 蛋白质相互作用网络
【学位授予单位】：石家庄铁道大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP301.6
【目录】：

• 摘要3-4
• Abstract4-9
• 第一章 绪论9-18
• 1.1 研究背景9-10
• 1.2 研究目的及意义10-11
• 1.2.1 研究目的10
• 1.2.2 研究意义10-11
• 1.3 研究现状11-14
• 1.3.1 复杂网络中节点重要性评估研究现状11-13
• 1.3.2 复杂网络中社团挖掘研究现状13-14
• 1.4 主要研究内容及创新点14-16
• 1.4.1 主要研究内容14-15
• 1.4.2 创新点15-16
• 1.5 论文的组织结构16-18
• 第二章 相关理论研究18-34
• 2.1 网络节点的重要性评价指标18-22
• 2.1.1 度中心性18
• 2.1.2 接近度中心性18-19
• 2.1.3 介数中心性19-20
• 2.1.4 特征向量中心性20
• 2.1.5 综合性评价指标20-22
• 2.2 基准网络上的节点重要性评价22-28
• 2.2.1 基准网络介绍22-23
• 2.2.2 评价指标计算23-28
• 2.3 经典社团挖掘算法28-32
• 2.3.1 GN算法28-29
• 2.3.2 Newman快速算法29-31
• 2.3.3 CPM算法31-32
• 2.4 社团挖掘算法的性能指标32-33
• 2.5 本章小结33-34
• 第三章 种子节点非重叠社团挖掘算法34-44
• 3.1 种子节点34
• 3.2 深度优先搜索算法34-35
• 3.3 算法描述35
• 3.4 算法的时间复杂度分析35-37
• 3.5 实验结果及分析37-39
• 3.5.1 Zachary’s Karate网络38
• 3.5.2 Football网络38-39
• 3.6 与其它算法对比39-43
• 3.6.1 与经典社团挖掘算法对比39-41
• 3.6.2 不同重要性评价指标对比41-43
• 3.7 本章小结43-44
• 第四章 基于核心节点的局部社团挖掘算法44-57
• 4.1 核心节点44
• 4.2 相似度44-45
• 4.3 算法描述45-49
• 4.4 算法的时间复杂度分析49-50
• 4.5 基准网络上的实验结果与分析50-53
• 4.5.1 阈值的选取50-52
• 4.5.2 实验结果及分析52-53
• 4.6 与其它算法对比53-56
• 4.6.1 与经典聚类挖掘算法对比53-55
• 4.6.2 不同重要性评价指标对比55-56
• 4.7 本章小结56-57
• 第五章 PPI网络上的局部社团挖掘算法应用57-66
• 5.1 蛋白质功能模块预测概述57
• 5.2 PPI网络功能模块聚类挖掘常用算法57-59
• 5.2.1 图划分聚类算法58
• 5.2.2 基于密度的局部搜索聚类算法58-59
• 5.2.3 层次聚类算法59
• 5.3 PPI网络数据59-61
• 5.4 用于PPI网络分析的性能指标61
• 5.5 局部社团挖掘算法在PPI网络上的应用61-65
• 5.6 本章小结65-66
• 第六章 总结与展望66-68
• 参考文献68-72
• 致谢72-73
• 个人简历、在学期间的研究成果及发表的学术论文73

【相似文献】

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

1 胡洪林;;截断思想在算法分析中的应用[J];科技风;2012年12期

2 陈际平;算法分析与优化程序的研究[J];西北大学学报(自然科学版);1994年05期

3 梁彦杰;徐坚;;算法分析中概率变化与图形生成[J];云南大学学报(自然科学版);2009年S2期

4 刘宁;邵晓艳;;算法分析与设计课程中多媒体技术的应用[J];科技风;2009年18期

5 海亚;张永平;;算法对学生解决问题能力的培养[J];黑龙江科技信息;2008年10期

6 李冰颖,夏利民,舒远仲;学分制模式下网上选课系统的算法探析[J];江西科学;2004年05期

7 Anany Levitin;Maria Levitin;;算法谜题[J];中国科技信息;2014年08期

8 杜刚;陆黎明;;一修路问题的算法解决分析[J];太原师范学院学报(自然科学版);2006年02期

9 许之民;;砝码称重问题的多种算法分析与探究[J];合肥学院学报(自然科学版);2011年01期

10 李亚楠;;菌群优化算法分析[J];贵州大学学报(自然科学版);2011年02期

中国重要会议论文全文数据库 前10条

1 俞洋;田亚菲;;一种新的变步长LMS算法及其仿真[A];通信理论与信号处理新进展——2005年通信理论与信号处理年会论文集[C];2005年

2 周颢;刘振华;赵保华;;构造型的D~2FA生成算法[A];中国通信学会通信软件技术委员会2009年学术会议论文集[C];2009年

3 赖桃桃;冯少荣;张东站;;一种基于划分和密度的快速聚类算法[A];第二十五届中国数据库学术会议论文集（一）[C];2008年

4 刘远新;邓飞其;罗艳辉;舒添慧;;ERP柔性平台下物流运输配送系统算法分析[A];第二十六届中国控制会议论文集[C];2007年

5 王树西;白硕;姜吉发;;模式合一的“减首去尾”算法[A];第二届全国学生计算语言学研讨会论文集[C];2004年

6 王万青;张晓辉;;改进的A~*算法的高效实现[A];2009全国测绘科技信息交流会暨首届测绘博客征文颁奖论文集[C];2009年

7 孙焕良;邱菲;刘俊岭;朱叶丽;;IncSNN——一种基于密度的增量聚类算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

8 韩建民;岑婷婷;于娟;;实现敏感属性l-多样性的l-MDAV算法[A];第二十七届中国控制会议论文集[C];2008年

9 张悦;尤枫;赵瑞莲;;利用蚁群算法实现基于程序结构的主变元分析[A];第五届中国测试学术会议论文集[C];2008年

10 王旭东;刘渝;邓振淼;;正弦波频率估计的修正Rife算法及其FPGA实现[A];全国第十届信号与信息处理、第四届DSP应用技术联合学术会议论文集[C];2006年

中国重要报纸全文数据库 前1条

1 科文;VIXD算法分析Web异常[N];中国计算机报;2008年

中国博士学位论文全文数据库 前10条

1 魏哲学;样本断点距离问题的算法与复杂性研究[D];山东大学;2015年

2 刘春明;基于增强学习和车辆动力学的高速公路自主驾驶研究[D];国防科学技术大学;2014年

3 张敏霞;生物地理学优化算法及其在应急交通规划中的应用研究[D];浙江工业大学;2015年

4 李红;流程挖掘算法研究[D];云南大学;2015年

5 盛歆漪;粒子群优化算法及其应用研究[D];江南大学;2015年

6 黄磊;高动态环境捷联惯导信号处理及高精度姿态速度算法研究[D];南京航空航天大学;2015年

7 刘新旺;多核学习算法研究[D];国防科学技术大学;2013年

8 于滨;城市公交系统模型与算法研究[D];大连理工大学;2006年

9 曾国强;改进的极值优化算法及其在组合优化问题中的应用研究[D];浙江大学;2011年

10 肖永豪;蜂群算法及在图像处理中的应用研究[D];华南理工大学;2011年

中国硕士学位论文全文数据库 前10条

1 赵官宝;基于位表的关联规则挖掘算法研究[D];昆明理工大学;2015年

2 殷文华;移动容迟网络中基于社会感知的多播分发算法研究[D];内蒙古大学;2015年

3 徐翔燕;人工鱼群优化算法及其应用研究[D];西南交通大学;2015年

4 潘浩;基于可逆结构的超点和长流检测算法研究[D];大连海事大学;2016年

5 王宁伟;微博网络中的重叠社区发现算法研究[D];北京交通大学;2016年

6 高山;星载MIMO检测算法的抗SEU技术研究[D];解放军信息工程大学;2014年

7 张振宾;国密SM4和SM2算法功耗攻击关键技术研究与实现[D];清华大学;2015年

8 闫婷;基于混合细菌觅食和粒子群的k-means聚类算法在类风湿并发症中的研究[D];太原理工大学;2016年

9 曹阳;基于质心策略的蝙蝠算法[D];太原科技大学;2015年

10 高越;量子K近邻算法研究[D];东南大学;2015年

，

本文编号：675633