基于社团结构和自信息的复杂网络链路预测算法研究

发布时间：2017-04-08 16:39

  本文关键词：基于社团结构和自信息的复杂网络链路预测算法研究，，由笔耕文化传播整理发布。

【摘要】：现实世界中很多复杂系统诸如社会、生物、信息系统甚至自然道路河流都可以用复杂网络来抽象表示,以网络中的结点表示对象,以边表示对象之间的交互关系。复杂网络蕴藏的信息会随着真实系统不断演化而叠积,交互关系(链接)作为其中的一种重要信息载体,对其进行挖掘显得十分必要。作为信息挖掘的基础研究问题之一,链路预测能够根据已知的网络拓扑结构,网络节点属性等一系列特征来发掘其中的隐含信息,同时它也是对网络不完整性的一种补全手段。具体来说,链路预测就是通过衡量各种与网络密切相关的影响因素,充分利用这些因素来预测网络中丢失的链接和未来可能产生的链接。随着大数据时代的降临,已有的某些预测算法已经不能满足实际问题的需要,算法的预测准度还需要进一步提高。目前链路预测的主流研究方向是基于相似性度量的方法,此类方法有着较低的时间复杂度和较高的预测能力。基于概率模型的方法因为技术手段的革新也受到越来越多的重视,此类方法随着模型的精确构建而有着越来越高的预测精度,同时时间复杂度也逐步被降低。本文在前人工作的基础上分别对这两类预测算法进行了深入研究,并在此基础上从网络结构特性和信息论角度出发,提出了基于网络社团结构的CSBased算法和基于自信息的CNSI算法。CS-Based算法思想来源于复杂网络社团结构本身的特性:社团内部联系紧密,社团与社团之间连接相对稀疏。本文认为这一性质对链路预测有着重要的促进作用,社团内的节点相似度会因社团本身的紧密程度而得到提升,社团之间的节点相似度也会因为社团之间的紧密度而提升。如果将社团这种特性加入到链路预测中,将会很大程度上提高算法的准度。真实数据集上的实验得出,CS-Based算法预测性能优于其他经典方法。对于CNSI算法,本文通过信息论知识建立预测模型,将节点间的相似度转化为网络中某些重要特征存在的前提下节点成链的条件自信息,如果越多的特征存在,比如本文中用到的共同邻居、不同长度的路径等,自信息就越小,由此反映出节点间发生链接的可能性越大。最后通过实验同样证明了CNSI方法较好的预测能力,优于其他对比算法。
【关键词】：复杂网络 社团结构 信息论 链路预测
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要3-4
• Abstract4-8
• 第一章 绪论8-13
• 1.1 论文研究的背景和意义8-9
• 1.2 国内外的研究现状9-11
• 1.3 论文的主要研究内容11-12
• 1.4 论文的组织架构12-13
• 第二章 复杂网络结构特征概述与链路预测问题13-23
• 2.1 复杂网络相关知识13-15
• 2.1.1 复杂网络的图表示13-14
• 2.1.2 路径和平均路径长度14
• 2.1.3 节点度和度分布14
• 2.1.4 聚类系数14-15
• 2.2 链路预测问题15-16
• 2.3 链路预测算法16-20
• 2.3.1 基于概率模型的链路预测算法16-17
• 2.3.2 基于节点邻居相似性的链路预测算法17-19
• 2.3.3 基于路径相似性的链路预测算法19-20
• 2.3.4 基于随机游走的链路预测算法20
• 2.4 链路预测问题评价指标20-22
• 2.5 本章小结22-23
• 第三章 基于社团结构的链路预测算法23-36
• 3.1 复杂网络社团结构23-24
• 3.2 社团检测算法SLPA24-25
• 3.3 CS-Based算法25-28
• 3.3.1 CS-Based算法的思想25-26
• 3.3.2 社团紧密度定义26-27
• 3.3.3 CS-Based算法描述27-28
• 3.3.4 算法分析28
• 3.4 实验及结果分析28-35
• 3.4.1 实验环境28
• 3.4.2 数据集28-30
• 3.4.3 参数设置30
• 3.4.4 结果分析30-35
• 3.5 本章小结35-36
• 第四章 基于自信息的链路预测算法CNSI36-49
• 4.1 信息论相关知识简介36-37
• 4.2 链路预测的信息论模型37-38
• 4.3 基于节点邻居结构体的CNSI算法38-45
• 4.3.1 CNSI算法的提出38-39
• 4.3.2 CNSI算法的描述39-45
• 4.4 实验及结果分析45-48
• 4.4.1 实验环境与数据集介绍45
• 4.4.2 参数设置45-46
• 4.4.3 结果分析46-48
• 4.5 本章小结48-49
• 第五章 总结与展望49-51
• 5.1 本文的工作总结49-50
• 5.2 下一步工作展望50-51
• 参考文献51-55
• 在学期间的研究成果55-56
• 致谢56

【相似文献】

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

1 刘晋霞;曾建潮;薛耀文;;复杂网络强社团结构探测[J];小型微型计算机系统;2011年04期

2 贾宁宁;封筠;;复杂网络的社团结构发现[J];河北省科学院学报;2013年02期

3 宣照国;苗静;党延忠;刘建国;;科研领域关联网络的社团结构分析[J];上海理工大学学报;2008年02期

4 王伊蕾;王远志;李涛;田生文;;伪度优先演化网络的社团结构研究[J];计算机工程与应用;2009年20期

5 汪小帆;刘亚冰;;复杂网络中的社团结构算法综述[J];电子科技大学学报;2009年05期

6 司夏萌;刘云;丁飞;熊菲;;具有社团结构的有界信任舆论涌现模型研究[J];系统仿真学报;2009年23期

7 谢军;;复杂网络中分析社团结构算法研究概述[J];信息通信;2010年04期

8 朱大勇;张新丽;李树全;;利用局部拓扑信息发现模糊社团结构[J];电子科技大学学报;2011年01期

9 邵斐;蒋国平;;基于社团结构的负载传输优化策略研究[J];物理学报;2011年07期

10 谈煜;梁润鹏;;一种基于层次化社团结构的网络可视化方法[J];微型电脑应用;2012年04期

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

1 苗清影;汪小帆;;基于社团结构的复杂网络可控性研究[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

2 李晓佳;张鹏;狄增如;樊瑛;;复杂网络中的社团结构[A];第四届全国网络科学学术论坛暨研究生暑期学校论文集[C];2008年

3 胡延庆;赵尔波;张丹;狄增如;樊瑛;;社团结构的局域和自适应比较性定义及其相应探测方法[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

4 吴文涛;肖仰华;何震瀛;汪卫;余韬;;基于权重信息挖掘社会网络中的隐含社团[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

5 樊瑛;李梦辉;张鹏;吴金闪;狄增如;;权重对网络结构和性质的影响——社团结构中权重的作用[A];2006全国复杂网络学术会议论文集[C];2006年

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

1 程建军;复杂网络中的社团检测方法研究[D];兰州大学;2015年

2 李琳;基于多元统计分析的社团挖掘算法研究[D];上海交通大学;2014年

3 武志昊;复杂网络中的重叠社团发现问题研究[D];北京交通大学;2013年

4 魏芳;基于图挖掘的网络社团结构发现[D];复旦大学;2008年

5 刘传建;复杂网络中的社团结构划分及分析应用[D];山东大学;2014年

6 何东晓;复杂网络社团结构发现方法研究[D];吉林大学;2014年

7 刘晋霞;复杂网络社团结构的探测及其在资金融通网络中的应用研究[D];兰州理工大学;2013年

8 刘瑶;社会网络特征分析与社团结构挖掘[D];电子科技大学;2013年

9 邬盈盈;基于V稳定性理论的复杂网络稳定性分析与牵制控制方法研究[D];浙江大学;2010年

10 于乐;社会网络中社团发现及网络演化分析[D];北京邮电大学;2014年

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

1 刘微;复杂网络中社团结构的发现[D];辽宁师范大学;2011年

2 王大军;基于标签传播的社团检测算法研究[D];辽宁大学;2015年

3 杨强;微博社交网络模型的建立及其性质研究[D];北京化工大学;2015年

4 付世海;基于社团结构的网络多传播源定位算法研究[D];东北大学;2013年

5 马骁骑;复杂网络中社团检测技术研究[D];黑龙江大学;2015年

6 张献鹏;基于P4结构的社团挖掘方法[D];西安电子科技大学;2014年

7 陈奔燕;复杂网络的社团探测[D];湘潭大学;2015年

8 杜梅;基于半监督的社团结构发现方法研究[D];合肥工业大学;2014年

9 韩凌霄;复杂网络社团划分及城市公交网络研究[D];青岛理工大学;2015年

10 董哲;复杂网络中的社团发现算法研究[D];解放军信息工程大学;2014年

  本文关键词：基于社团结构和自信息的复杂网络链路预测算法研究，由笔耕文化传播整理发布。

本文编号：293255