社会网络中的链接预测任务

刘峰　刘秉权　王晓龙

摘 要：随着互联网技术的飞速发展，社会网络成为了许多人生活日常中的一部分。这些不同兴趣的社会网络，大都会提供种类各异的用户交互服务。这些种类丰富的社会成员之间的交互行为大部分都可以用链接的形式来表示。链接预测问题主要以分析链接网络结构为主要方法，从而预测一对节点是否会在未来产生链接，或是预测一对节点之间已经存在链接的类型。本文详细介绍了链接预测的任务，并给出了相应的求解方法。

关键词：链接预测；社会计算；用户相似度度量；极性值分类

中图分类号：TP391.41 文献标识号：A 文章编号：2095-2163（2015）05-

Link Prediction Task in Social Network Service

LIU Feng1， LIU Bingquan1， WANG Xiaolong1，2

（1 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China；

2 Graduate School of Shenzhen， Harbin Institute of Technology， Shenzhen Guangdong， 518055， China）

Abstract： With the rapid development of internet techniques， SNS（Social Network Service） becomes many peoples daily life. Most of these different focus SNSs provide many kinds of functions for member interactions. Most of the interaction among members could be represented as link. By analyzing the structure of link network， the link prediction problem aims to estimate the existence or value of the links. In this paper， the details of link prediction task and certain solutions are respectively introduced.

Keywords： Link Prediction； Social Computing； User Similarity Metric； Signed Value Classification

0 引 言

伴随着互联网技术的高速发展，社会网络（SNS，Social Networks Services）也随之兴起并呈现出快速普及态势。目前，各类在线SNS中的注册用户数目已经十分庞大，越来越多的研究者和服务商也开始关注如何为这些用户提供更好的服务。其中为社区内用户之间提供丰富的交互功能（user interaction）就是SNS的一个重要功能，这些用户交互可以利用链接（link）来实现其确立并加以表示。对链接预测相关问题进行深入系统的研究，必将会对社会网络的研究发展有着毋庸置疑的基础性重要意义。

例如Wikipedia、Epinion、Slashdot等网站，即为用户提供了用户生成内容（UGC，User Generated Content）的发布服务，也允许用户之间对彼此发布的内容进行评论、修正与补充。一些网站还采取用户自己选举管理员的方式来进行管理，例如Wikipedia的管理员选举（admin role promotion）。如果使用图来对社会网络进行建模，图中的节点表示用户，以上这些用户行为都可以用节点之间的链接来表示，用户交互的具体内容则可以用链接类型和链接边上的值来表示。包含这种用户或是实体之间链接的数据集，一般称为链接数据或是关系数据。对这些链接数据集进行分析和预测的数据挖掘研究，统称为链接挖掘（link mining）。其中用来处理对象间是否存在链接的预测，以及预测链接类型的研究将可称为链接预测（link prediction）。通过对链接预测相关问题的研究，研究者可以更为精准、全面地对SNS中的用户交互进行建模和分析，从而为其社会成员提供更好的用户体验。

本文首先分析了社会网络的结构特点，以及网络中的数据分布情况。在此基础上，进一步介绍了对于链接存在的预测和链接值的预测这两种常见的链接预测任务，而后又提出了相应的解决方法。

1 社会网络的结构与特点

社会网络是一种“复杂网络（complex network）”[1]，这种网络的拓扑结构表现出不同于一般网络结构的特性。复杂网络中各个元素之间相连接的模式既不是完全有规律可循，也不是完全随机的产生。大部分社会网络还有另外一个特点，就是“无标度（scale-free）”。即任意从网络中选择一个节点，与其有连接的节点数目的统计描述将符合指数法则分布（power-law distribution）。

以Wikipedia的管理员选举的数据为例，用图来表示链接网络，把会员表示为图中的节点，会员之间的管理员选举投票行为用图中的有向链接边来表示，投票的具体内容用链接值表示。基于此，本文随机选择了一个全连通网络，其中包含46个用户以及各用户之间的205条边，利用工具包NodeXL[2]画出网络结构图。如图1所示，图中平均每个节点拥有4.45条边，节点之间的平均距离为1.77。节点的最大度数为11，最小度数为1，除了中间少数节点拥有很高的出入度，大部分节点的度数都较低。

由图1可知，该图中实线表示“支持投票”，虚线表示“反对投票”，该网络中大部分都是正例（支持投票）。这种正负样本不均衡的现象也普遍存在于社会网络中，比如某些商品评价网站中大部分都是相信某人提供的评价，又如某些能标注“朋友”和“敌人”的网络中，大部分的标注都是关于自己的朋友。而在另外的某些网络中，比如共同创作网络，却只存在正例，但其中没有连接边的用户并非一定不会共同创作一篇文章，只是目前还没有共同创作过一篇文章。

为了进一步分析社会网络的结构特点，本文对整个管理员选举数据集中拥有不同度数节点出现的频率进行了统计，如图2所示。从图2中可以明显看出，出现频率高（Y值较大）的节点的度数较小（X值较小），由此可知大部分节点拥有较小的度数，而拥有高度数的节点出现频率则很低。特别是度数达到一定数量的节点出现频率极低，图中几乎平行于X轴且贴近Y=0的点线也反映了这一点。为了方便观察，将图2的X，Y都设定为取10的对数，得到图3。可以看出，图3中的节点度数分布更趋近于线性，说明了在该网络中，节点度数符合指数法则分布。

通过如上分析，可以大致总结社会网络拥有正负例样本分布不均匀，节点度数呈现指数分布等特点。而且在不同的实际环境中，不同应用重点的社会网络都还具有自身的特点。对各类网络进行处理时应该提取相应的特征，并采用合适的方法。这些多样性使得社会计算的各个问题充满了乐趣和挑战。

2 链接存在的预测

2.1 问题描述

预测两个节点是否存在一条链接，是链接预测研究中较早就开始涉及的问题，链接预测（link prediction）的命名也是由此项任务产生。Getoor和Diehl[3]给出的经典链接预测定义为：“通过两个节点的属性和观测到的链接，来预测这两个节点之间是否会存在一条链接”。例如预测社交圈内谁和谁可能会成为朋友，或者预测谁和谁会参与某些事件，例如打电话，发邮件，或是会共同创作一篇文章或是其它一些活动；这类问题的共同特点是，对象属性和部分链接可见，目的是尝试去预测那些不可见的链接存在的可能性，如图4所示。

2.2 常用方法

在研究共同创作（co-author）问题时，Nowell和Kleinberg[4]尝试了多种用户相似度计算方法，并根据相似度的高低来预测两位作者是否会在未来共同创作一篇文章。研究中采用图来表示作者间的创作关系，如图5所示。之后通过节点的自身状态信息和链接分布情况来计算任意两个节点之间的相似度，并排序，相似度高的两个节点则会认定为创作过一篇文章，或是有可能在将来共同创作一篇文章。Dong等[5]列出了多种可用于链接预测的用户相似度计算方法，并进行了比较。

以上的方法主要是基于对用户相似度的度量（user similarity metric）的计算，随着对共同创作问题的深入研究，各种其它特征和基于机器学习（machine learning）方法相继获得采用。Hasan等[6]把这一问题当做一个二分类问题来求解，即假设两个作者间存在一条链接，如果分类器给这条链接的分类值为1的话，就认为这两位作者会在未来共同写一遍文章，0则不会。进一步地，研究者们尝试了多种常用的有监督学习分类模型，包括决策树、K近邻、多层感知器、支持向量机和径向基函数网络。

3 链接值的预测

3.1 问题描述

随着在线社会网络服务的进步，用户可以使用越来越复杂的功能，例如从原来的只能表达“粉，赞”这类正极性链接（positive links），增加到可以表达“黑，踩”等负极性链接。随着这些功能的出现，研究者们也开始研究对负极性链接（negative links）的预测[7，8]。主要研究对象为能提供正、负两种或多种评价、标签等服务的社会网络。例如Slashdot Zoo中的用户直接可以标明对方是朋友（Friend）或是敌人（Foe），又例如Wikipedia等网站允许用户自身选举时的投票预测。以上这些关系，同样可以用图来表示，如图6所示。其中，节点表示用户，每个链接表示用户之间发生过的某种交互、评价或态度，链接边上的值用来表示具体的交互内容。

3.2 常用方法

因为引入了包含负极性值的链接，以及用户行为的有向性，使得链接网络结构变得更加复杂，能提取出的特征也增加了。基于这些数据，研究者们设计了很多方法对用户之间的链接值进行预测。其中一种为将负极性边引入用户相似度度量，Symeonidis和Tiakas[9]将节点负极性度数引入相似度计算，并利用最短路径来计算不直接相连节点之间的相似度。另外一种比较常用的方法是将对链接值的预测转化为分类问题，使用训练集样本的特征训练相应的分类器，再用该分类器来对测试集中两个节点之间的链接值进行预测。Leskovec等[10]使用逻辑斯蒂回归模型来预测两个节点的链接值的极性，具体就是隐去网络中的一条链接边，从其余边提取特称，包括节点的度数和边的链接值。之后使用这些特征训练分类器并进行预测。

随着社会网络服务的功能更加丰富，越来越多的网络可以用包含正、负两种链接的链接网络来建模，Leskovec等[11]将这种网络统称为“极性网络（signed network）”，Agrawal等[12]将正、负极性的链接值称为“链接标签（link label）”。这些研究都使用了逻辑斯蒂回归来预测Epinions（用户信用）、Slasdot（敌友关系）和Wikipedia RfA（管理员选举）的链接网络中的链接值。在分析学习到的模型的同时，研究者们发现发现不少有趣的社会网络现象。最近的研究中，Liu等[13]使用基于深度置信网络的深度学习方法，进一步提升了对极性网络中链接极性值的预测性能。

4 结束语

社会网络中链接预测的方法和应用研究，由最原始的对链接存在预测为开端发展至今，其研究框架日趋清晰，各关键问题的研究逐步深入，研究方向和应用领域也越发广泛。链接预测主要任务包括对链接存在的预测和链接值的预测，而且对链接存在的预测也可以看成一种预测链接值是否为正极性的情况，所以某种程度上可以说链接预测最根本的研究还是对链接值的预测。解决链接预测任务的方法可以归结为基于用户相似度度量，以及基于分类器的链接极性值分类两大种类。前者在需要较少的计算开销前提下能提供可以接受的结果，后者借助于机器学习方法提供较高的准确率。

参考文献：

[1] BOCCALETTI S， LATORA V， MORENO Y， et al. Complex networks： Structure and dynamics[J]. Physics reports， 2006， 424（4）：175–308.

[2] SMITH M A， SHNEIDERMAN B， MILIC-FRAYLING N， et al. Analyzing （social media） networks with NodeXL[C]//Proceedings of the fourth international conference on Communities and technologies. New York， NY， USA： ACM， 2009：255–264.

[3] GETOOR L， DIEHL C P. Link mining： a survey[J]. ACM SIGKDD Explorations Newsletter， 2005， 7（2）：3–12.

[4] LIBEN-NOWELL D， KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American society for information science and technology， 2007， 58（7）：1019–1031.

[5] DONG L， LI Y， YIN H， et al. The algorithm of link prediction on Social Network[J]. Mathematical Problems in Engineering， 2013（1）：1-7.

[6] AL HASAN M， CHAOJI V， SALEM S， et al. Link prediction using supervised learning[C]//SDM06： Workshop on Link Analysis， Counter-terrorism and Security. Philadelphia， PA， USA： SIAM， 2006：1––10.

[7] HSIEH C J， CHIANG K Y， DHILLON I S. Low rank modeling of signed networks[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. New York， NY， USA： ACM， 2012：507–515.

[8] TANG J， CHANG S， AGGARWAL C， et al. Negative link prediction in social media[C]//Proceedings of the Eighth ACM International Conference on Web Search and Data Mining. New York， NY， USA： ACM， 2015：87–96.

[9] SYMEONIDIS P， TIAKAS E. Transitive node similarity： predicting and recommending links in signed social networks [J]. World Wide Web， 2014， 17（4）：743–776.

[10] LESKOVEC J， HUTTENLOCHER D， KLEINBERG J. Predicting positive and negative links in online social networks[C]//Proceedings of the 19th international conference on World wide web. New York， NY， USA： ACM， 2010：641–650.

[11] LESKOVEC J， HUTTENLOCHER D， KLEINBERG J. Signed networks in social media[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. New York， NY， USA： ACM， 2010：1361–1370.

[12] AGRAWAL P， GARG V K， NARAYANAM R. Link label prediction in signed social networks[C]//Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. Palo Alto， CA， USA： AAAI Press， 2013：2591–2597.

[13] LIU F， LIU B， SUN C， et al. Deep belief network-based approaches for link prediction in signed social networks[J]. Entropy， 2015， 17（4）：2140–2169.