基于流行度制衡的微博用户相似度计算方法

覃 俊，李 欢，周 磊

(中南民族大学 计算机科学学院， 武汉 430074)

基于流行度制衡的微博用户相似度计算方法

覃 俊，李 欢，周 磊

(中南民族大学 计算机科学学院， 武汉 430074)

以微博用户推荐算法中相似度计算为研究对象，根据微博用户关注信息的特点，分析了关注用户的流行度的不同程度，以及这种程度差异对相似度计算产生的影响，在此基础之上提出了一种加入流行度制衡因子的相似度计算方法.可通过流行度制衡因子，在计算用户相似度时，适度减少(增加)流行度偏高(偏低)的用户对计算结果的影响.实验结果表明：加入流行度制衡因子的用户相似度计算具有更好的推荐效果.

微博；个性化推荐；用户相似度；流行度制衡

随着互联网的飞速发展，以新浪微博、Twitter等为代表的社交媒体微博服务因具有及时、便捷、受众面广等独特的传播优势而成为一种主要的社交网络形态[1].然而，即时性的信息分享作为微博的独特之处[2，3]，在服务用户的同时也导致了信息的泛滥成灾.

作为解决信息爆炸问题渠道之一的个性化推荐系统，因可帮助用户在这些过载的信息中找到与自己兴趣相投的用户，并定位到自己感兴趣的信息而受到国内外学者的广泛关注.研究主要集中在以下两个方面：一方面是基于用户所发微博内容的推荐方法，另一方面则是基于微博用户社会关系的推荐方法.基于微博内容的推荐方法主要通过提取用户所发的微博文本，研究文本内容之间的相关性以进行兴趣定位，进而对微博用户进行推荐[4-7].而基于社会关系的推荐方法主要集中在如何更好的运用微博用户间的社会关系，以提升推荐效果[8-14]．其中Lin等[15]学者通过对Beehive网络中用户链接关系及链接内容进行研究，挖掘其在进行推荐中的作用，发现通过分析用户之间的链接信息对用户进行推荐，对推荐结果的准确性更具有帮助.即在对微博用户进行用户推荐时，基于微博用户社交信息的推荐算法比基于用户内容信息的推荐算法效果更好[16,17].另一方面，较之于利用内容相关性来推荐用户，利用微博用户社交信息进行推荐，可以大大减少微博上数据稀疏性问题对推荐准确性的影响[18].

鉴于此，本文主要研究在微博用户社交关系推荐中最为关键的用户相似度度量方法.根据微博用户关注信息的特点，围绕用户的流行度，探讨其对用户相似度计算的不同影响，提出流行度制衡因子，进而改进原用户相似度的计算方法，并在此基础上进行微博用户推荐的实验.

1 相关工作

当前基于用户社交信息的推荐算法，其核心部分在于根据已有信息计算用户之间的相似度.对于微博这类由“关注”与“被关注”这种单向链接形成社交网络，一般采用以下3种方式计算用户相似度.

(1)基于关注对象的用户相似度.微博平台中用户会对其感兴趣的对象进行关注操作，通过计算微博用户之间相同关注对象的比例，可以度量用户与用户之间的兴趣倾向相似程度.公式表示如下:

(1)

如公式(1)所示，out(u)为微博类社交网络中微博用户所关注的对象的集合，即被微博用户u所指向的其他微博用户的集合.Sim(u，v)的计算方法实际上是利用微博用户间共同关注的对象的比例，即基于出度(Out Link)的方法.该指标用于度量微博用户共同关注对象的比例，当Sim(u，v)值越大，说明该两用户所关注的用户集合的相似程度越大，同时也说明他们之间相互感兴趣的概率越高.

(2)基于粉丝的用户相似度.对于微博类社交平台来说，用户的兴趣方向是双向的，其中用户的粉丝(关注用户的人)也能从其他角度反映该用户的兴趣取向.基于粉丝的用户相似度计算公式所采用的方法是：以用户之间的粉丝的集合来表示用户的特征向量，通过计算粉丝之间的相似性来衡量用户的兴趣倾向.

(2)

如公式(2)所示，Sim(u，v)采用的是入度(In Link)的方法，即以粉丝的集合来表示用户的兴趣特征向量，也就是C矩阵中相应的列向量.其中，in(u)对应的为微博类社交网络平台中该微博用户u的粉丝对象的集合，即指向该微博用户u的其他用户的集合.Sim(a，b)用来度量同时对微博用户a、b感兴趣的用户的比例，当Sim(u，v)越大，说明共同关注了这两个微博用户的其他用户的集合的相似程度越大，进而可以说明两者的兴趣越接近.

(3)基于链接对象的用户相似度.以上两种相似度分别从用户的出度与入度两个方面分别进行衡量，即sim(u,v)=sim(v,u).考虑到关注的方向性，基于链接对象重合度的计算公式则是通过计算潜在朋友形成链路的概率大小来衡量用户之间的兴趣相似度.

(3)

如公式(3)所示，Sim(u，v)通过度量用户u的关注用户中同时也关注了用户v的比例，以此判断u与v的兴趣相似度.

以上三种相似度计算公式为当前社交网络中计算用户相似度的主要公式.在徐志明等[17]的研究中，通过将微博用户的社交信息中关注信息、粉丝信息以及两者相结合的综合社交信息等进行分析研究并通过系统性的实验，得出在对微博用户进行关系分析时，以上众多信息中基于微博用户关注信息的分析最具有价值，与此同时基于微博用户关注信息计算出的用户相似度也最能表示用户的兴趣倾向.

鉴于此，本文主要研究对象即为微博用户关注信息的相似度计算，根据研究微博用户关注信息的特点，改进基于用户关注信息的相似度计算公式.

2 改进的相似性计算方法

2.1 问题描述及分析

当前，基于微博平台的用户推荐算法，其根本目的主要是为用户推荐合适的好友，以扩展其朋友圈子.其核心即计算用户关注或被关注信息的相似度.但是此类推荐算法在对微博用户进行基于关注信息相似度计算时，并未分情况进行处理.即不论用户关注对象是流行度较高(即关注链接较多)的用户，还是用户的现实生活中的好友，对用户相似度计算的影响都是一样的.但现实生活中并非如此.

在现实生活中，微博平台上存在着大量这样的微博用户，他们大多数在关注自己线下的好友或真正感兴趣的用户的同时，为广泛接受新的信息或参加线下活动，还盲目添加了大量的热门主题或明星用户.这些被用户添加的热门主题及用户往往并不能准确地体现微博用户的兴趣所在.相反，微博用户对较为冷门的用户或主题节点的添加，从某些角度来说更能反映用户真正的兴趣所在.

综上分析，本文提出一个新的观点或者思路：在计算基于用户关注信息相似度时，对于流行度高、关注链接较多的用户，对用户的相似度贡献值应小于流行度较低、关注链接较少的用户.

2.2 相关概念与定义

上面提到，一般用户的关注信息中，存在着许多与用户潜在兴趣用户或线下熟识好友无关的热门主题与明星用户，在计算基于用户关注信息的相似度时，因为大量用户都会对这些明星用户进行关注，从而影响传统余弦相似度计算公式计算出的相似度的准确性.本文提出一种基于用户关注信息的改进的相似度计算公式.在介绍该改进公式之前，首先介绍相关的概念与定义.

(1) 用户集.对于整个微博网络中的N个用户，其用户集U={u1,u2,u3,…,uN}.

(2) 兴趣矩阵.对于每个用户ui，对应着其兴趣向量vi=(a1,a2,a3,…,aN)，这些微博用户的兴趣特征向量的集合即构成了一个N×N的用户兴趣矩阵C.矩阵C中的任一元素cuiuj都表示着用户ui对用户uj的兴趣程度，在本文中用0和1进行度量.即当cuiuj=1时表示用户ui关注了用户uj，即用户ui为用户uj的粉丝；当cuiuj=0时则表示用户ui并未关注用户uj.

(3) 社交信息.对于微博用户的兴趣矩阵C进行分析可以得到微博用户的社交信息Relation：

Relation= { Relation(ui) |ui∈U} .

(4)

对于任一用户ui其社交信息Relation(ui)表示为：

Relation(ui) = { Followee(ui), Follower(ui) }，

(5)

其中Followee(ui)与Follower(ui)分别表示用户ui的关注信息与粉丝信息.具体表示如下：

Followee(ui)={cuiuj=1|ui∈U,uj∈U,i≠j}，

(6)

Followee(ui)={cujui=1|ui∈U,uj∈U,i≠j}.

(7)

(4) 流行度制衡因子.对于任意一微博用户a，其流行度制衡因子为：

(8)

其中N为微博网络中的总用户数，Followee(a)为上文提到的用户a的粉丝集.通过制衡因子α，在计算用户相似度时，降低流行度较高/提高流行度较低的用户对计算结果的影响.理论上当某一用户关注数无限趋近于总用户数时，该用户的流行度制衡因子α即可取到0值；而当用户无粉丝信息时，其流行度制衡因子α趋于无穷大.但实际应用中用户粉丝数至少为1，因该用户如无任何粉丝信息，则不会出现在基于用户关注信息的相似度计算中，因此流行度制衡因子α的取值范围为[0，lnN].

(5) 基于用户关注信息的改进的相似度计算公式：即加入了公式(8)中流行度制衡因子的余弦相似度计算公式.对于任意两个微博用户u与用户v，其基于用户关注信息的改进的相似度计算公式为：

(9)

其中流行度制衡因子α(a)的作用为：对于用户u与用户v同时关注的、具有大量粉丝(入度)的用户节点进行制衡.即该微博用户a的粉丝(入度)越多，则对同时关注了它的两个用户进行关注相似度计算时，用户a对该计算结果的贡献越小.同理，当微博用户u与用户v同时关注较为冷门的用户时，受该关注行为的影响，他们在基于关注信息的相似度计算时所获得的值更大，他们在现实生活中熟识或相互感兴趣的可能性也就越大.

考虑到完整性，这里根据改进的相似度计算公式，给出了考虑用户流行度制衡的推荐PBR算法的完整框架，算法描述如下：

输入：微博用户的兴趣矩阵C，待推荐的微博用户u以及推荐个数N

输出：推荐结果列表L

① 根据微博用户的兴趣矩阵C，得到用户的社交信息Relation.

② 根据用户的社交信息Relation,通过使用加入流行度制衡因子的相似度计算公式，进行微博用户间的相似度计算，得到微博用户基于关注信息的相似度矩阵S：

(10)

③ 根据微博用户基于关注信息的相似度矩阵S，利用考虑相似度传播后的最终用户相似度的计算公式对其进行计算，得到经过相似度传播后的综合相似度矩阵S：

Sim(u,v)=(1-β)×simα(u,v)+β×

(11)

④ 根据得到的经过相似度传播后的综合相似度矩阵S，对待推荐用户u与其他微博用户的综合相似度进行从高到低的排序，得到对推荐用户u的排序结果R.

⑤ 按照排序结果R，取前N个用户数据，产生最终的推荐结果列表L.

3 实验部分

3.1 数据来源

根据本文实验需要，文中所使用的实验数据主要为数据堂(清华大学)采集的新浪微博平台的微博用户数据.该数据集主要包含了新浪微博用户、其关注列表以及其关注列表中用户总量.数据采集时间范围为2013年11月至2013年12月.采集方式为通过以10个相邻的用户节点为种子节点，通过用户的关系链往外进行扩散，每次抓取与当前用户相邻的用户节点，并不断进行迭代，最后获得本实验的微博用户数据集合.通过该方式获取的用户因基本属于较为相近的兴趣圈，故可保证不会因实验数据集中用户的连接信息过于稀疏，以致无法准确衡量算法的推荐效果.该数据中包含11994个微博用户数据，其平均关注用户数为60户左右.

本文实验对该数据集合中每个用户的所有关注关系进行随机的划分：对于每个用户，选择70%的关注关系作为训练集，30%的作为测试集.以对本文算法进行实验.实验参照的算法为以下两算法.

(1) TSR算法 (Two-Stage Recommendation，简称为TSR算法)[11].该算法是一种采用两阶段用户推荐模型的推荐算法.其中的用户相似度计算公式为前文提及公式(1)，该用户相似度计算公式并未区分用户的不同.因该算法在当前基于用户社交信息相似度的推荐算法中使用较广，具有显著的推荐效果，因此作为本文的参照算法之一.

(2)“Friend-of-Friend”算法[22].选取“Friend-of-Friend”算法作为其中一个对比算法，是因为该算法是一种基于强链接关系的推荐算法，应用较广.其基本思想为：假设A与B的好友列表中有很大的交集部分，则可以认为A与B成为好友的可能性较大.其中，将本微博数据中的互相关注的用户关系作为原“Friend-of-Friend”中度量的好友关系.

3.2 实验结果

通过为微博用户进行TopN推荐，期间选取不同的N值与本文的PBR算法、原TSR算法中基于关注信息的推荐算法，以及“Friend-of-Friend”算法进行实验对比，以验证本文的PBR算法的推荐性能.实验设置如下：设置Top-N中推荐个数N={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}，参数β分别选取为0.4与 0.6，数据集中的微博用户数量为1000.选取的实验指标为Fmeasure[23]，其公式表示如下：

(12)

其中，recall与precision分别为算法的召回率与准确率，其公式分别表示如下：

(13)

(14)

其中，TestSetHits表示推荐结果中相关用户数，Recommendations表示总推荐用户数，TestSet表示目标用户的测试集中的所有关注用户总数.公式(13)中的precision指标用来衡量推荐算法推荐的准确性，该指标的值越大，证明推荐列表中与用户相关的用户数越大，则算法准确性越高.公式(14)中的recall用于衡量算法挖掘到相关用户占总相关用户的比例.召回率越大，则推荐算法推荐列表中相关用户所占比例也就越高.而Fmeasure作为将这两个指标综合考虑而得到得指标，可用来衡量算法的综合性能.该指标的最后实验结果越大则说明算法的综合推荐性能越好，因此作为本实验的评价指标.

最终实验结果图1所示.图1(a)(b)(c)(d)分别描述了3个算法在不同参数取值β下用户推荐结果的Fmeasure指标曲线.Fmeasure反映的是根据准确率与召回率得出的算法的综合推荐性能指标.如图1(a)所示，当参数β取值为0.2且推荐个数较少时，本文提出的PBR算法与TSR算法的Fmeasure略低于“Friend-of-Friend”算法.但随着推荐用户数的增加，这两个算法的Fmeasure指标逐渐上升并超过“Friend-of-Friend”算法.同时随着参数取值β的增加，PBR算法与TSR算法的Fmeasure值也随之增大，即算法的综合推荐效果随着参数β的增大也得到了一定的提高.如图1(b)(c)(d)所示，当参数β取值为大于0.2后，PBR算法与TSR算法的Fmeasure值曲线整体基本都在“Friend-of-Friend”算法之上，即前两种算法的综合推荐性能要优于“Friend-of-Friend”算法.

图1 算法的Fmeasure指标曲线Fig.1 Fmeasure curve of the algorithm

而对于PBR算法与TSR算法，从图1所示的在不同参数β下算法的Fmeasure指标曲线图可以看出，PBR算法的Fmeasure值曲线整体上都在原TSR算法的Fmeasure值曲线之上，即本文提出的PBR算法的综合推荐性能明显优于原TSR算法.同时从图1中PBR算法的Fmeasure指标曲线图可以看出，在该实验数据集上当参数β取0.8且为用户进行Top10推荐时，PBR算法的综合推荐性能最好.

3.3 实验结论

通过对PBR算法、TSR算法以及“Friend-of-Friend”算法这3个算法在Fmeasure评价指标上的实验，可以得出以下结论.

(1)“Friend-of-Friend”算法在微博平台进行用户推荐时，因其只考虑强关系进行推荐的缘故，当推荐用户数目较少时，能快速为用户找到其感兴趣的用户，但随着推荐个数扩大，因未考虑到用户的弱连接对其兴趣的体现，导致该算法在为用户进行潜在兴趣用户的寻找时能力是十分有限的.这也说明了对于微博这类单向兴趣连接的社交网络平台，仅仅考虑强连接用户进行推荐，推荐效果并不理想.

(2)从TSR算法与基于本文思想提出的PBR算法的实验结果可以看出，虽然当推荐数目逐渐增大时，两算法的推荐准确率渐渐接近，但从整体上来看PBR算法较之于TSR算法，具有更好的推荐效果.即本文考虑了流行度制衡的改进算法为用户找到其潜在感兴趣的用户的能力，明显强于TSR算法.

(3)同时从算法推荐性能的相关实验可以看出，当参数β取值增大时，可提高PBR算法与TSR算法的准确率.因而可说明在计算用户相似度时，考虑待推荐用户的关注信息，对于提高算法的推荐准确率具有一定的帮助，取值的最佳范围可根据具体运用的数据集进行测试选取.

综上，在微博平台进行基于社交网络图的用户推荐时，应考虑用户之间的单向兴趣连接.与此同时这也验证了在计算用户关注信息相似度时，考虑对其进行流行度制衡的改进算法可以有效地可提高推荐准确率.本文提出的基于该思想的PBR算法，可以更为有效的挖掘出用户潜在的兴趣用户.

4 结语

本文主要研究微博用户社交关系中关注信息对用户推荐的影响，针对当前微博平台中，用户关注信息相似度计算方法上存在的问题，进行了分析与改进，定义了流行度制衡因子，并在此基础之上提出了一种改进的基于用户关注信息的相似度计算方法.

通过将本文所提出的改进应用在新浪微博用户数据集上进行用户推荐实验，验证了本文方法的有效性.证明了较之于其他两种算法，运用了本文改进的相似度计算方法的PBR推荐算法，在对微博平台进行用户推荐时，具有更好的推荐效果.

本文提出的PBR算法，与基于传统相似度计算公式的推荐算法相比，有两个明显的优势：(1)更容易发现微博用户的潜在兴趣用户.本文的PBR算法在利用了微博用户关注信息进行用户推荐的同时，区分了因用户流行度不同而对相似度计算的影响，即在计算用户相似度时，降低流行度较高/提高流行度较低的用户对计算相似度结果的贡献，以达到制衡因各用户的流行度不同而对相似度计算结果的影响.(2)本文的方法在进行微博用户推荐时，仅通过微博用户链接情况反映出的关注信息进行用户相似度的计算，在一定程度上减少了因数据稀疏性问题对算法的推荐效果的影响，可以较好地保证算法性能的稳定.

当然，与一般的基于用户网络图的算法相同，本文提出的PBR算法的推荐效果同样也受用户建立的社交关系质量的影响.比如，如果微博用户所添加的关注链接信息，并不能准确地描述用户的兴趣倾向，那么，通过本算法得到的推荐结果，可能与微博用户真正的兴趣没有较好的相关性.另外，因本文提出的PBR算法的相似度计算建立在用户已有的关注链接上，故对发现用户之前尚未添加的、新的兴趣类型的能力不足.

下一步我们的研究重点将针对微博用户信息中的其他用户信息，例如用户背景基本信息、用户所发微博文本内容信息以及用户交互信息等有效信息.研究如何对这些信息进行综合分析，并与本文研究的用户关注信息进行结合运用，以计算用户的相似度，更好地度量用户的兴趣倾向，以减少该算法受用户建立的社交关系质量的影响程度.

[1] Gao Q, Abel F, Houben G J, et al. A comparative study of users′ microblogging behavior on Sina Weibo and Twitter[M]. Berlin: Springer, 2012: 88-101.

[2] 喻国明，欧 亚，张佰明,等. 微博：一种新传播形态的考察--影响力模型和社会性应用,互联网络[M].北京:人民日报出版社,2011:24-28.

[3] 李 熙.基于六度分割理论和中心度识别微博网络的关键人物[D].成都:西华大学.2013:5-7.

[4] Bogers T, Björneborn L. Micro-serendipity: Meaningful coincidences in everyday life shared on Twitter[J]. iConference 2013, 2013: 196-208..

[5] Hannon J, McCarthy K, Smyth B. The pursuit of happiness: searching for worthy followees on[J]. Computer Networks and ISDN Systems, 1998, 30(1-7): 107-117.

[6] Hannon J, McCarthy K, Smyth B. Finding useful users on twitter: twittomender the followee recommender[M]. Berlin: Springer, 2011: 784-787..

[7] Armentano M G, Godoy D, Amandi A. Topology-based recommendation of users in micro-blogging communities[J]. Journal of Computer Science and Technology, 2012, 27(3): 624-634.

[8] Armentano M G, Godoy D, Amandi A. Topology-based recommendation of users in micro-blogging communities[J]. Journal of Computer Science and Technology, 2012, 27(3): 624-634.

[9] Massa P, Avesani P. On the move to meaningful internet systems 2004: CoopIS, DOA, and ODBASE[M]. Berlin: Springer, 2004:492-508.

[10] Yuan W, Guan D, Lee Y K, et al. Improved trust-aware recommender system using small-worldness of trust networks[J]. Knowledge-Based Systems, 2010, 23(3): 232-238.

[11] 张中峰,李秋丹.社交网站中潜在好友推荐模型研究[J].情报学报, 2011：30(12): 1319-1325.

[12] Lekakos G, Giaglis G M. Improving the prediction accuracy of recommendation algorithms: approaches anchored on human factors[J]. Interacting with computers, 2006, 18(3): 410-431.

[13] 牛庆鹏.博客潜在朋友推荐技术的研究[D].沈阳:东北大学,2009:37-51.

[14] Recht B, Fazel M, Parrilo P A. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J]. SIAM review, 2010, 52(3): 471-501.

[15] Lin K Y, Lu H P. Why people use social networking sites: an empirical study integrating network externalities and motivation theory[J]. Computers in Human Behavior, 2011, 27(3): 1152-1161.

[16] Yang L, Smola S. Zheng Zha. Like like alike: joint friendship and interest propagation in social networks[J]. WWW-11, 2011: 12.

[17] 徐志明,李 栋,刘 挺,等.微博用户的相似性度量及其应用[J].计算机学报,2014,37(1):207-218.

[18] Lerman K, Ghosh R. Information contagion: an empirical study of the spread of news on Digg and Twitter social networks[J]. ICWSM, 2010, 10: 90-97.

[19] 杨 晶, 杨长春, 丁 虹. 一种改进的新浪微博好友推荐算法[J]. 常州大学学报：自然科学版, 2013, 25(3):66-70.

[20] 荣辉桂, 火生旭, 胡春华，等. 基于用户相似度的协同过滤推荐算法[J]. 通信学报, 2014(2):16-24.

[21] 唐晓波, 祝 黎, 谢 力. 基于主题的微博二级好友推荐模型研究[J]. 图书情报工作, 2014(9):105-113.

[22] Madge C, Meek J, Wellens J, et al. Facebook, social integration and informal learning at university:′It is more for socialising and talking to friends about work than for actually doing work′[J]. Learning, Media and Technology, 2009, 34(2): 141-155.

[23] Linden G, Smith B, York J. Amazon. com recommendations: Item-to-item collaborative filtering[J]. Internet Computing, IEEE, 2003, 7(1): 76-80.

Similarity Computing Method Based on the Micro-Blog User′s Popularity Depression

QinJun,LiHuan,ZhouLei

(College of Computer Science and Technology, South-Central University for Nationalities, Wuhan 430074, China)

This paper aims to improve the performance of micro-blog users′ recommendation algorithm whose key issue is user similarity calculation. This paper firstly introduces current several user similarity calculation methods and their shortcomings. And then, based on the characteristics of micro-blog users, we discuss their concerning users′ popularity of different level, which aims to explore their effects on the user similarity calculation. And on this basis, an improved similarity calculating method of considering depression factor is proposed. In the user similarity calculation, popularity balance factor can reduce/increase the impact of calculation results caused by the user high/low popularity. The experimental results indicate that the proposed user similarity calculation method has better recommendation results.

micro-blog; personalized recommendation; user similarity; popularity depression

2015-08-01

覃 俊(1968-)，女，博士，教授，研究方向：智能优化、数据挖掘、信息安全，E-mail: 498011695@qq.com

湖北省自然科学基金资助项目(2011CDB416)

TP393.092;TP391.3

A

1672-4321(2015)03-0088-07