复杂网络中关键节点的查找方法研究

发布时间：2017-09-27 14:31

  本文关键词：复杂网络中关键节点的查找方法研究

  更多相关文章： 中点 直径路径 先验蛋白质 PPI网络 复杂网络

【摘要】：复杂网络中的关键节点对整个网络的结构具有重要作用。对于真实网络而言,能够有效地定位到关键节点对网络的维护与网络性质的研究等方面都具有重要意义。本文从网络拓扑结构出发,并结合PPI (Protein-Protein Interaction)网络的生物信息特征,给出两个关键节点查找算法。直径在各种类型的网络中都是极其重要的拓扑结构参数。然而,直径很少被用于关键节点的查找。本文定义直径所在路径的中点为整个网络的中点,并给出搜索中点的DCD算法。该算法被用在小世界网络、无标度网络、星形长尾网络和五个真实网络中,实验结果表明,通过DCD算法搜索到的中点在网络中心性指标如介数中心性(BC)接近中心性(CC)、度中心性(DC)、肛核分解上比整个网络的平均情况具有优势。此外,删除中点后,网络结构如直径和最大连通分支都发生很大变化。本文还基于DCD算法提出了有效的删边策略,该策略能够实现只删除少量边而使网络节点对在很大程度上不连通。DCD算法不需要找到所有可能的直径所在路径,而是基于广度优先和Bellman准则,因此其时间复杂度对于稀疏网络而言要优于Floyd算法。对于PPI网络而言,结合生物信息的关节蛋白质搜索方法被证明比单纯从拓扑结构出发的方法准确率更高。然而,现有的大多数搜索方法只包含一类生物学信息。PPI网络固有的由假阳性及假阴性交互关系引起的噪音也对重要蛋白质预测的准确性有很大影响。本文对此提出了一个有效的重要蛋白质搜索方法IDSSP,该方法首先结合STRING数据库的多种生物学信息对每个蛋白质进行评分,评分高的蛋白质被用作先验蛋白质。然后,对先验蛋白质的邻居节点进行权重计算以选出候选重要蛋白质,权值的计算过程通过对DIP和STRING数据库的整合实现。整合后的蛋白质交互关系具有高可信性。在酿酒酵母菌上进行的实验结果表明IDSSP方法在绝大多数情况下比现有的准确率较高的方法CPPK、CEPPK和UDoNC准确率更高。除此之外,本文中所使用的先验蛋白质不需要是重要蛋白质。
【关键词】：中点 直径路径 先验蛋白质 PPI网络 复杂网络
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-9
• 1 绪论9-13
• 1.1 研究背景及意义9-10
• 1.2 研究现状10-12
• 1.3 本文内容组织结构12-13
• 2 复杂网络关键节点搜索概述13-23
• 2.1 复杂网络中心性指标简介13-14
• 2.1.1 介数中心性13
• 2.1.2 接近中心性13-14
• 2.1.3 度中心性14
• 2.1.4 k-核分解14
• 2.2 直径与网络连通性14-15
• 2.3 PPI网络中的关键节点搜索15-22
• 2.3.1 “中心性—致命性”法则15-17
• 2.3.2 PPI相关数据库17-18
• 2.3.3 重要蛋白质搜索算法18-22
• 2.4 小结22-23
• 3 基于直径的重要节点搜索方法23-39
• 3.1 基于直径的重要节点搜索方法23-25
• 3.2 数据集25-27
• 3.2.1 确定性网络25-26
• 3.2.2 由Pajek生成的小世界网络模型和无标度网络模型26-27
• 3.2.3 实际网络27
• 3.3 实验结果27-37
• 3.3.1 确定性网络27-28
• 3.3.2 星形长尾网络28-29
• 3.3.3 小世界网络和无标度网络29-32
• 3.3.4 实际网络32-35
• 3.3.5 基于DCD算法的删边策略35-37
• 3.4 DCD算法时间复杂度37
• 3.5 结论37-39
• 4 基于先验知识的重要蛋白质搜索方法39-50
• 4.1 基于先验知识的重要蛋白质搜索方法39-42
• 4.1.1 STRING中的组合分数39-40
• 4.1.2 IDSSP中的蛋白质评分40-41
• 4.1.3 候选重要蛋白质41-42
• 4.2 数据集42
• 4.3 实验结果42-48
• 4.3.1 综合比较42-43
• 4.3.2 先验蛋白质个数43-44
• 4.3.3 重要与非重要先验蛋白质44-45
• 4.3.4 IDSSP方法的随机性45-47
• 4.3.5 F_1 Score47-48
• 4.3.6 高分先验蛋白质的普适性48
• 4.4 结论48-50
• 结论50-52
• 参考文献52-58
• 附录A DCD算法伪代码58-61
• 附录B S.cere中评分前40名的蛋白质61-62
• 攻读硕士学位期间发表学术论文情况62-63
• 致谢63-64

【相似文献】

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

1 李忠学,童根树,严慧;节点连接刚性对门式刚架结构承载能力的影响[J];力学季刊;2001年02期

2 孙伟;李平;;全预制砼框架结构节点连接[J];科技信息;2009年23期

3 谭跃进;吴俊;邓宏钟;;复杂网络中节点重要度评估的节点收缩方法[J];系统工程理论与实践;2006年11期

4 王蕾蕾;林中材;潘佳庆;杨孔庆;邹卫东;;利用节点效率评估地理网格网络的鲁棒性[J];湖北科技学院学报;2013年02期

5 ;[J];;年期

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

1 查晓雄;钟建伟;;节点对集装箱房性能影响的研究[A];'2011全国钢结构学术年会论文集[C];2011年

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

1 ;为电网“充电”[N];网络世界;2002年

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

1 王家林;非节点连接有限元理论及其软件实现[D];重庆大学;2008年

2 刘军;物联网可靠感知节点部署优化理论与方法研究[D];广东工业大学;2015年

3 刘亚志;延迟容忍网中数据传输关键技术研究[D];北京邮电大学;2013年

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

1 郑晓欣;城市供水管网节点混合规律研究[D];哈尔滨工业大学;2015年

2 任卓明;复杂网络中的节点重要性度量研究[D];上海理工大学;2013年

3 杨文静;Tarax Node节点在线调试平台的设计与实现[D];电子科技大学;2015年

4 王倩;影响信息流行为的节点间关系模型与控制策略的研究[D];石家庄铁道大学;2015年

5 陆兆龙;钢筋混凝土宽柱双梁节点的抗震性能研究[D];扬州大学;2015年

6 雷雨潼;林中有向传感器节点确定性部署的研究[D];北京林业大学;2016年

7 南栋卿;复杂网络中关键节点的识别研究[D];吉林大学;2016年

8 谢昆;多温度工况冷弯薄壁钢货架梁-柱节点疲劳性能试验研究[D];东南大学;2016年

9 关雅文;复杂网络中关键节点的查找方法研究[D];大连理工大学;2016年

10 毛一帆;含时二分网络中重要节点的识别研究[D];深圳大学;2017年

，

本文编号：930192