论文总字数：24937字

摘 要

社交网络分析可以帮助人们获得大量有价值的商业信息和社会行为信息，吸引了众多领域领域的兴趣。在计算机科学领域，社交网络链接预测，即预测网络未来可能形成的链接是社交网络分析的重要方向之一。在经济学领域，研究人员使用博弈论分析网络形成的机制，称为网络形成博弈。将博弈论方法与链接预测结合起来是一个新颖的研究方向。然而，现有的基于博弈论的社交网络链接预测方法仅采用拓扑结构信息表示用户收益，一方面不能有效反映博弈过程中用户效用变化，另一方面忽略了网络权重等信息。在这篇文章中，我们提出了使用网络形成博弈模型改进链接预测的方法，目的是能更好地反映网络形成机制来提高链接预测精度。进一步，我们探究使用网络权重信息帮助改进社交网络链接预测方法。

首先我们提出网络形成博弈链接预测框架，简单地将博弈论分析和链接预测方法结合起来。然后，在基于节点的链接预测博弈方法中，我们使用网络形成博弈模型表示用户的效用，代替基于轨道向量的方法。另外，我们从福利矩阵的计算方法出发，提出了将权重信息融入基于边的链接预测博弈方法。在真实数据集中的实验表明，我们提出的方法在一定程度上提高了之前的博弈论链接预测方法。

关键词：链接预测；博弈论；社交网络

Abstract

Social Network Analysis can help people get a lot of valuable information. It has attracted great research interests in different fields. In Computer Science, much effort has been down in predicting future links, which is called link prediction. While in Economics, researchers use game theory to analyze the mechanism of network formation, which is called Network Formation Game. To combine link prediction and game theory is a novel research direction. Most existing work use network topology to represent user’s utility in game theoretic models, which cannot effectively reflect the utility changes but also ignore the network weight information. In this work, we present an approach to improve link prediction via levering the power of Network Formation Games. And then we introduce a method that combine the network weight into game theoretic link prediction models.

Firstly, we propose a framework that straightforwardly combines game theoretic analysis with link prediction method. Secondly, we incorporates Network Formation Game into node based game theoretic method, which is called Node-NFG. Specifically, Node-NFG use NFG models to represent utility, which can better reflect network formation mechanism. Thirdly, we developed the improved edge based game theoretic method that take advantage of both network weight and topology by redefining the welfare matrix. The experiments are conducted on real world datasets and the results demonstrate that our proposed method outperforms that of the previous game theoretic link prediction method.

Keywords: Link Prediction, Game Theory, Social Network

目 录

摘要 1

Abstract 2

第一章 绪论 5

1.1 研究背景 5

1.2 研究现状 6

1.2.1 链接预测 6

1.2.2 网络形成博弈模型 6

1.2.3 有权网络的链接预测 7

1.3 论文工作 7

1.4 论文组织结构 7

第二章 链接预测模型和网络形成博弈 9

2.1 链接预测问题及表示方法 9

2.2 基于网络结构的相似性指标 9

2.3 基于博弈论的社交网络链接预测模型 10

2.4 网络形成博弈 10

2.4.1 网络形成博弈模型 10

2.4.2 真实网络中的实证分析 11

2.5 NFG链接预测框架 12

2.6 本章小结 13

第三章 基于节点的NFG链接预测博弈方法 15

3.1 基本思想和流程 15

3.2 节点策略初始化 15

3.3 NFG效用函数设置 16

3.4 纳什均衡求解和链接过滤 16

3.5 本章小结 17

第四章 基于边的有权网络链接预测博弈方法 19

4.1 有权重网络的相似性指标 19

4.1.1 有权相似性指标 19

4.1.2 弱连接的作用 19

4.2 基于边的有权链接预测预测博弈方法 20

4.2.1 基本思想 20

4.2.2 有权福利函数设置 20

4.2.3 收益函数计算及收益方法优化 21

4.3 本章小结 22

第五章 实验评估 23

5.1 数据集 23

5.1.1 网络数据集 23

5.1.2 数据集的划分 23

5.2 评价指标 24

5.3 实验结果及分析 24

5.3.1 NFG链接预测框架实验 25

5.3.2 基于节点的NFG博弈方法（Node-NFG）实验 26

5.3.3 基于边的有权网络博弈方法(Edge-WRA)实验 27

5.4 本章小结 29

第六章 总结与展望 30

6.1 总结 30

6.2 展望 30

致谢 31

参考文献 33

绪论

剩余内容已隐藏，请支付后下载全文，论文总字数：24937字