基于用户质量的关注关系预测

李旺龙，李川

（四川大学计算机学院，成都 610065）

基于用户质量的关注关系预测

李旺龙，李川

（四川大学计算机学院，成都 610065）

链接预测是当前信息网络研究中的热点问题，旨在关注如何通过已知的网络结构等信息预测网络中尚未产生连边的两个节点之间产生链接的概率，链接关系包含好友关系、follow关系、@关系。提出基于用户质量的关注关系链接预测的新方法LPR，基于真实数据的实验表明，LPR方法较基于局部信息相似性和路径相似性的方法，有较大的提升。

用户质量；相似性；链接预测；微博

0 引言

微博中的链接关系包含好友关系、follow关系、@关系等。这些关系均为有向关系，可表示为一个有向图。微博是一种典型的异构信息网络[1]。用户和微博可看作网络中的节点，用户间、用户与微博间可有不同类型的链接关系。链接预测是当前信息网络研究中的热点问题，旨在关注如何通过已知的网络结构等信息预测网络中尚未产生连边的两个节点之间产生链接的概率[2]。链接预测在不同的场景中有不同的应用和价值。例如，在犯罪分子网络中，链接预测可用来发现潜在的犯罪分子；在社交网络中，链接预测可指示用户间建立好友关系的可能性，为用户提供好友推荐。另外，链接的产生隐含着网络结构的演化，抓住链接关系产生规律往往能揭示网络的演化趋势。

常用的链接预测方法多是基于节点相似性进行链接预测，这些相似性包括用户属性相似性[3]、局部拓扑结构相似性[4]和路径相似性[5]等。节点间的相似性越高，链接关系的产生概率越大。然而，在微博这类在线社交网络中系统，仅凭借相似性很难刻画用户间链接关系产生的普遍规律。这主要因为：

（1）网络中的信息传播[6]会对链接关系的产生有巨大影响，微博中用户链接关系的产生往往是基于微博的发出与转发，微博被转发的次数与该微博的发出者被其他用户看到的概率成正比。

（2）社会学中的重要规律现象，如马太效应[7]、二八定律[8]等，很难用相似性简单表征。在社会网络中占据较多资源或者处于较核心地位的人，会利用资源优势扩充自己的资源。对微博中的链接关系而言，粉丝较多的用户，会吸收更多的粉丝。

本文针对上述问题进行了研究，提出微博异构信息网络中用户链接关系的预测新算法LPR（Link Prediction Regression）。该算法利用逻辑回归（Logistic regression）[10]方法计算链接关系产生的概率。

1 问题定义

定义G（V；E；P）为一个属性图，其中V为节点集合，E为有向边集合，P为节点和边的属性集合。网络总节点数为N，边数为M。网络共有N*（N-1）条有向边，即全集U。通过一种链路预测的方法，对节点对（x,y）∈（UE）所表示的有向边赋予一个分数值Sxy，分值越大表示有向边产生的概率越大。

针对微博异构信息网络，可描述为：设G（V；E；P）为一个微博属性图，其中V为节点集合，包括微博和用户这两类；E为有向边的集合，包括用户与微博的链接关系（用户发微博、用户转发微博）以及用户与用户的链接关系（关注）；P为各类节点与连边的属性。预测不存在的链接关系（用户与微博，或者用户与用户）产生的概率。

2 预测算法LPR

2.1 数据处理

King-wa Fu[11]的研究表明在微博系统中存在大量的“僵尸用户”。这些“僵尸用户”多为营销公司注册，用来操纵关注人数获取利益。这类用户通常会关注大量用户或者关注用户数远大于其粉丝数。另一类是活跃度较低的用户，这类用户很少使用微博，通常关注的用户很少。本文将这两类用户看作噪声用户。为减少噪声用户对链接预测方法的影响，对用户进行过滤显得十分必要。过滤条件如下：

（1）过滤关注人数小于5或者关注人数大于800的用户。

（2）过滤关注人数大于粉丝数20倍的用户。

（3）过滤前两步处理后PR值较小的1%的用户。

2.2 特征定义

在微博这种弱关系网络中，用户间以相同的兴趣聚合在一起，两个用户间共同关注的用户数，可表征这两个用户兴趣的相似性；而两用户共同粉丝数，则可表征在其他用户眼中他们的相似性。Jaccard[4]系数，在考虑共同邻居的同时也考虑了这两个用户的所有邻居，能较合理地刻画两个用户的结构相似性。

通常用路径相似性来衡量网络中两个节点之间关系的强弱。设网络中的两个节点x和y，要衡量x到y这条链接关系的强弱，可以通过计算网络中从x经过任意一个中间节点z到达y的路径的条数。

在信息传播理论当中，网络中的核心节点往往占有更多的资源，即二八定律。在微博网络中，一些权威或影响力较高的用户往往会拥有更多的粉丝。他们所发的微博会被更多其他用户转发。从而有了更多机会被其他用户关注，即会产生马太效应。因此，对于一条待预测的用户链接关系，两个用户会具有不同的影响力和权威值，他们的影响力和权威值，对这条链接关系会产生一定的影响

定义（用户质量）（User Quality）设T表示用户发出的微博数，R表示用户被转发的微博数，L表示用户发出的包含链接的微博数，PR为用户在微博系统中的PR值，则用户质量可表示为：

2.3 预测模型

在LPR中，利用逻辑回归可以计算出一条链接关系产生的概率P。将概率大于阈值θ的链接关系预测为将会产生，否则预测为不会产生。逻辑回归的一般性表示如下：

决策边界：

损失函数：

其中m为训练集的大小，n为回归参数的数量，x（i）为第i个训练数据，θj为第j个回归参数，λ为正则化参数。优化求解时，采用随机梯度下降法（SGD，Stochastic Gradient Descent）。由此，得到LPR算法具体过程为：

（1）按2.1节的方法过滤后网络中边的集合为E。

（2）随机抽取若干网络中的链接ET作为正例。

（3）随机抽取若干不存在于网络中的链接EF作为负例。

（4）在E-ET-EF的网络中计算ET∪EF中所有节点的特征以及链接的特征，并将节点的特征转换为链接关系的特征，最终链接关系的特征集为X。

（5）将EF∪ET分为训练集、验证集和测试集。

（6）在训练集上训练模型，在验证集上选择使预测结果最优的模型超参数（θ、λ、SGD百分比和SGD学习率），得到最终模型hθ（x）和阈值θ。

（7）将测试集中任意一条链接关系代入模型，即可得到该链接关系产生的概率P。当P＞θ时，预测该链接关系将会产生，否则，预测该链接关系不会产生。

3 实验

为衡量LPR算法的有效性，本文选取了真实的微博数据，主要包括关注关系和微博信息数据，并与基于局部结构相似性和路径相似性的链接预测方法进行比较。在LPR中模型的训练与验证阶段，先按在验证集上F-Score最大的得到2.3节提到的超参数，再将学习率缩小为原来的一半，迭代不同的次数得到验证集上不同的F-Score，如图1所示。

在计算基于局部结构相似性时，定义两个节点的局部结构相似性为他们入度和出度方向Jaccard系数的平均值。即：

在计算基于路径的相似性时，直接选取2.2节计算节点关系强度的特征，定义为TwoStep。在测试集上，LPR、SS与TwoStep的准确率，召回率以及F-Score比较如图2所示。

图1 LPR算法性能

可以发现，LPR较SS和TwoStep有明显效果提升。其主要原因在于社交网络具有高度稀疏性，绝大多数用户间都没有共同好友或好友间二步之内不可达，LPR综合了结构相似性与路径相似性作为特征并且额外加入起点和终点用户质量作为特征，更细致地刻画了用户间链接关系的产生因素。

4 结语

本文基于信息传播的理论，提出在微博这种异构信息网络中的用户质量度量，且提出了预测微博中用户间链接关系产生的方法——LPR。链接预测是一个有广泛应用场景的研究问题，不同的场景对应不同的异构信息网络。在不同的异构信息网络中，节点和边的特征会有很大不同。传统基于相似性的方法，在解决链接预测问题时，存在较大的局限性和主观性。而LPR方法，综合基于相似性的特征和用户质量。实验结果证实了该方法的可行性与有效性。

图2 SS、TwoStep与LPR效果比较

[1] Han J.Mining Heterogeneous Information Networks:the Next Frontier[C].Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2012:2～3

[2] 吕琳媛.复杂网络链路预测[J].电子科技大学学报,2010,39（5）:652

[3] Lin D.An Information-Theoretic Definition of Similarity[C].ICML.1998,98:296～304

[4] Jaccard.http://en.wikipedia.org/wiki/Jaccard_index#References

[5] Zhou T,Lü L,Zhang Y C.Predicting Missing Links Via Local Information[J].The European Physical Journal B,2009,71（4）:623～630

[6] 徐玉萍.网络信息传播规律研究[J].图书馆学研究,2010（6）:14-17.

[7] Merton R K.The Matthew Effect in Science[J].Science,1968,159（3810）:56～63

[8] Pareto_principle http://en.wikipedia.org/wiki/Pareto_principle

[9] Brin S,Page L.The Anatomy of a Large-Scale Hypertextual Web Search Engine[J].Computer Networks and ISDN Systems,1998,30（1）:107～117

[10] 李航.统计学习方法[M].北京：清华大学出版社,2012

[11] Fu K,Chau M.Reality Check for the Chinese Microblog Space:a Random Sampling Approach[J].PLoS ONE,2013,8（3）:e58356

Attention Link Prediction Based on User Data Quality

LI Wang-long，LI Chuan
（College of Computer Science,Sichuan University,Chengdu 610065）

Link prediction is one of the most heated topics in information network research,which mainly concerns how to predict the probability of new links between different pairs of nodes,including friends,follow,@relationship,etc.Proposes a new method LPR for links prediction in the micro-blog information networks.Experiments of the real data show that the LPR method is far better than methods which are based on local information similarity and path similarity.

User Data Quality;Similarity;Link Prediction;Micro-Blog

1007-1423（2015）03-0003-04

10.3969/j.issn.1007-1423.2015.03.001

李旺龙（1990-），男，湖北孝感人，硕士，研究方向为数据挖掘、分布式计算

李川（1977-），男，河南郑州人，博士，副教授，硕士生导师，研究方向为数据库、数据挖掘

2014-12-25

2015-01-10

国家自然科学基金（No.61103043）、国家“十二五”科技支撑计划项目（No.2012BAG04B02）、武汉大学软件工程国家重点实验室开放基金项目（No.SKLSE2012-09-26）