基于高阶编码的复杂网络链路预测冶忠林有限公司计算机与互

本书从复杂网络角度出发，对基于高阶编码的链路预测算行结与探索。全书分为4部分，由11章构成。第1部分(第1-3章)介绍了复杂网络与链路预测相关的基础知识以及经典的基于节点相似性的链路预测算法；第2部分(第4-7章)考虑了节点与邻居的邻居节点的高阶相似性关系，介绍了基于网络表示学阶编码链路预测算法；第3部分(第8-9章)从物理学的角度出发，考虑节点与节点之间的相互作用力以及节点的高阶特征，介绍了基于复杂网络引力场的高阶编码链路预测算法；第4部分(第10-11章)对链路预测当下的主流应用作了介绍。后，本书做了整结，并指出了待改之处。

第1部分基础知识

第1章复杂网络

1.1复杂网络简介

1.1.1复杂网络的由来

1.1.2复杂网络的图表示

1.1.3复杂网络的计算机表示

1.1.4路径与短路径

1.1.5连通性

1.2复杂网络的拓扑性质

1.2.1节点的度

1.2.2度分布

1.2.均路径长度

1.2.4直径

1.2.5集聚系数

1.2.6节点中心性

1.3典型的复杂网络模型

1.3.1随机网络模型

1.3.2小世界网络模型

1.3.3无标度网络模型

第2章 链路预测

2.1链路预测方法

2.2链路预测技术

2.3数据集划分

2.3.1随机抽样

2.3.2逐项遍历

2.3.3k折叠交叉检验

2.3.4熟识者抽样

2.4评价指标

2.4.1 AUC

2.4.2度

2.4.3排序分

2.5应用

第3章基于节点相似性的链路预测算法

3.1基于局部信息的节点相似性算法

3.1.1基于共同邻居的节点相似性算法

3.1.2基于Adamic-Adar的相似性算法

3.1.3基于资源分配的相似性算法

3.1.4基于偏好连接的相似性算法

3.1.5基于局部朴素贝叶斯模型的相似性算法

3.2基于路径的节点相似性算法

3.2.1基于局部路径的相似性算法

3.2.2 Katz相似性算法…

3.2.3 LHN-II相似性算法

3.3基于随机游走的节点相似性算法

3.3.1基均通勤时间的相似性算法

3.3.2基于随机游走的余弦相似性算法

3.3.3有重启的随机游走相似性算法

3.3.4基于局部随机游走的相似性算法

3.3.5基于叠加效应的随机游走相似性算法

3.4其他节点相似性算法

3.4.1基于矩阵森林理论的相似性算法

3.4.2TSCN相似性算法

3.5基于节点相似性的链路预测算法主函数

第2部分基于网络表示学阶链路预测算法

第4章 基于矩阵分解的DeepWalk 链路预测算法

4.1问题描述

4.2模型框架

4.2.1基于矩阵分解的DeepWalk算法

4.2.2LPMF算法

4.3实验分析

4.3.1实验数据

4.3.2基准方法

4.3.3评价指标

4.3.4实验结果与分析

4.3.5度分布可视化

4.3.6调参与分析

4.3.7网络表示可视化

4.3.8案例研究

第5章基于网络节点文本增强的链路预测算法

5.1问题描述

……

9.2.3LP-GFCNNC算法

9.3实验分析

9.3.1实验数据

9.3.2基准方法

9.3.3实验结果与分析

9.3.4度分布可视化

第4部分链路预测的应用

第10章链路预测在知识图谱中的应用

10.1知识图谱的表示

10.2知识图谱嵌入技术

10.2.1距离变换嵌入模型

10.2.2语义匹配嵌入模型

10.3利用链路预测完成知识图谱补全任务

第11章链路预测在系统中的应用

11.1系统简介

11.2基于内容的

11.3基于协同过滤的

11.4相关数据集

参考文献

随着社会的快速发展，每天产生的数据量以指数级的规模在增长，但其中有价值和可用的数据却占很小的一部分，如何从海量的数据中抽取和挖掘出这部分数据是目前研究的热点之一。数据伴随着日常生活而产生，可以反映人们的日常生活行为，因此，对数据的挖掘和建模分析可以直接反映真实生活的方方面面。先对数行分析和模拟，再在现实生活中提出可行的意见或建议，这是目前常用的方法系统。另外，研究者为现实世界中的各种复杂系统建立了复杂网络模型，开始研究各种复杂网络系统的行为和特性，如复杂网络的演化机制、连通性以及抗毁性等，并发现这些行为和特性离不开复杂系统中个体本身的行为，更离不开个体与个体之间的关联关系，而链路预测为挖掘个体与个体之间的关联关系提供了有效的预测机制。与此同时，链路预测也为社会步做出了很大的贡献。比如，在社交网络中，在线社交的出现为移动互联网带来了的变革。其中为常见的一个应用是在线社交利用网络的结构特征预测陌生人成为朋友的可能性，即将当前不是朋友但以后可能是朋友的给另一位用户，这不仅方便了用户，还提升了用户对本社交系统的忠诚度，这就是链路预测技术的体现。

本书主要介绍基于高阶编码的链路预测算法，考虑了节点的1阶相似性、2阶相似性、……、n阶相似性，同时融入了更多的网络结构信息和节点间的信息建模网络结构，更好地表示了节点之间的高阶关系，从而有效挖掘网络中蕴含的深层次特征。首先，本书为读者提供了链路预测的相关基础知识，为了解高阶编码的链路预测算法奠定基础；其次，为让读者对高阶编码的链路预测算法有更深刻的认识，从网络表示学度介绍了4种高阶链路预测算法（基于矩阵分解的DeepWalk链路预测算法、基于网络节点文本增强的链路预测算法、基于高似的链路预测算法、联合多视图特征的链路预测算法），又从复杂网络引力场的角度介绍了2种高阶链路预测算法（基于复杂网络引力场的链路预测算法、基于复杂网络引力场与节点收缩的链路预测算法）；后，通过理论联系实际，介绍了链路预测在实际生活中的广泛应用，以加深读者对链路预测的理解。

本书由冶忠林、杨燕琳、孟磊和马子恒共同撰写完成。在本书的撰写过程中，冶忠林负责第1~3章的撰写工作，杨燕琳负责第4~6章的撰写工作，马子恒负责第7~11章的撰写工作，孟磊负责本书的组稿工作。本书的撰写还借鉴了一些网络、书籍中的观点，在此向这些作者一并表示感谢。

本书的完成受到国家研发计划（2020YFC1523300）、青海省自然科学青年项目（2021-ZJ-946Q）、青海省研发与转化计划（2020-GX-112）、青海师范大学中青年科研项目（2020QZR007）的资助。

希望本书能帮助对基于高阶编码的链路预测算法感兴趣的读者，解决他们的疑惑。由于作者有限，本书难免存有偏颇之处，敬请读者提出宝贵意见。如有任何疑问，敬请读者联系本书作者（邮箱：zhonglin_ye@fox. com)，我们当深表感谢。

第1章复杂网络

自20世纪90年代邓肯·瓦茨（DuncanWatts）和艾伯特·拉斯洛·巴拉巴西（Albert-Laszló Barabasi）等提出小世界网络模型和无标度网络模型以来，复杂网络科学呈爆炸式发展，研究者们为现实中各复杂系统建立了复杂网络模型，如交通网络、生态网络和社交关系网络等。为了更有效地解决现实问题，学者们开始研究各种复杂网络系统的行为和特性，如复杂网络的演化机制、连通性以及抗毁性。学者们还发现复杂网络系统的这些行为和特性不仅依赖于复杂系统中个体本身的行为，更依赖于个体与个体之间的关联关系。链路预测为探索复杂网络的演化机制、行为和特征等提供了一个有效的预测机制。

为了使读者更好地理解链路预测，本章将介绍复杂网络的相关知识，这对于初次接触或者刚入门链路预测的读者来说，是很有必要的。

1.1复杂网络简介

复杂网络科学的迅速发展为人类的生活带来了便利，了社会步。复杂网络被用来表示离散的物体之间的关联关系，它[由大量的节点和边组成，其中，节点表示现实中复杂网络系统中的个体，边表示个体之间的关联关系。在实际生活中，存在着各种各样的复杂网络，例如，社交关系系统可以看作人与人之间的关系网络，将人看作节点，人与人之间的关系看作边；生物蛋白质系统可以看作蛋白质与蛋白质之间的相互作用网络[2]，将蛋白质作为节点，蛋白质之间的相互作用作为边。类似的复杂网络还有电力网络[3]、交通网络[4]、科研合作网络[5]等。人类社会的网络化为人类社会生产与生活带来了极大的便利，提高了人类的生产效率和生活质量。

1.1.1复杂网络的由来

欧拉对七桥问题的抽象和论证思想，了数学中的一个分支——图论（GraphTheory)[1]。因此，欧拉被公认为图论之父，而图1-2也被称为欧拉图。如今，人们关于复杂网络的研究与欧拉当年关于七桥问题的研究在某种程度上一脉相承，即网络结构与网络性质密切相关。这种抽象思想也广泛应用到了现实世界的各个复杂系统中，例如，将交通系统中的路作为边，将路连通的地方作为点，这样就把交通系统抽象为了图。

冶忠林，博士，青海师范大学计算机学院副教授。硕士研究生期间主要研究新一代互联网语义信息搜索引擎，解决了搜索过程中问句的分词、词性标注、语义理解和超大规模知识图谱构建等问题，该搜索引擎在开放领域问答国际评测任务中获得了综合性能M的成绩。博士研究生期间主要研究复杂网络数据挖掘，在第六届与第七届中国计算机学会主办的大数据学术会议上两次获得佳学术论文提名。目前主要研究方向为自然语言处理中的词性标注、分词、智能问答等，以及复杂网络领域的网络表示学、图神经网络、社会计算等。2019年入选青海省Q人计划拔尖人才项目。截止目前，已发表学术论文36篇，其中，SCI/EI检索论文17篇，中文1篇，国际顶会1篇，C中文科技B类期刊5篇，中文核心10余篇，已获得发明专利1项，实用新型发明专利2项。获得研究生国家奖学金、优秀研究生标兵、优秀研究生等荣誉称号16次（除学业奖学金）。曾参与开发绵阳市道路交通卡口管理系统、交通违章抓拍系统，该系统目前已部署在绵阳、天津、乌鲁木齐等多个城市，为城市交通管理和运营提供了重大技术贡献。现参与国家自然科学项目一项，青海省重大成果转化专项两项，国家研发项目一项，主持青海师范大学青年科学一项。指导学生参加竞赛获得校级一等、优秀、铜牌各一项，省级二等、三等一项，获优秀指导老师荣誉一项。