一种基于相似社团和节点角色划分的社交网络用户推荐方案
2016-08-06钟晓宇刘宴兵肖云鹏
钟晓宇，刘宴兵，肖云鹏
(重庆邮电大学 网络与信息安全技术重庆市工程实验室，重庆 400065)
一种基于相似社团和节点角色划分的社交网络用户推荐方案
钟晓宇，刘宴兵，肖云鹏
(重庆邮电大学 网络与信息安全技术重庆市工程实验室，重庆 400065)
摘要：针对现有的社交网络用户推荐方案中主要考虑个体相似性问题以及节点角色无层次差别的问题，提出一种基于相似社团和节点角色划分的推荐方案。在传统的用户相似度计算基础上，从社团结构和属性两方面，综合考虑社团间联系的紧密程度和社团用户兴趣爱好相似程度，提出一种社团相似度的计算方法；其次，从用户节点所在的社团内部和外部2个维度度量节点间紧密度，并据此度量节点的社会影响力，进而将它们划分成不同角色，实现用户推荐的差异化。通过新浪微博真实社交数据对方案进行验证，实验结果表明，该方案适用于存在社团现象的社交网络层次化用户推荐，并具有良好的推荐效果。
关键词：相似社团；节点角色；用户推荐；社交网络
0引言
随着信息化社会的到来，互联网已成为人们日常生活中的重要组成部分。在线社交网络，如Facebook,Twitter等，更是近年来互联网最炙手可热的产品之一。但是，社交网站因其数据量巨大、数据结构多样化以及数据关系复杂化的特点，需要提高用户获取信息的效率，挖掘到满足用户个性化需求的信息资源的方法[1]。推荐技术就是在此种背景下被提出和发展的，为用户提供高质量的用户推荐、项目或服务推荐，不仅可以增加用户粘性，也帮助企业了解用户需求，并开启了社交广告新模式。用户推荐作为推荐应用中一项重要的服务，近年来也成为了研究热点，通过计算用户相似性，为用户推荐还未形成链接但相似性高的其他用户[2-3]。
目前大多数的用户推荐方案的一个重要前提是2个节点相似性越大[4-5]，他们之间新增关注的可能性就越大，主要有以Jaccard相关系数[6]、Salton相似系数[7]为代表的基于共同邻居的相似性指标，以Adamic-Adar指标[8]为代表的基于节点度的相似性指标；Newman等人也考虑2个节点之间的路径数对相似性产生的影响，提出基于路径的相似性指标LHN-II[9]；其他相似性算法还包括基于随机游走定义的SimRank指标[10-11]和重启型随机游走算法[12-13]。由此可以看出，传统的用户推荐方案主要以个体用户的相似度为基础，少有考虑群体因素的影响。因此，本文在此基础上，将个体间相似研究扩展为群体间相似研究，综合考虑社团间联系的紧密程度和社团用户兴趣爱好相似程度，从社团结构和属性两方面，提出一种社团相似度的定义及计算方法。
另一方面，基于节点角色的社会网络应用研究也具有重要意义。Guimera, R.和Scripps, J[14-15]等人将其应用于社交网络、语义网络的链接挖掘问题。也有科学研究通过用户节点行为模式来划分角色，如Backstrom和Kumar R等人根据用户角色分析用户群体之间的关联[16]，Menasce等人利用角色划分优化电子商务的计算资源[17]，朱天等学者利用用户在社交网络中显露的情感行为特征将用户聚类，划分成不同类型[18]。综上可知，目前少有研究将节点角色划分应用到推荐领域，本文则创新地将其引入到用户推荐方案中，实现一种多角色层次的差异化推荐。
考虑到上述传统用户推荐方案中存在的不足，本文提出一种基于相似社团和节点角色划分的推荐方案。将传统的仅在个体之间进行的相似度计算扩展到群体之间进行，从社团结构和属性两方面提出一种社团相似度的定义及计算方法。以2个社团的公共相邻社团数占相邻社团总数的比例来度量它们的结构相似度；并利用社团用户的标签信息将社团属性分类，2个社团属性特征向量相似度即为它们的属性相似度。针对现有的推荐方案中推荐方式的单一性问题，本文假设在网络中拥有相似结构的用户节点具有相似的社会影响力，从社团内部和外部2个维度度量该节点与其他节点的紧密度，得到节点的影响力二维坐标，由此将它们分类，划分成不同角色，以实现用户推荐的差异化。
1问题形式化及相关定义
1.1问题形式化
为形式化地描述本文研究的问题，定义社交网络为一个有向图G={V,E}，其中V={v1,v2,…,vn}是社交网络中用户节点集合，E⊆V×V为用户间的朋友关系，若存在边ei,j=
本文研究问题可表示为
1)在tk时刻，根据网络G={V,E}得出S={s1,s2,…,sn}，计算目标社团si与其他社团sj(sj⊂S,sj≠si)的相似度Simi,j；
2)对∀vi∈si,∀vj∈sj,划分节点vi与vj的角色；
3)对相似度排名前TOP-N的社团，即rank(Simi,j)≤N,∀vi∈si且vi∈Rk,∀vj∈sj且vj∈Rk∪Rk-1，预测tk+1时刻是否存在边ei,j=
1.2相关定义
通常，用户vi与vj的相似度为两节点间相似度，是基于节点与节点之间关联关系进行的，在过去的研究中，用户相似度计算可分为结构相似和属性相似两方面。属性相似是指用户的特征信息相似；结构相似是指节点在网络中的结构等价性，如果2个节点在网络中共享很多相同的邻居节点，则这2个节点被认为结构等价。
定义1(Jaccard相似系数)：对集合X和Y,将它们的交集和并集的比值定义为2个集合的Jaccard相似性得分，计算公式为
(1)
定义2(余弦相似系数)：余弦相似度用向量空间中2个向量夹角的余弦值作为衡量2个个体间差异的大小，对向量X和Y,计算公式为
(2)
定义3(结构相似度)：设节点vi与节点vj的结构相似度为t(vi,vj)，令N(i)为节点vi的邻居节点集合，N(i)∩N(j)为vi与vj的共同邻居集合，|N(i)∩N(j)|表示其数量，则节点vi与节点vj利用Jaccard系数归一化的结构相似度计算公式为
(3)
定义4(属性相似度)：设节点vi与节点vj的属性相似度为f(vi,vj)，定义节点vi的n个特征属性为一个n维向量，即vi(i1,i2,i3,…,ik)，则节点vi和vj的基于余弦相似系数的属性相似度计算公式为
(4)
2基于相似社团和用户角色的社交网络用户推荐方案
2.1方案架构
本方案可划分成4个关键部分，如图1所示，包括①社团发现：利用社团发现算法挖掘网络中存在的用户的社交社团；②社团相似度计算：从结构和属性两方面计算社团相似度；节点角色划分；③用户角色划分：利用用户节点在社团中的影响力将用户分为不同层次的角色；④用户推荐：在相似社团之间进行角色层次差异化推荐。其中①是现有fastGN算法应用，②③④部分为本方案的研究重点。
图1 用户推荐方案框架Fig.1 Framework of user recommendation scheme
2.2社团相似度
由本文第2章所述，通常根据节点所在网络的连通性和节点用户的相关属性来计算节点相似度，以此类推，可将社团整体看作网络中的节点，从结构和属性两方面来定义社团相似度。
1)结构相似度。2个社团在整个网络中联系越紧密，则代表2个社团越可能相似。因此，社团间结构相似度可用2个社团公共相邻社团比例来衡量。
定义5(社团间结构相似度)：设ηi表示社团si的相邻社团，社团si与社团sj的结构相似度为ti,j,扩展节点间结构相似度定义为
(5)
2)属性相似度。同一社团中的用户通常因为具有相同的兴趣或偏好，如图2所示，这些兴趣或爱好往往显示在用户的标签信息中，大多数情况下，社交社团的属性其实是相对复杂的，可能同时属于几个类型，对其中个别类型更具倾向性。例如，一个社团中所有成员的标签对音乐、旅行、科技、财经这4种类型都有涉及，但是所占比重并不相同，可能科技类和财经类所占比重高于其他2类。
图2 社交网络社团Fig.2 Communities in social network
正是考虑到上述情况，在本文中，为计算社团间属性相似度，我们先计算社团属于每个划分类型概率，并以特征向量的形式来表现，再将属性相似度计算转化为计算特征向量的余弦相似度。
定义6(社团划分类型集合)：设社团划分类型集合C={C1,C2,…,Cn},n为划分类型个数。
定义7(社团属性特征向量)：设社团si的属性特征向量为fi=(i1,i2,…,in),其中ik(k∈{1,2,…,n})表示社团属性被划分为第k个类型的概率。
定义8(社团间属性相似度)：设社团si与社团sj的属性相似度为fi,j
(6)
为计算社团属于每个划分类型的概率，本文中我们选择朴素贝叶斯文档分类法，将各个标签出现的概率用社团属性向量来表示，根据各用户标签出现频率确定社团类型的划分标准，即社团划分类型集合C={C1,C2,…,Cn}，对每个社团，针对每一个类型Ck都将其进行一次分类。
定义9(社团属性向量)：设社团si属性向量为Xi={Xi1,Xi2，…，Xim},社团标签集中每个标签都为社团的一个属性，若社团si有m个不同标签，则si有m个属性，Xij(j∈{1,2,…,m})表示社团si的第j个标签出现的概率。
(7)
分类结果为2个类别，即Ck=1表示属于该类型,Ck=0表示不属于该类型。
根据贝叶斯决策理论，社团si属于类型Ck的概率ik,
(8)
社团属性相似度算法具体步骤如下。
算法： 社团属性相似度
输入：社团si,社团sj用户节点，用户关注关系，用户标签
输出：社团si和社团sj属性相似度fi,j
1.确定社团划分的n个类型及其分类标准
2.对每个划分类型，分别将其对应训练样本进行概率参数学习,生成n个分类器
3.for分类器Ck,k:1→n
6.end for
7.updatefiandfj
8.fi,j=cos(fi,fj)
3)社团相似度。
定义10(社团间相似度)：设社团si和社团sj的社团间相似度为结构相似度与属性相似度的线性组合，定义为Simi,j,ti,j表示社团si和社团sj的结构相似度，fi,j表示属性相似度，α为调节参数，取0到1之间的任意值，则Simi,j=α·ti,j+(1-α)·fi,j.
2.3社团用户角色划分
本文假设满足拥有相似的结构的节点占据网络中的相同角色，通过分析节点在自身社团内外的影响力来定义节点在网络中的角色，并划分成不同层次。
对节点的影响力分析，本文采用一种基于社团结构的二维影响力度量方法，2个维度记为节点的Inner值和Outter值，构成节点影响力二维坐标。如图3所示，根据影响力二维坐标，可将网络的节点划分成为3种层次的角色：核心点、重要点及普通点。
图3 节点角色图Fig.3 Node role division
核心点(Role1)：表示节点在社团内外都拥有极大的社会影响力；重要点(Role2)：表示节点在社团外部具有很大的社会影响力；普通点(Role3)：表示节点在社团内外社会影响力较小。
影响力度量方法的本质是利用PageRank算法分析节点在社团内部和外部的影响力。PageRank是一种计算网页重要性排名的算法，其原理是依据从许多优质的网页链接过来的网页，必定还是优质网页。
页面pi的PageRank值计算公式为
(9)
(9)式中：c为衰减因子；L(pj)表示与页面pj相连的页面数量；N表示所有页面的数量。多次迭代后PR(pi)收敛。
本文中，我们采用社团中的每个点在社团内外的重要性来量化节点在所属社团的内部影响力和外部影响力，节点影响力分析的问题可形式化表述为：
1)对每个社团si，对与其中每个用户vi互为好友的用户vj，若vj∈si,则将vj加入到用户集合ListIn中，反之将vj加入到用户集合ListOut中；
2)用户vi与集合ListIn构成有向图G′={V′,E′},V′=vi∪ListIn；用户vi与集合ListOut构成有向图G″={V″,E″}， V″=vi∪ListOut；
(10)
(11)
计算节点影响力二维坐标算法具体步骤如下。
算法： 节点影响力二维坐标
输入：社团si用户节点，用户关注关系，衰减因子β
输出：社团中每个用户的Inner和Outter值
1.for everyvi∈sido
Waters 2695-2475高效液相色谱仪（配Empower 2软件）；梅特勒-托利多（METTLER TOLEDO）XS-205电子天平（精度为0.01 mg）；上海民桥精密科学仪器有限公司SL502 N电子天平（精度0.01 g）；梅特勒-托利多（METTLER TOLEDO）FE20 pH计；昆山市超声仪器有限公司KQ-500E型超声波清洗器。多功能微生物自动测量分析仪（北京先驱威峰技术开发公司，ZY-3001V）；37℃恒温培养箱；钢管自动放置器（北京先驱威峰技术开发公司，ZY-300G）；三洋MLS-3780高压蒸汽灭菌锅；Thermo Scientific A2生物安全柜。
2.ifvi,vjare connected
3.ifvj∈sithenlistInaddvj
4.ifvj∉sithenlistOutaddvj
5.end for
6. for everyvi∈sido
7.for everyvj∈V′ do
10.end do
11.end for
12.for everyvj∈V″ do
15. end do
16.end for
17.end for
2.4推荐方案
传统的推荐方案是在用户相似的基础上进行的，即2个不存在连边的用户节点之间的相似度越高，越可能形成关注。但现实中常存在另一种情况，2个相似社团中的各层次用户之间也可能形成关注关系，例如，2个研究相似课题的实验室中，人员可划分成实验室主任、科研老师和学生3个层次，2个团队的学生之间可能形成关注，其中一个团队的部分学生也可能与另一个团队的个别科研老师形成关注。若2个实验室联系越紧密，研究课题越相似，形成的关注关系也越多。
图4 用户推荐方案示意图Fig.4 User recommendation scheme in community pair
正是考虑到上述情况，本文扩展了传统的用户推荐方案，采用一种基于相似社团和节点角色划分的方式推荐用户。分为如下步骤。
1)在tk时刻，根据网络G={V,E}得出S={s1,s2,…,sn};
2)计算目标社团si与其他社团sj(sj⊂S,sj≠si)相似度Simi,j;
3)对∀vi∈si,∀vj∈sj,根据σ(i),σ(j)分别划分节点vi与vj的角色；
4)对相似度排名前TOP-N的社团，即rank(Simi,j)≤N,∀vi∈si且vi∈Rk,∀vj∈sj且vj∈Rk∪Rk-1,如图4所示，将所有满足此条件的用户vj推荐给用户vi.
3实验和结果分析
3.1实验数据
1)数据集。本文采用的是新浪微博数据集，新浪微博是国内知名社交网站，用户可以关注其他用户，或者被其他粉丝关注，可以发布微博分享图文和转发别人发布的微博。该数据来自文献[19]的实验数据，包含在新浪微博平台上注册的170万用户以及他们之间的关注关系，数据集具体信息如表1所示。
用户关注关系数据按照抓取的时间节点，被分为30个时间片(即30个timestamp)，从图5中可以看出，在每个时间片都有新增的关注关系，因此，若使用此数据集，能够实现根据部分时间片关系数据形成的网络验证用户节点在后续时间片中是否形成新的连边，符合实验要求。
表1 数据集信息
图5 关注关系增量变化Fig.5 Increment of relationships
2)数据说明。①考虑实验可操作性以及微博数据中相互关注的用户更可能存在真实的社交关系这一特点，我们从数据集中随机选择10 000个用户，根据他们之间的相互关注关系构成的网络作为实验数据。②使用文献[20]中的软件对实验数据执行fastGN算法，挖掘出了约100个社交社团，结合社交网络的实际情况，按照社团中用户的数量分成3种不同规模的社团，每种社团中的用户数量分别为0-50个、50-100个以及100-200个。③对这3种规模的社团，随机选择每种30个分别组成3组实验社团，记作dataset0，dataset1和dataset2。
另外，由于用户标签数据稀疏，在计算社团的属性特征向量时，为达到更好效果，我们用社团中所有用户关注的认证用户(大V用户)的标签作为此社团的标签集，平均每个认证用户有5个标签。
3.2评价指标
为验证本文算法准确性，将数据集中已存在的关注数据根据关注时刻分为训练集(timestamp=1)与测试集(timestamp>1)两部分。
本文提出的是一种相似社团间的好友推荐方法，将计算用户间相似度扩展为计算社团间相似度，生成的好友推荐集也不再是单个用户而是社团中的具有同样角色层次的一类用户。因此，传统的用户推荐算法的2种经典评价指标：Precision和AUC，也应重新被定义。
新的评价指标计算方法：
1)Precision:Precision=m/N
(12)
准确率为推荐成功数m与推荐总数N的比值，在本文实验中，若目标社团一类用户与推荐集的一类用户形成的任一关注在测试集中，都记作该类用户推荐成功。
2)AUC:AUC=(n1+0.5*n2)/n
(13)
AUC从整体上衡量预测算法的精确度，它表示在测试集中推荐的得分比一个随机选择的不成功的推荐得分高的概率。对每个目标社团，每次随机选择一个与之在测试集中存在关注的相似社团和不存在关注的相似社团进行比较，独立比较n次。其中存在n1次关注的社团与目标社团相似度大于不存在关注的社团与目标社团相似度，存在n2次两者相等。
3.3实验方案
1)社交社团。在timestamp=1时刻对实验数据执行fastGN算法，使用文献[14]中的软件将其可视化，得到的部分社交社团及具体社团示例如图6所示，图6b中每个阴影区域代表一个社团，图6a中节点代表社团中的用户，节点间的连边则代表2个用户互相关注，节点标签为用户的具体ID。
2)推荐准确率与社团间相似度对应变化关系。对传统的基于用户相似度的推荐方案，通常在验证其可行性的科学实验中，采用验证推荐准确率是否与用户节点间相似度成正相关这一方式。类似地，可采用检测推荐准确率随社团间相似度变化的趋势来验证本文提出的基于相似社团的用户推荐方案的可行性。
图6 网络中的社团及其具体示例Fig.6 Communities in network and specific community example
因此，本文对3组实验社团中的每个社团都进行相同操作：将与它相似度排名top10社团中的用户，按照用户被划分的角色层次，分别推荐给该实验社团中相同层次角色的用户，推荐准确率与社团相似度情况如图7所示。由图7可知，对3组实验社团，推荐准确率与社团间相似度均成正相关，即为目标社团中的用户推荐越高相似度社团中的其他用户时，越容易形成正确的推荐。
3)差异化推荐方式与非差异化推荐方式的效果对比。为验证角色层次差异化推荐是否对推荐效果的影响，本文在3组实验社团中，分别为每个目标社团荐相似度排名top30社团中的用户，并对比如下2种方式的推荐效果：
Case1:只推荐同层次角色的用户；
Case2:推荐同层次和高一层次角色的用户。
图7 推荐准确率与社团间相似度对应变化Fig.7 Corresponding change of recommendation precision and community similarity
图8-图10分别显示了对3组实验社团，case2的推荐准确率均略高于case1。
图8 dataset0两种推荐方式效果对比Fig.8 Performance comparision of two recommendation cases in dataset0
图9 dataset1两种推荐方式效果对比Fig.9 Performance comparison of two recommendation cases in dataset1
图10 dataset2两种推荐方式效果对比Fig.10 Performance comparison of two recommendation cases in dataset2
结果表明，差异化推荐能够提升推荐效果，第2种方式准确率只是略高于第1种则恰好证明多数的关注关系都在同层次用户之间建立的，但是与高一层次用户也可能形成推荐。
4)推荐的效果与社团规模对应变化。由于本文所述的推荐方案是在相似社团直接进行的，为研究社团规模是否对推荐效果产生影响，并验证推荐效果最优的社团规模，本文在3组实验社团中任意选择两组分别作为目标社团集与相似社团集，再将相似社团集中所有社团采用上述case2方式推荐给每个目标社团，表2和表3为目标社团集的Precision平均值(记为AvePrecision,)和AUC平均值(记为AveAUC)变化。从表2中可以看出，本方案具有良好的推荐效果，且目标社团集为dataset1时效果优于其他2组社团集。由此可知，本方案最适用于50-100个用户规模的社团。
表2 3组实验社团平均准确率
表3 3组实验社团平均AUC
4结论
本文在传统社交网络中用户推荐方案基础上，提出了一种基于相似社团和节点角色划分的推荐方案。首先，将传统的主要在个体之间进行的相似度计算扩展到群体之间进行，从社团结构和属性两方面，提出了社团相似度的计算方法；其次，假设在网络中拥有相似结构的用户节点具有相似的社会影响力，从用户节点所在的社团内部和外部2个维度度量节点间紧密度，得到节点的影响力二维坐标，由此将它们分类，划分成不同角色，实现了用户推荐的差异化。最后利用新浪微博真实社交数据验证了该方案的推荐准确率与社团间相似度成正相关变化，角色层次差异化推荐可以提升推荐效果，实验表明，该方案适用于存在社团现象的社交网络层次化用户推荐，并具有良好的推荐效果。
参考文献：
[1]FRASER M,DUTTA S.Throwing sheep in the boardroom:How online social networking will transform your life,work and world[M].USA：John Wiley & Sons,2010.
[2]TANG Jiliang, HU Xia, LIU Huan. Social recommendation: a review[J]. Social Network Analysis and Mining, 2013, 3(4): 1113-1133.
[3]PAREEK J, JHAVERI M, KAPASI M A, et al. Recommendation System Using Social Networking[J]. International Journal of Computer Science, Engineering & Information Technology, 2012, 2(5): 45-54.
[4]LU Linyuan,ZHOU Tao.Link prediction in complex networks:A survey[J].Physica A,2011(390):1150-1170.
[5]DONG Yuxiao, TANG J, et al. Link prediction and recommendation across heterogeneous social networks[C]//Data Mining (ICDM), 2012 IEEE 12th International Conference on. [s.l.]:IEEE, 2012: 181-190.
[6]JACCARD P.Etude comparative de la distribution florale dans une portion des Alpes et du Jura[J].Bulletin de la Societe Vaudoise des Sciences Naturelles,1901,37(142):547-579.
[7]SALTON G, MCGILL M J. Introduction to modern information retrieval[M]. Auckland: MuGraw-Hill, 1983.
[8]ADAMIC L A, ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211-230.
[9]LEICHT E A,HOLME P,NEWMAN M E J.Vertex similarity in networks[J].Phys Rev E,2006(73):026120.
[10] JEH G, WIDOM J. SimRank: A measure of structural context similarity[C]// Proceedings of the ACM SIGKDD 2002. New York: ACM Press, 2002: 538-543.
[11] QIAO Shaojie,LI Tianrui,LI Hong,et al.SimRank:A Page Rank approach based on similarity measure[C]//Intelligent Systems and Knowledge Engineering(ISKE),2010 International Conference on.Hangzhou:IEEE,2010:390-395.
[12] BACKSTROM L, LESKOVEC J. Supervised random walks: predicting and recommending links in social networks[C]//Proceedings of the fourth ACM international conference on Web search and data mining. [s.l.]:ACM, 2011: 635-644.
[13] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Comput Netw & ISDN Syst, 1998, 30(1-7): 107-117.
[14] GUIMERA R, SALES-PARDO M，AMARAL L A N. Classes of complex networks defined by role-to-role connectivity profiles[J]. Nature physics, 2007(3)：63-69.
[15] SCRIPPS J, TAN P N，EAFAHANIAN A H. Node roles and community structure in networks[C]// Joint 9th WEBKDD and 1st SNA-KDD Workshop. [s.l.]:ACM, 2007:26-35.
[16] BACKSTORM L, KUMAR R, MARLOW C, et al. Preferential bahavior in online groups[C]//Proceedings of the ACM Web Search and Data Mining(WSDM). California: ACM, 2008:117-128.
[17] MENASCE D, ALMEIDA V, FONSECA R. A methodology for workload characterization of e-commerce sites[C]//Proceedings of ACM Conference on Electronic Commerce. Denver: ACM, 1999: 119-128.
[18] ZHU Tian, WANG Bai, WU Bin. Social network users clustering based on multivariate time series of emotional behavior[J]. The Journal of China Universities of Posts and Telecommunications, 2014, 21(2): 21-31.
[19] ZHANG Jing, LIU Biao, TANG Jie, et al. Social influence locality for modeling retweeting behaviors[C]//Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. [s.l.]:AAAI Press, 2013: 2761-2767.
[20] QI Ye, WU Bin, SUO Lijun, et al. Telecomvis: Exploring temporal communities in telecom networks[M]//Machine Learning and Knowledge Discovery in Databases. Berlin Heidelberg：Springer, 2009: 755-758.
DOI：10.3979/j.issn.1673-825X.2016.04.013
基金项目：国家自然科学基金(61272400)；重庆市青年人才项目(cstc2013kjrcqnrc40004)；教育部-中国移动研究基金(MCM20130351)；重庆市教委科学计划项目(KJ1500425)；重庆邮电大学文峰基金(WF201403)
Foundation Items：The National Science Foundation of China(61272400); The Chongqing Youth Innovative Talent Project(cstc2013kjrcqnrc40004); The Ministry of Education of China and China Mobile Research Fund(MCM20130351); The Science Project of Chongqing Municipal Education Commission(KJ1500425); The WenFeng Foundation of CQUPT(WF201403).
收稿日期：2015-12-29
修订日期：2016-05-06通讯作者：钟晓宇zxy8712@163.com
中图分类号：TP391
文献标志码：A
文章编号：1673-825X(2016)04-0525-08
作者简介：
钟晓宇(1991-)，女，四川乐山人，硕士。主要研究方向为数据挖掘，社交网络推荐。E-mail:zxy8712@163.com。
刘宴兵(1971-)，男，四川遂宁人，教授，博士，博士生导师，主要研究方向为无线网络管控和网络信息安全。E-mail:liuyb@cqupt.edu.cn。
肖云鹏(1979-)，男，安徽人，副教授,博士，主要研究方向为大数据，移动互联网，信息安全。E-mail:xiaoyp@cqupt.edu.cn。
(编辑：魏琴芳)
A user recommendation scheme based on similar community and node role division in social network
ZHONG Xiaoyu，LIU Yanbing，XIAO Yunpeng
(Chongqing Engineering Laboratory of Network and Information Security, Chongqing University of Posts and Telecommunications,Chongqing 400065, P. R. China)
Abstract:In view of current research on user recommendation mainly considering similarity of node pair and ignoring role level difference of users, we introduce a new way based on similar community and node role division. At first, relying on the similarity of node pair, we put forward a method to calculate the similarity of community pairs from two perspectives: community structure and attributes of users. Secondly, according to the measurement to external and internal tightness of every node in community, we analyze the users’ social influence and divide them into different roles in order to recommend friends discriminatively. Finally, we select Sina Weibo data to verify our method. Experiment results show that the scheme performs well and is suitable for user recommendation where there are communities in the social network and users can be divided into roles of different levels.
Keywords：similar community；node role；user recommendation；social network
