论文总字数：36272字

摘 要

社交网络中的链接预测是通过目前已知的网络结构等相关信息，预测网络中节点之间的链接变化。传统的链接预测侧重于预测网络中尚未链接的两个节点之间，在未来产生链接的可能性。现有链接预测工作忽略了一个普遍的事实，即当前网络中链接在未来可能会断开，这类链接称为消失链接。

目前在消失链接预测方面及消失链接预测方法的研究非常少，本文从基于拓扑结构的基本链接预测方法出发，对社交网络中的消失链接预测方法进行了研究，主要工作和贡献如下：

1. 明确消失链接在具体社交网络中的含义，对原先评价传统链接预测方法的标准进行扩展，使其适用于消失链接预测的方法。
2. 分别在无向网络和有向网络中进行实验，将预测方法分为无权图、有权图和带时需信息的方法这三类，结合并改进多种有效的预测方法，进行消失链接预测。实验结果表明传统的链接预测方法不适用于消失链接预测中，考虑时序信息的方法取得了有效的预测结果。
3. 分析实验结果，发现链接消失的可能原因有时间因素、相互性原则和节点的受欢迎程度，而网络内嵌性对链接的消失没有明显的影响。

关键词：社交网络，链接预测，消失链接，链接强度

Disappearing Link Prediction Method in Social Network

Abstract

Link prediction in social network is the method to predict the change of links between nodes by analyzing known structure information of the network. The traditional link prediction focuses on predicting the new link in the future. It neglects a general fact, that the link in current network may break in the future. This kind of links are called disappearing link.

At present, researches on how to predict disappearing links is very few. This paper does the research on how to predict disappearing links in the aspect of the methods based on topology structure information. The Main work and contributions of this paper are:

1. Define what the disappearing link is in specific social network. Extend the evaluation criterion for traditional link prediction to fit the methods of disappearing link prediction.
2. Propose methods for undirected graph, methods for directed graph, and methods with timing information. Combine and improve these methods, and do examination both in directed and undirected network. From the result of examination, it shows that traditional methods in link prediction are not useful in disappearing link prediction, while the methods with timing information turn out to be effective.
3. Analyze the result of examination, and then find the probable reason for link disappearing, including timing information, reciprocity and popularity. Embeddedness does not work in disappearing link prediction.

Keywords: Social Network, Link Prediction, Disappearing Link, Link Strength

目 录

摘 要 I

第一章 绪论 1

1.1 研究背景和目的 1

1.2 国内外研究现状 1

1.3 主要工作及贡献 3

1.4 论文组织结构 4

第二章 消失链接预测问题 5

2.1 消失链接 5

2.2 消失链接预测流程 5

2.3 评价标准 5

2.4 本章小结 7

第三章 无向图中的消失链接预测 8

3.1 无向图中的消失链接预测方法 8

3.1.1 无向无权图中的链接强度计算方法 8

3.1.2 无向有权图中的链接强度计算方法 9

3.1.3 带时序的无向图中的链接强度计算方法 9

3.2 实验数据 10

3.2.1 数据集介绍 10

3.2.2 数据统计 11

3.3 评价标准选择 12

3.4 实验结果及分析 13

3.5 本章小结 21

第四章 有向图中的消失链接预测 22

4.1 有向图中的消失链接预测方法 22

4.1.1 有向无权图中的链接强度计算方法 22

4.1.2 有向有权图中的链接强度计算方法 22

4.1.3 带时序的有向图中的链接强度计算方法 23

4.2 实验数据 24

4.2.1 数据集介绍 24

4.2.2 数据统计 24

4.3 评价标准 25

4.4 实验结果及分析 26

4.5 本章小结 33

第五章 总结与展望 35

5.1 总结 35

5.2 展望 35

致谢 36

参考文献 37

附录一 本科学习期间科研成果及荣誉 39

第一章 绪论

1.1 研究背景和目的

随着Web2.0技术的迅速发展，人们迅速进入了在线社交的时代，对社会网络的研究也获得了广泛的关注。人的本质在其现实性上是一切社会关系的综合。在实际社会生活中，每个人都有自己的人际关系。如果把人看作节点，人与人之间的关系看作边，这些人和相互间的关系就构成了现实生活中的社交网络。

社交网络一个最大特点就是动态性和多变性：社交网络中的节点和边会随着时间增加或减少。链接预测为如何通过现有的信息来有效地对未知链接和未来的链接变化做出预测提供了解决方法。现有大多数链接预测工作主要处理对未知链接（网络中实际存在但未被我们发现的链接）的预测和对未来链接（网络中目前还不存在但将来很有可能出现的链接）的预测。然而，只有极少数的研究工作意识到不仅要预测未知和未来的链接，而且还需要预测网络中未来可能消失的链接，本文称之为消失链接预测问题。

本文着重研究的是社交网络中的消失链接预测问题。社交网络是现实世界的某种程度上的抽象，将之看作一个图，其中的节点就代表了用户，节点之间的链接就是用户之间的关系。链接预测通过捕捉网络中隐藏的关于边的信息，帮助我们理解影响每条边产生和消失的因素，进而帮助我们了解整体网络的演化方式。链接预测研究不仅具有如上所述的理论价值，其更重要的意义还是体现在应用方面。如今，社交网络服务网站在互联网中拥有大量的用户，如Facebook、YouTube等网站甚至拥有十几亿的注册用户。在这些网站中，用户希望寻找到有共同兴趣爱好的朋友，以及在现实中感兴趣但不容易接触到的人，从而扩大自己的社交范围。不难发现，在大多数成功的社交网络服务网站中，都具备推荐系统，帮助用户结识感兴趣的朋友，包括“你可能认识的人”、“你可能感兴趣的人”、“你关注的人还关注”等。这些都是通过链接预测来实现的，不仅增进了网站的社交功能，更有助于提高用户体验，从而吸引更多的用户。在结交新朋友上，传统的链接预测方法已经得到了很好的应用，而消失链接预测更关注的是链接的维系。例如在当前的好友中，发现并提示可能会破裂的关系，以及最稳定的关系，相当于用户与当前所有好友的亲密度。在社交网络中好友关系普遍多于现实中的朋友关系，因此消失链接预测对好友管理提供的辅助作用会逐渐显现。

1.2 国内外研究现状

随着Facebook，LinkedIn等各种社交网站的流行，社会网络的应用引起了广泛的关注。这些社交网络提供了大量的动态网络数据，为研究动态网络提供了方便。而链接预测作为数据挖掘领域的重要研究方向之一，在计算机领域已有了比较深入的研究。链接预测的方法可以大致分为以下四类：第一类是基于节点的链接预测方法，第二类的基于拓扑结构的链接预测方法，第三类是基于社交理论的链接预测方法，第四类是基于学习的链接预测方法^[1]。

基于节点的链接预测方法主要思想非常简单，节点对之间越相似，他们产生链接的可能性也越大，反之亦然。这与人们更乐意与教育背景、兴趣爱好、地理位置等更接近的人成为朋友。在这类方法中比较新的研究有Bhattacharyya等人定义的多重分类树模型，通过学习用户个人档案中的关键字定义用户的相似度^[2]。该方法的研究中发现，除了用户的直接好友，与其他用户之间的相似度是几乎相同的。此外，Anderson等人提出的使用用户兴趣爱好的重合度来衡量相似度方法，将用户不同的行为表示成向量，用行为向量之间的余弦值来表示用户之间的相似度^[3]。在能够获取到用户的行为和属性信息的情况下，这类方法能够取得较好的效果。在没有节点和边的属性的简单网络中，仍能通过拓扑结构信息来得到节点间的相似度，这类方法就是基于拓扑结构的链接预测方法。Liben-Nowell和Kleinberg提出了基于网络拓扑结构的相似度的预测方法，并总结了一系列相似度测量的指标^[1]。包括基于节点共同邻居的方法：Common Neighbor，Adamic-Adar，Jaccard系数，Preferential attachment等；基于路径的Katz算法以及基于随机游走的方法：Hitting time，，SimRank 等算法。

基于社会理论的链接预测方法运用了社群、三角闭包、强弱链接、同质性与结构平衡等经典社会理论，通过额外获取一些具有意义的交互信息来提高预测效果。Valverde-Rebaza和Lopes将Twitter上用户的兴趣爱好和行为与社会理论结合进行预测，取得了有效的成果^[5]。Li等人提出了中心节点在链接预测中的重要地位，并提出了一系列的基于最大熵游走的链接预测方法^[6]。

基于学习的链接预测方法主要分为基于特征的分类方法、概率图模型和矩阵分解方法。Ichise等人利用作者、文章题目、摘要以及时间等信息进行语义分析，提高了合著网络中的预测结果^[7-10]。Clauset等人提出了一个能够推断网络层次结构的模型，用于解决链接预测问题^[11]。Menon等人将链接预测问题看做是矩阵的完全问题，将矩阵分解方法扩展来解决链接预测问题^[12]。

除了以上提到的多种方法外，还有许多方法，然而这些工作都是在研究关系的建立，对于关系的解除的研究则非常少。以下是一些在消失链接预测问题中的研究。

Kwak等人收集了51天内韩语用户在Twitter上在线关系和推文的日常快照，发现了“取消关注”行为在Twitter上是一种普遍现象。通过分析用户的行为发现关系的相互性、关系的持续时间、关注之人的信息价值和关系的重叠是影响用户“取消关注”行为的几个主要因素^[13]。之后还采访了22名韩国用户，采访结果表明，用户更倾向于“取消关注”那些短时间内发送许多推文，以及总是发一些生活琐事的人。之后，包括Kwak的一些研究人员又使用逻辑回归模型得到了5个结构性因素和7个行为性因素，能够很好地解释取消关注的行为^[14]。并且发现了Twitter用户在交互关系中表现得更关注自我，通常希望得到关注更甚于关注他人，这一特点也会在关系解除中产生影响。

Xu, Huang等人考虑了Twitter上用户决定“取消关注”的相互关联性和动态特性，通过SIENA模型来测试了相互性、身份、内嵌性、同质性以及信息价值对解除关系的影响^[15]。其中相关性属性在“取消关注”行为中至关重要，两个用户相互关注和拥有共同的关注对象会明显降低相互之间“取消关注”行为发生的可能性。并且“取消关注”行为常常是双向的，当一个用户发现别人不再关注自己，他也会取消对这个人的关注。此外，身份差距越大，对关系解除的正面影响也越大，其余几个特性都对保持关系有正面影响。

Kivran-Swaine等人参考链接强度、网络内嵌性、权利和身份这几个关键的社会学概念，提出了三类特征：节点s自身的属性，包括关注s的人数、关注s的人数和s关注的人数之比、关注s人数中s也关注的人的比例以及s关注的人数中也关注s的人的比例；关注者的属性，定义关注s的人为f，包括关注f的人数、关注f的人数和f关注的人数之比；节点对的属性，例如s和f共同关注者的数量等。然后使用多水平逻辑回归模型分析提出的各属性对关系解除的影响^[16]，实验结果表明链接强度、网络内嵌性和身份地位对关系解除有影响。关注s的人越重要，越有可能停止关注s。s与f共同关注的人越多，s和f的关系越不容易解除。

Sibona 等人通过网上问卷调查Facebook用户，找出了好友请求在关系解除时产生的影响，并将统计到的各种因素分类为在线和线下两个类别^[17]。在线因素包括频繁的无关紧要的文章、观点极端的文章、不合时宜的文章、琐碎生活的文章等，线下因素包括讨人厌的行为、关系变动等。

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