复杂网络中基于模式的链接预测

摘要

复杂网络中的链接预测一直以来都受到研究者们的关注，它通过分析已知网络的信息，建立复杂的模型来预测网络中未知的链接和未来可能产生的链接。链接预测对于探索以复杂网络为模型的应用背后的规律有着极为重要的作用。传统的链接预测主要针对于复杂网络的拓扑结构，试图通过已有的链接关系发现新的链接，从而探索网络中隐含的知识。然而，传统方法并未充分合理地利用复杂网络中蕴含的丰富属性信息，而属性信息对于网络中链接的形成具有重要的作用。基于以上考虑，本文将复杂网络中的多维属性信息与原有的链接预测模型进行结合，研究基于属性的链接预测问题。
　　由于复杂网络中大多数点对之间未链接，而未链接的点对作为不可信反例无法有效用于传统预测模型中，因此本文利用PU学习思想（Positive and Unlabeled Learning），提出一种基于属性的链接模式挖掘算法，该算法将未链接的点对以合理的方式引入训练模型，从组合特征的角度挖掘链接模式，并设计D指标过滤具有区分力的链接模式，通过基于属性的链接模式从整体上刻画网络中链接形成的原因。同时针对链接预测问题，本文通过图的聚集计算求解基于属性的链接模式强度，并利用模式构造个性化概率转移矩阵，从而建立基于链接模式的局部随机游走模型(PBLRW)。本文提出的预测方法区别于传统的随机游走预测方法，以属性特征作为依据，构建个性化的概率转移矩阵，使得关系紧密的节点之间获得更高的随机游走概率，从而最终产生更为精确的预测效果。
　　本文分别在UCI数据集、政治博客(Political Blogs)数据集和新浪微博数据集上进行了多组实验，实验结果表明:(1)本文提出的链接模式挖掘方法能够挖掘并过滤出具有较强区分力的模式，这些模式对于类别具有明显的区分能力，因此能够很好地刻画链接是否产生的内在原因;(2)本文提出的基于模式的链接预测模型，能够充分利用属性知识构造个性化的概率转移矩阵，克服了传统随机游走模型中转移概率固定的缺陷;(3)对于政治博客数据集和新浪微博数据集的实验表明，本文提出的模型在各项综合指标上均优于传统的链接预测方法和基于分类的方法。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 国内外研究现状

1．2．1 链接预测问题研究现状

1．2．2 带属性的链接预测问题研究现状

1．2．3 现状总结

1．3 研究目标及内容

1．4 论文的主要工作

1．5 论文组织结构

第二章 复杂网络链接预测相关技术

2．1 复杂网络

2．1．1 复杂网络的统计性质

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

2．1．3 复杂网络举例

2．2 链接预测基本模型

2．2．1 链接预测问题基本定义

2．2．2 带属性的链接预测问题

2．3 链接预测关键技术

2．3．1 基于二元分类的预测方法

2．3．2 基于节点相似性的预测方法

2．3．3 基于路径相似性的预测方法

2．3．4 基于随机游走的预测方法

2．4 本章小结

第三章 复杂网络中的链接模式挖掘

3．1 基本思想

3．2 基于属性的链接模式挖掘

3．2．1 基于PU学习思想的模式挖掘

3．2．2 评价模式的区分力：D值

3．3 模式挖掘算法

3．4 本章小结

第四章 基于模式的链接预测

4．1 基本思想

4．2 链接模式的强度计算

4．2．1 随机块模型

4．2．2 链接模式强度计算

4．3 基于链接模式的随机游走模型

4．3．1 基于模式的概率转移矩阵构造算法

4．3．2 算法伪代码

4．3．3 算法分析

4．4 本章小结

第五章 数据集获取和预处理

5．1 UCI Machine Learning Repository

5．1．1 数据集描述

5．1．2 数据集预处理

5．2 Political Blogs数据集

5．2．1 数据集描述

5．2．2 数据集预处理

5．3 新浪微博数据集

5．3．1 数据集获取

5．3．2 数据集描述

5．3．3 数据集预处理

5．4 本章小结

第六章 实验设计与分析

6．1 实验环境

6．1．1 硬件环境

6．1．2 软件环境

6．2 实验评价指标

6．2．1 模式挖掘算法验证实验评价指标

6．2．2 链接预测实验评价指标

6．3 基于PU学习的模式挖掘算法实验

6．3．1 实验设计

6．3．2 对比方法介绍

6．3．3 整体效果对比

6．3．4 模式区分力验证

6．3．5 训练集大小对挖掘算法的影响

6．4 复杂网络链接预测实验

6．4．1 实验设计

6．4．2 对比方法介绍

6．4．3 整体效果对比

6．4．4 训练集大小对预测效果的影响

6．4．5 不同L值下算法的预测效果

6．5 本章小结

第七章 原型系统实现

7．1 原型系统整体架构

7．2 原型系统实现

7．2．1 开发环境

7．2．2 系统流程图

7．2．3 原型系统总体类图

7．2．4 系统可视化

7．3 本章小结

第八章 总结和展望

8．1 研究工作总结

8．2 研究工作展望

致谢

参考文献

作者简介