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

摘要

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

目录

声明

摘要

插图

表格

第一章绪论

1．1研究背景和意义

1．1．1 研究背景

1．1．2研究意义

1．2国内外研究现状

1．3研究内容

1．4论文组织结构安排

第二章链路预测相关知识

2．1 复杂网络基础知识

2．1．1网络的表示

2．1．2链路预测问题描述

2．1．3链路预测评价指标

2．2复杂网络的基本特征

2．3网络的节点中心性

2．4基于相似性的链路预测

2．4．1基于共同邻居的相似性指标

2．4．2基于路径的相似性指标

2．4．3基于随机游走的相似性指标

2．4．4其他相似性指标

2．4．5局部、全局以及半局部相似性指标

2．5本章小结

第三章静态网络中基于互信息的链路预测算法

3．1熵与互信息

3．1．1熵

3．1．2互信息

3．2基于互信息的链路预测算法及其改进

3．2．1基于互信息的链路预测算法

3．2．2改进的基于互信息的链路预测算法

3．3 MMI算法设计与分析

3．3．1算法设计

3．3．2算法分析

3．4实验数据与结果分析

3．4．1实验数据

3．4．2实验结果分析

3．5 Facebook超链接网络分析

3．5．1实验准备

3．5．2实验结果与分析

3．5．3网络特征与实验结果展示

3．6本章小结

第四章互信息与节点中心性在动态网络中的应用

4．1动态网络的表示

4．2动态网络中的预测模型

4．3基于互信息的动态网络链路预测算法

4．3．1 移动平均模型下的链路预测算法

4．3．2动态网络中MMI算法的参数分析

4．4时间序列划分长度分析

4．5节点中心性在动态网络中的应用

4．5．1 基于节点中心性的链路预测算法

4．5．2实验流程及结果分析

4．6本章小结

5．1本文总结

5．2展望未来

参考文献

致谢

在读期间发表的学术论文与取得的研究成果