复杂网络中社团发现算法研究及应用

发布时间：2017-10-20 04:35

  本文关键词：复杂网络中社团发现算法研究及应用

  更多相关文章： 复杂网络 社团发现 非重叠社团 重叠社团 蛋白质相互作用网络 熵有效性函数

【摘要】：复杂网络研究作为一个新兴的学科方向,吸引了许多来自不同学科研究人员的广泛关注。社团结构是复杂网络的一个重要特征,刻画了复杂网络中局部内的关系和局部之间的关系,是复杂网络研究的一个新热点。随着人类基因组计划测序工作的完成,以蛋白质组学为研究重点的后基因时代悄然到来,蛋白质组学的研究对象是蛋白质相互作用网络。目前,蛋白质相互作用网络的研究重点是生物模块识别,生物模块可看作是蛋白质相互作用网络中的社团结构。将社团结构发现算法应用到蛋白质相互作用网络识别生物模块,并结合基因本体数据库进行生物学分析,具有重要的理论研究价值和实际应用意义。本文主要研究内容包括:(1)对复杂网络中的基准网络和生物学中的蛋白质相互作用网络数据,进行了关键特征验证与分析。发现两类网络数据基本满足小世界特征,基准网络数据基本不满足无尺度特征,模块度特征较明显。蛋白质相互作用网络具有明显的无尺度特征;(2)研究了几种经典的非重叠社团发现算法:谱方法、k-means算法、GN算法、模块度优化算法和MCODE算法。在蛋白质相互作用网络数据上的应用表明模块度优化算法所得划分结果具有较高生物支持;(3)在重叠社团发现算法方面,重点研究了派系过滤算法和模糊聚类算法,基准网络和蛋白质相互作用网络上的实验结果表明,派系过滤算法在较稀疏的基准网络和蛋白质相互作用网络数据上,节点丢失率较高。模糊聚类算法在基准数据上实验结果较好,但在蛋白质相互作用网络中只能发现少量模块,模块规模跨度较大,降低了在生物学方面的支持作用;(4)基于信息熵概念提出了一个新的社团结构评价指标:熵有效性函数。该指标在社团划分正确性与时间代价方面优于模块度函数。将其与FCM算法相融合,在基准网络数据上的实验结果表明熵有效性函数能够较准确地找到“最佳”聚类数。
【关键词】：复杂网络 社团发现 非重叠社团 重叠社团 蛋白质相互作用网络 熵有效性函数
【学位授予单位】：石家庄铁道大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• abstract5-11
• 第一章 绪论11-19
• 1.1 研究背景11-12
• 1.2 研究目的及意义12
• 1.3 复杂网络社团分析研究现状12-16
• 1.3.1 非重叠社团分析研究现状13-14
• 1.3.2 重叠社团分析研究现状14-16
• 1.4 论文研究内容及创新点16-17
• 1.4.1 主要研究内容16-17
• 1.4.2 主要创新点17
• 1.5 论文的组织结构17-19
• 第二章 复杂网络关键特征描述及验证分析19-32
• 2.1 相关图论知识19-20
• 2.1.1 图的基本概念19-20
• 2.1.2 图的矩阵表示20
• 2.2 复杂网络关键特征描述20-22
• 2.2.1 小世界特征20-21
• 2.2.2 无尺度特征21-22
• 2.2.3 模块度特征22
• 2.3 网络数据22-30
• 2.3.1 基准网络数据22-24
• 2.3.2 PPI网络数据24-26
• 2.3.3 网络特征量验证与分析26-30
• 2.4 社团结构分析相关评价指标30-31
• 2.4.1 用于基准网络分析的评价指标30
• 2.4.2 用于PPI网络分析的评价指标30-31
• 2.5 本章小结31-32
• 第三章 非重叠社团发现算法研究与应用32-64
• 3.1 谱方法32-40
• 3.1.1 基于Laplace矩阵的谱方法32
• 3.1.2 基于Normal矩阵的谱方法32-33
• 3.1.3 基于特征系统的谱映射33
• 3.1.4 谱方法在基准网络上的应用33-40
• 3.1.5 谱方法的特点总结40
• 3.2 k-means算法40-48
• 3.2.1 k-means算法介绍40-41
• 3.2.2 k-means算法在基准网络上的应用41-47
• 3.2.3 k-means算法在PPI网络上的应用47-48
• 3.2.4 k-means算法的优缺点48
• 3.3 GN算法48-53
• 3.3.1 GN算法介绍48-49
• 3.3.2 GN算法在基准网络上的应用49-52
• 3.3.3 GN算法在PPI网络上的应用52-53
• 3.3.4 GN算法的优缺点53
• 3.4 模块度优化算法53-60
• 3.4.1 基于层次聚类的模块度优化算法介绍53-54
• 3.4.2 模块度特征向量算法介绍54
• 3.4.3 模块度优化算法在基准网络上的应用54-57
• 3.4.4 模块度优化算法在PPI网络上的应用57-60
• 3.5 MCODE算法60-61
• 3.5.1 MCODE算法介绍60
• 3.5.2 MCODE算法在PPI网络上的应用60-61
• 3.5.3 MCODE算法的优缺点61
• 3.6 非重叠社团发现算法的纵向对比61-63
• 3.7 本章小结63-64
• 第四章 重叠社团发现算法研究与应用64-82
• 4.1 CPM算法64-68
• 4.1.1 CPM算法介绍64-65
• 4.1.2 CPM算法在基准网络上的应用65-67
• 4.1.3 CPM算法在PPI网络上的应用67-68
• 4.1.4 CPM算法的优缺点68
• 4.2 FCM算法68-73
• 4.2.1 FCM算法介绍68-70
• 4.2.2 FCM算法在基准网络上的应用70-73
• 4.2.3 FCM算法在PPI网络上的应用73
• 4.3 FWSC算法73-77
• 4.3.1 FWSC算法介绍73-74
• 4.3.2 FWSC算法在基准网络上的应用74-76
• 4.3.3 FWSC算法在PPI网络上的应用76-77
• 4.4 EWSC算法77-80
• 4.4.1 EWSC算法介绍77-78
• 4.4.2 EWSC算法在基准网络上的应用78-80
• 4.4.3 EWSC算法在PPI网络上的应用80
• 4.5 本章小结80-82
• 第五章 熵有效性函数82-91
• 5.1 信息熵概念82
• 5.2 新的评价指标——熵有效性函数82-83
• 5.3 熵有效性函数与模块度函数对比分析83-85
• 5.4 结合熵有效性函数的FCM算法85-90
• 5.4.1 聚类数范围85-86
• 5.4.2 两个过滤条件86
• 5.4.3 算法描述与时间复杂度分析86-87
• 5.4.4 实验结果与分析87-90
• 5.5 本章小结90-91
• 第六章 结论91-93
• 参考文献93-98
• 致谢98-99
• 个人简历、在学期间的研究成果及发表的学术论文99

【参考文献】

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

1 孙茜雅;;基于最小熵聚类的社团检测算法[J];电子科技;2012年03期

2 郑啸;陈建平;邵佳丽;别立东;;基于复杂网络理论的北京公交网络拓扑性质分析[J];物理学报;2012年19期

，

本文编号：1065275