基于复杂网络结构的链接预测

发布时间：2020-04-13 20:01

【摘要】：近年来,随着统计学、物理学、社会学和计算机科学等多门学科的交叉性研究的兴起,复杂网络分析逐渐成为交叉性科学研究的热点。链接预测是根据网络结构属性预测网络中节点之间是否存在链接的方法和技术。该技术作为复杂网络分析的主要研究方向,在模拟网络演化、学习网络表征等理论研究方面,以及推断信息传播、提供推荐服务等应用服务领域均有重要的研究价值。但是由于数据规模的不断扩大,网络结构也日益复杂,使得已有链接预测算法的有效性大大降低。因此如何充分利用复杂网络结构信息设计链接预测算法成为该领域中新的难点和重点。同时随着人们对机器学习与数据挖掘领域研究的不断深入,如何学习网络中的复杂结构提高链接预测算法的性能也受到极大的关注。本文以挖掘共邻节点贡献、加权聚类系数、影响力节点和社区信息等复杂网络结构特征为主线,结合贝叶斯模型、随机块模型、迁移学习等机器学习技术对基于复杂网络结构的链接预测算法开展了深入细致的研究,并做出了以下主要贡献:(1)新近提出的基于局部朴素贝叶斯概率模型的链接预测算法能够度量不同共邻节点对潜在节点对的贡献,实现简单且有效。但该算法假定每个共同邻居对链接的形成产生单独作用,并不能反映网络各节点相互连接的图状结构特征。针对这一问题,本文提出了一种基于树状增强朴素贝叶斯概率模型的链接预测算法。该算法利用互信息来度量共邻节点之间的潜在相关性,有效地解决了其中的独立性假设限制。在对人工网络、真实网络的实验结果证明了其相对于传统算法的优越性。(2)在加权网络中,基于局部结构的相似度指标被广泛用于加权复杂网络的链接预测问题。然而此类指标忽略了共同邻居对计算潜在链接相似度产生的不同贡献,也没有计算局部结构中共邻节点之间链接的不同加权权重。因此,本文通过引入加权聚类系数的概念把无权的朴素贝叶斯预测算法拓展到加权复杂网络的应用场景。在真实加权网络的大量实验上证明了提出算法的有效性。(3)基于局部结构的预测指标对网络中所有可能的链接计算相似度,并无区分链接是否处同一社区或者不同社区之间,也没有区分处于不同社区结构下共邻节点对预测节点对的影响。因此本文通过划分社区结构提出了一种差分化处理潜在链接和共邻节点贡献的预测算法。该算法把链接划分成社区内部和社区间两类链接计算相似度,同时提出了共邻节点链接度和社区参与度的概念,有效地处理了在社区划分下不同共邻节点的影响。大量实验表明算法能够有效提高链接预测效果并推广到CN和Jaccard指标当中。(4)社区表示在复杂网络中的簇。同一社区内部节点之间的链接比较紧密,而社区与社区之间的链接比较稀疏。本文借鉴了经典的随机块模型和社交圈子发现算法,提出一种平衡模块度最大化的链接预测算法(MMLP)。MMLP首先搭建一个强调内部链接的概率生成过程。该过程能够有效的利用模块度定义解释链接预测和社区发现之间的联系,同时把集成特征和链接相关联,从而学习不同特征在不同社区的权重。大量的实验表明MMLP比基准算法取得了更好的预测效果。(5)面向多维度异构网络的链接预测算法缺点在于显式地使用维度间的关联。即在原有的同构算法基础上添加和维度相关的概率表示,并没有深入挖掘各维度子网络之间的隐含关系。同时各种用于计算相似度的特征均是基于局部结构或者路径结构的特征,是领域相关的,并不具备一般性。为了克服这些缺点,我们在MMLP的基础上采用迁移学习的思想用源维度子网络学习的知识帮助目标维度子网络的预测,提出一个社区层次的内部维度间知识迁移的算法(ITLP)。ITLP既保留了MMLP在挖掘社区变化和链接生成之间的关系的特点,更通过迁移学习的思想有效地拓展到多维网络链接预测中。在真实多层次数据集的实验证明了ITLP的鲁棒性。(6)许多通过共邻节点影响权重定义相似度的预测算法没有办法同时把网络的宏观(全局)和微观(局部)两类特性纳入到同一个算法当中。即使部分算法能够集成上述特性,但运算效率低,没有办法拓展到较大规模的密集网络当中。为了克服这些缺点,提出一个基于全局性影响力节点识别的链接预测算法。该算法通过引入有影响力节点识别技术中的节点影响力排名得分来定义不同共邻节点的贡献,有效集成了局部结构和全局结构的影响。在无权网络和加权网络的大量实验表明,提出的算法能够快速并准确地完成较大规模具备密集结构网络的链接预测任务。
【图文】：

a) 完整网络 b) 训练网络 c) 待预测网络图 1-1 链接预测实验划分过程示意图1.2 链接预测接下来将介绍链接预测的基本定义、研究现状以及相关检验指标。1.2.1 问题定义给定一个复杂网络G=(V,E)，其中V和E分别表示节点或者链接的集合。在一个特定的时间点t，，链接预测的目的是在某个未来的时间点 ′(t′>t)判断尚未产生的链接的潜在节点对（或称为预测节点对）是否会产生新的链接，或者在当前的网络结构下预测丢失链接或者未被发现的链接。由于动态网络数据获取比较困难，因此在目前的主流研究中，一般都假设网络是静态的。尽管该研究思路在一定程度上和真实的复杂网络不符，但是

图 2-1 网络局部结构示例图独立的共邻节点，两者均影响蓝色潜在节点对的形成。在左下角子图的 TAN 模型说明中，属性X1在类Y上依赖于X3的值，而左上角子图的 LNB 模型说明中每个属性对Y的影响是独立于其他属性的。显然LNB并不包括属性之间的关系（共邻节点之间的关系），它可能无法反映在局部结构中的“链接”结构。相反，TAN 能够捕获属性之间的潜在相关性并使其在预测过程中发挥重要作用[80]。综上所述，本章节的贡献总结如下： 提出了一个新颖的基于树状增强朴素贝叶斯（TAN）模型的复杂网络链接预测算法。该算法保留了 LNB 的优点同时利用信息熵对共邻节点之间的隐含关系建模，缓解其中的强独立假设限制。 TAN 算法可以扩展到其他基于相似度的度量：CN、AA 和 RA。 使用人工和真实世界的数据集进行实验评估，结果表明提出的算法能够对共邻节点之间的相关性建模，并提高链接预测任务的精确度。
【学位授予单位】：华南理工大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O157.5;TP301.6

【相似文献】

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

1 李经安;徐志平;;一种改进的邻节点发现算法[J];计算机与网络;2015年12期

2 李瑞睿;郑相全;王靖;叶久志;;一种基于定向天线的邻节点发现算法[J];现代电子技术;2011年05期

3 杨健敏;乔钢;聂东虎;马璐;;基于定向收发的水声通信网络邻节点发现机制[J];电子与信息学报;2018年11期

4 刘丽;;基于伪最近邻节点的异构无线网络组网实现及仿真[J];吉林工程技术师范学院学报;2014年03期

5 朱清超;;多跳吞吐量分析及邻节点实时估计算法设计[J];计算机应用;2017年09期

6 刘靖永;李乐民;景小荣;;多跳无线网络中无需邻节点信息的空间覆盖广播算法[J];电子与信息学报;2010年10期

7 张筠;李颖;;移动Ad Hoc网络中定向发送与接收算法的改进[J];计算机工程;2009年05期

8 伍国华;马满好;;路径交叉检测与消除方法和邻节点置换方法改进TSP的解[J];计算机应用研究;2011年02期

9 张远;郭虹;刘洛琨;;AODV协议中扩展环搜索与邻节点列表的实现[J];计算机工程;2006年10期

10 高辉;刘静;徐友云;;Ad hoc网络中一种基于邻节点时间安排的多址接入协议[J];上海交通大学学报;2008年07期

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

1 董朝平;郭龙祥;殷敬伟;生雪莉;;基于Mamdani推理的水下数据转发机制研究[A];中国声学学会2017年全国声学学术会议论文集[C];2017年

2 魏远伦;滕丁;;TD小区H载波不能被占用的原因分析与解决[A];四川省通信学会2014年学术年会论文集[C];2014年

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

1 伍杰华;基于复杂网络结构的链接预测[D];华南理工大学;2018年

2 张远;基于距离和角度信息的无线传感网节点定位问题研究[D];山东大学;2012年

3 顾德;无线传感器网络拓扑边界与瓶颈辨识[D];浙江大学;2012年

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

1 韩琳;基于定向天线的自组织网络邻节点发现机制研究[D];西安电子科技大学;2017年

2 高辉;分布式网络中基于邻节点调度的多址接入协议的研究[D];上海交通大学;2008年

3 杨巧;基于改进相似度的社会网络链接预测研究[D];华南理工大学;2015年

4 肖珑;基于邻节点残存率和双路径的回退路由算法[D];天津大学;2012年

5 郑果;移动自组网拓扑管理软件的研究与设计[D];复旦大学;2009年

6 贺瑛;面向城市场景的车辆自组织网络路由协议研究[D];西安电子科技大学;2014年

7 姜男澜;WSN定位问题的研究[D];杭州电子科技大学;2014年

8 刘金定;基于邻节点残存率的AODV路由协议优化研究[D];南京理工大学;2009年

9 王冠;基于费舍尔信息的协作定位算法研究[D];重庆邮电大学;2017年

10 O词つ

本文编号：2626377