基于互信息和节点中心性的链路预测算法研究

发布时间：2020-03-25 11:36

【摘要】：链路预测作为复杂网络重要的研究方向之一,在理论研究和实际应用中都意义重大。目前关于链路预测的研究主要是针对静态网络,忽略了网络的时间演化信息,并且大部分的链路预测算法没有考虑到邻居节点之间的差异性,因此存在一定的不足。本文主要从以下几个方面展开研究:1,在链路预测中区分不同的邻居节点;2,利用网络的历史信息进行动态网络链路预测;3,在链路预测中考虑节点中心性的影响。主要工作如下:1、研究了静态网络中基于互信息的链路预测算法。为了对不同的邻居节点进行有效地区分,本文在原始互信息算法的基础上考虑了共同邻居的度信息,提出了改进的互信息算法。该算法不仅考虑了共同邻居之间的结构信息,还通过节点的度信息来区分不同的邻居节点。实验表明:在静态网络中,区分不同的邻居节点可以提高链路预测算法的精确度。2、改进的互信息算法在动态网络中的应用。为了充分利用网络演化过程中的历史信息,本文利用时间序列模型表示动态网络,并将改进的互信息算法与移动平均模型相结合,提出了改进的移动平均互信息算法。该算法不仅利用了网络的结构信息和节点的度信息,还考虑了历史信息对当前时刻的影响。实验表明,当网络中存在较多连边时,改进的移动平均互信息算法在链路预测中表现优异。3、研究了动态网络链路预测中节点中心性的作用。考虑到不同节点在网络中重要性的差异,首先通过节点中心性方法来衡量节点的重要性,然后进行归一化处理,并与已有的链路预测算法相结合,将结合后的算法应用于动态网络链路预测。实验结果表明,考虑节点中心性的链路预测算法在动态网络中有较高的精确度。
【图文】：

哥尼斯堡七桥问题

对于复杂系统的描述和研宄一般是通过复杂网络来实现的。逡逑对复杂网络的研宄有着悠久的历史，最初起源于１９３６年欧拉解决的“七桥逡逑问题”。如图１．１所示，“七桥问题”是指如何从一个地方（Ａ、Ｂ、Ｃ、Ｄ）出逡逑发，走遍Ａ、Ｂ、Ｃ和Ｄ四个地方，最后回到起点，条件是每座桥走且仅走一逡逑遍［１，２】。欧拉将每个出发点抽象为图中的节点，每座桥可以理想化为一条边，因逡逑此，该问题就变成了如何通过一笔画出图１．１（ｂ）的图形。逡逑ｘ逡逑（邋Ｂ逦Ａ逦抽象邋＇）Ｂ邋Ｈ逦逡逑Ｄ逦Ｄ逡逑（ａ）逦（ｂ）逡逑图１．１哥尼斯堡七桥问题逡逑Ｆｉｇ邋１．１邋Ｔｈｅ邋ｐｒｏｂｌｅｍ邋ｏｆ邋ｓｅｖｅｎ邋ｂｒｉｄｇｅｓ邋ｉｎ邋Ｋｏｎｉｇｓｂｅｒｇ逡逑二十世纪六十年代，Ｅｒｄｏｓ和Ｒｅｎｙｉ连续发表了三篇文章，从而提出了著名逡逑的随机图（ＥＲ）模型［３＿５］，从此复杂网络理论在数学领域有了系统化的研宄。逡逑ＥＲ模型的大致含义如下：对于一个节点数为Ｎ的网络，在一定时间内，这Ｎ逡逑个节点之间随机相连，其中连接的概率均为；？，，且ｐ是个固定值，由此形成的逡逑网络叫随机网络。该模型的提出极大地促进了复杂网络的研究进展

无向图,示例,顶点

Ｆｉｇ邋２．１邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｕｎｄｉｒｅｃｔｅｄ邋ｎｅｔｗｏｒｋ逡逑在无向网络中，如果0＾ｉ0）ｅ￡，则说明顶点／和顶点＿／之间是相邻的，即逡逑顶点／是顶点＿／的邻居，记ｒ（0为顶点／的所有邻居集合。如图２．１所示，顶点逡逑６的邻居有顶点１、顶点３和顶点５，用公式表示为ｒ（６）邋＝邋｛１，３，５｝。如果用邻接逡逑矩阵来表示图，则表达式如（２．１）所不：逡逑Ｗ邋Ｗ邋（２，）逡逑Ｉ邋１逦（Ｖｉ，ｖ；）邋ｅ邋Ｅ逡逑９逡逑
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5;TP301.6

【参考文献】