- 1 -
中国科技论文在线
基于用户社区的云服务个性化推荐
李凌飞1，张成文2**
作者简介：李凌飞 男 硕士研究生，主要研究方向：云计算和服务推荐
通信联系人：张成文，男，副教授，云计算和个性化推荐
（1. 北京邮电大学计算机学院；
2. 北京邮电大学计算机学院，北京市智能通信软件与多媒体重点实验室。） 5
摘要：传统的个性化推荐系统经过了多年的研究发展，在电子商务和 web 服务领域已成熟
应用。近几年随着云计算的迅猛发展，云服务数量快速增长，对于云服务的个性化推荐有
了新的需求，由于云服务的多层次和不同的付费模式，云服务对于功能和非功能性的需求
有着不同的要求。传统静态商品的推荐方法无法应用于云服务推荐。考虑到云服务环境中10
还有着海量的服务和用户，本文提出了一种利用社区发现进行用户社区划分并根据目标用
户所在的社区进行推荐的算法，以缩小对目标用户推荐的服务的范围，提高推荐精度和速
度，然后通过服务关系来确定用户的功能需求，进行推荐。实验表明，本文提出的方法有
效提高了推荐的精度。
关键词：云服务；个性化推荐；社区发现；服务关系。 15
中图分类号：请查阅《中国图书馆分类法》
A Personalized Cloud Services Recommendation Based on
User Community
LI Lingfei
1
, ZHANG Chengwen
2
20
(1. Department of Computer, Beijing University of Posts and Telecommunications;
2. Beijing Key Laborary of Intelligent Telecommunications Software and Multimedia, Department
of Computer, Beijing University of Posts and Telecommunications.)
Abstract: After years of research and development, traditional personalized recommendation
system has been widely used in the field of e-commerce and web services. In recent years, with 25
the rapid development of cloud computing and rapid growth in the number of services,
personalized recommendation for cloud services have a new demand due to multiple levels and
different payment modes cloud services. Traditional personalized recommendation in e-commerce
field is not suitable for cloud service very well. Paper proposes a personalized recommendation for
cloud services, which is based on user community and the relationship of services that are selected 30
by users in one community. a networks of users is built, then an algorithm is proposed for finding
overlapping community structure in large networks. This algorithm is based on label propagation
technique, but is able to detect communities in weighted networks. Detecting communities reduces
the scope of recommendation for the target user. Then, we make a recommendation by
relationship between services. The result shows that the algorithm is more effective. 35
Key words: Cloud services; personalized recommendation; community discovery; service
relationship
0 引言
推荐系统是为解决 Internet 上的信息过载问题而提出的一种智能代理系统，能从 Internet40
的大量信息中向用户自动推荐出符合其兴趣偏好或需求的资源。个性化推荐系统大概于 20
世纪 90 年代才被作为一个独立的概念提出来的，个性化推荐的研究得到了迅速的发展。
云服务环境中存在着大量的服务个体以及用户个体，每个服务与其他服务之间的关系变
得非常复杂，并且服务之间的关系也变得非常多。而用户所可能涉及的服务也许只是所有服
务的一小部分，如果能够将这一小部分的服务预先获取之后再根据服务之间的关系进行推45
- 2 -
中国科技论文在线
荐，这时服务间关系的计算量将变得比较简单。这些用户可能会涉及的服务可以通过获取与
用户需求相近的用户进而将这些用户所使用过的服务作为目标用户可能涉及的服务。
在云服务环境中，不同专业，不同领域和层次的用户通常浏览的信息和使用的服务是有
所不同，这里将用户在网络中使用的服务称作用户在云服务环境中的活动范围。例如，建筑
设计师与文案工作人员在日常工作中所使用的云服务通常是不同的，两者的活动范围几乎是50
不重叠的，而具有相近专业领域的用户通常选择的服务是相同或者在功能上相似，其活动范
围通常是重叠在一起的。
因此，本文拟采用复杂网络的社区发现，根据用户所使用的不同种类的服务，对用户进
行聚类，划分出分属不同专业领域的用户，同时也得到了这类用户的活动范围。在进行推荐
时就可以在用户所属的用户类涉及到的服务范围内进行服务关系计算和推荐。同时考虑到用55
户可以分属多个专业类，因此采用重叠的社区发现进行用户聚类，将用户数量和服务数量的
缩小到较小的规模。加快推荐速度以及增加推荐精度。在较小规模的服务数量下，利用服务
之间的关系来进行服务推荐。
1 相关研究进展
复杂网络和社区发现 60
关于复杂网络的研究已经有了较长的历史，而到现在对于复杂网络的研究仍是方兴未
艾，网络中的节点作为复杂系统的个体，各自之间有着自然形成或者人为构造的关系，复杂
网络可以反映现实社会的一些复杂的关系网络，云服务环境也可以用复杂网络来抽象，其中
的用户和服务都可以被作为节点来对待。复杂网络的一个重要特征就是其呈现的社区结构，
即复杂网络是由许多性质类型的节点组合而成的，相同性质类型的节点之间有较多的联系，65
不同性质类型的节点之间的联系较少(如图 1 所示)。
在复杂网络中自动搜寻和发现社区具有很大的现实意义，社区发现的研究起源于社会学
的研究工作 Newman 和 Girvan 的研究成果[1,2]，使得复杂网络中的社区发现成为近几年复杂
网络领域的一个研究热点并形成了复杂网络中一个重要的研究方向。
70
图 1 具有社区结构的复杂网络
Fig. 1 Community structure in networks
早期的社区发现算法采用的是层次聚类的方法[3]，通过自上而下的划分或者自下而上
的聚集来对网络进行划分。同时还有利用矩阵信息进行社区发现的谱分析法[4,5]。目前关于75
社区发现思想和算法又有了极大的丰富和发展，算法从简单的单边网络扩展到带权网络和有
向网络，从全局的社区发现到局部社区发现，从最初的层次聚类和谱分析又演变出随机游走
和聚集算法。一般的社区发现算法的复杂度一般比较高，近几年提出了一种复杂度比较低迭
代次数较少的标签传播算法 (label propagation algorithm, LPA)[6]。
标签传播算法 80
- 3 -
中国科技论文在线
算法的一般过程
其算法过程可以表示为：
1. 初始化，每个节点都赋予一个独有的标签；
2. 更新每个节点的标签，更新规则是：遍历所有的邻居，找到被使用次数最多的标签，
使用该标签替换自己的标签。如果出现次数最多的标签有多个，随机选择一个来替85
换。经过多次迭代之后，拥有相同标签的节点就趋于构成一个社区。
3. 结束更新，当所有的节点标签状态和更新前的状态不变时，不再更新。将使用同一
标签的节点构成一个社区。
节点更新过程中，在第 t 次迭代时需要记录保存前一次即 t-1 次时的状态，第 t 次迭代
中，遍历节点的邻居节点时，统计的标签应该是邻居 t-1 次时的所使用的标签。每次更新过90
后每个节点的标签都是它所有邻居使用标签中出现次数最多的那个标签。该算法的结束条件
所有节点的标签不再发生变化。该算法的结束条件是每个节点的标签都是它所有邻居使用标
签中出现次数最多的那个标签,其结束条件看似很难达到，但实际操作中，一般能够证明 5
次迭代之后，大约有 95%的节点都会得到最终的结果[6]。
该算法优点在于，其时间复杂度是线性的，初始化的时间复杂度为 O(n)，n 为节点数，95
每次迭代的复杂度为 O(m)，m 是边的个数。该算法的前提条件有每个节点的邻居确定，并
且对于某一节点 A，它所有的邻居在 A 更新标签的时候对于 A 的影响力是相同的，每个邻
居使用的标签都计数 1。
重叠社区发现
考虑现实中一个用户可能出现在多个领域中的情况，算法中允许一个节点同时属于两个100
社区，即可以应用于重叠社区的发现算法[7,8]。算法将每个节点所拥有的标签扩展为标签集
合，标签集合可以包含多个标签，同时每个标签有着一个系数值，来表示这个标签在标签集
合中的比重，所有标签系数值之和为 1。算法还设置了一个阈值，在更新标签时，当标签系
数值不小于该值时，保留标签，否则舍去，如果所有标签系数值都小于该值，则根据一般
LPA 算法的规则，通过随机选择的方法来确定节点的标签。 105
如图 2 所示，将每个节点的标签变为标签集合。每个集合中都是一个键值对(c，b)，c
表示标签，b 表示系数。集合中的系数和应该是 1。
图 2 标签的传播情况
Fig. 2 The propagation of lable 110
当节点的邻居很多时，需要注意的是并不是将所有的标签都放入集合中，例如第一次 a
有 b d e g 四个邻居，更新时替换为{(b, 1/4), (d, 1/4), (e, 1/4), (g, 1/4)}，每一个节点在更新时
都会出现这种情况，因为所有邻居初始化的标签都是独一无二的。该算法的规定一个阈值
- 4 -
中国科技论文在线
1/2，第一次更新时所有键值对(c，b)中，b<1/2 的键值对都会舍去，然后随机选择一个，比
如说 e，将标签集合更新为{(e，1)}。图 3 是一个重叠社区的发现过程，结果中 a 属于两个115
社区。
图 3 标签传播算法
Fig. 3 Lable propagation algorithm
标签传播算法的缺陷 120
带权的社区进行重叠社区发现时，由于阈值和标签集的设定，不能完全阻止某些标签通
过低权值的边向其他节点进行扩散，可能会出现某些标签扩散到很大的范围，增加了算法的
不稳定性，较坏情况下，会导致划分出的社区规模较大，不能很好地区分出用户的专业领域，
从而达不到社区发现的目的。
LPA 的概念非常简单，算法复杂度也较低，但其稳定性较差，当更新节点的邻接节点标125
签频率相同时，选择标签为随机的，而且标签的更新顺序也是不固定的，因此该算法的鲁棒
性受到严重损坏，有时也会出现标签震荡的现象，即节点标签在更新过程中，在两个状态之
间反复变化。目前关于 LPA 的研究多是单边不带权的网络。在本文所构建的用户关系网络
中，用户与用户之间的关系表示了两个用户使用的服务类型的相近程度，也就是用户之间活
动范围的重叠程度，以判断用户是否能化为同一个专业领域，因此使用边来表示用户关系时，130
需要区分不同的相近程度，需要对边进行加权。
2 改进的社区发现算法及推荐过程
为了避免标签的过渡扩散，同时提高算法的稳定性，利用本文设计的带权网络的特点，
本文提出了一种比较稳定的适用于带权网络的重叠社区 LPA 算法。算法根据用户节点连接135
的边以及边的权值，来获得用户在标签更新时对相邻节点的影响力，即连接边较多以及边权
值较大的节点的影响力较大。在初始化赋予标签时，只给影响力较大的节点赋予权值，其它
影响力较小的节点没有初始化标签，这样其它影响力小的节点趋于从影响力大的节点获得标
签，最终加入较大影响力所在的这些社区。同时根据影响力对节点排序，使用这个顺序进行
更新，更新过程使用异步更新。 140
- 5 -
中国科技论文在线
模型建立
首先，我们需要约定这样一个前提情况或者事实：在云服务环境中，可以按照服务所能
完成的功能将服务分为不同的类。而且对于每个具体的服务，我们也可以通过某种方法获得
关于其功能的描述信息。那么在推荐过程中，我们可以描述这样一个场景，在这一个云环境
中，有若干类的服务，分类是按照服务能够完成的功能来实现的，比如影音类，文本编辑类，145
数据处理等类别，对于每一个具体的服务，有相关的描述信息来获知它是属于那种抽象的服
务。然后我们可以根据用户使用的抽象服务来对用户进行聚类，也就是用户社区发现过程。
将云环境中的抽象服务类记录为一个集合 } AS { AS i ，包含所有的抽象服务类。i 取
值 1,2,3……,N，即取遍所有的抽象服务类。
在前期的复杂网络建立过程中，根据用户使用服务的记录，将所有服务用其所属的抽象150
服务类来替代。获得用户 Useri 所使用的抽象服务类的记录，记做 UASi，i 为用户的 id，记
录表示为 ,...}N,AS{UAS ijji ， jAS 表示第 j 个抽象服务类， ijN 表示用户使用的
这个服务类中的具体服务的个数，没有则为 0，忽略这个数量将可能导致在计算用户相似性
的时候出现偏差，因为会出现一个用户使用了许多第 j 类服务，而另一个用户只使用了很少
的 j 类服务，那么这两个用户的相似关系受到这个数量的约束。 155
计算两个用户的相似性 Cos(i, j) 。其中，分母为两个用户使用的抽象服务的并集，分子
是两个用户使用的抽象服务的交集。 j)(i, 表示服务类 jAS 与用户 iUAS 的关系， iUAS 包含
jAS 时，记做 1，否则记为 0；
)1(
)N,min(Nk)(j,k)(i,Nk)(j,Nk)(i,
)N,min(Nk)(j,k)(i,
j)Cos(i,
N
k
jkik
N
k
jk
N
k
ik
N
k
jkik
上式中，N 表示抽象服务的数量。 160
社区发现算法
与传统标签传播算法相似，仍分为初始化，更新和结束三个状态。
(1)初始化：构建网络，根据边以及权值计算节点的影响力。并根据影响力对节点排序，
这个顺序就是更新时的顺序。影响力记作
N
j
iji eP 。其中， ije 表示节点 i 和 j 的边权
值。同时计算所有节点影响力的平均值 P，并取一个系数 s(0 < s < 1)，给定阈值 Ps 当节165
点影响力大于阈值时，给予节点标签值，否则不赋予标签，其中，s 的值根据实验进行调整，
以取得较好结果。
更新:更新采用异步更新方法，即在第 t 次迭代时，如果更新到序列的第 i 个节点，这时
0 到 i-1 个节点已经更新过，即用第 t 次的标签状态，第 i+1 之后的节点的标签状态是 t-1 次
时的状态。更新第 i 个节点所需要的其他节点的状态就使用当前的标签状态。与异步相对应170
的同步方法指的是，第 t 次迭代更新时，所有用到的节点状态都是 t-1 次时的状态。
同步更新如式(2)所示
))1(,),1(),1(()( 21 tCtCtCftC xnxxx （2）
其中， )(tC x 表示的是节点 x 在时刻 t 时的更新情况，函数 f 的参数表示的是 x 的 n 个
- 6 -
中国科技论文在线
邻居在时刻 t-1 的标签状态。而异步更新则是使用节点的邻居在当下的标签状态，即有的邻175
居已经更新，使用当前 t 时刻的状态，其他未更新邻居使用的是 t-1 时刻的状态。因此异步
更新需要有一个更新顺序，其顺序是按照初始化中节点的影响力来排序，优先更新影响力较
大的节点。异步更新如(3)所示，其中 1 到 m 表示本次已更新的邻居，m+1 到 n 表示未更新
的邻居节点。
))1(),...,1(),(,),(()( )1(1 tCtCtCtCftC xnmxxmxx (3) 180
结束状态:当所有的节点的标签状态不在发生变化时，结束更新。
服务推荐
再使用 LPA 社区发现算法对用户进行分类之后，可以首先确定目标用户所在的用户社
区，然后利用服务之间的关系对目标用户进行推荐。服务关系是指，在用户选择服务时，经
常在某一段连续时间内，选择多个服务来完成某一项任务，这些服务构成一个服务组，服务185
组包含的服务之间存在着功能的相似性或者互补性，当有许多用户都有着在某一段时间内选
择这几个服务的情况，那么这几个服务之间就有着较密切的联系。当其他用户选择某一个服
务时，就有可能需要与这个服务有密切关系的服务，即用户存在可能的功能性需求，那么就
向该用户推荐与这个服务关系密切的服务。
推荐模型 190
用 集 合 kjii SCSCSCDS ,...,, 表 示 用 户 使 用 过 的 服 务 组 ， 用 集 合
kjii SSSCD ,...,, 表示组成服务组 iSC 的服务。用 ki 表示表示服务 iS 和服务组
kSC 的关系，如公式(6)所示，当服务 iS 在服务组 kSC 中时，记作 1。 kN 记录服务组 kSC 包
含的服务数量，见公式(5)。同时还有 ij 表示第 i 个服务和第 j 个服务是否在同一服务组中，
当两个服务同时出现在同一服务组中时，记作 1，只有在同一服务组中的两个服务才能计算195
其使用关系，见公式(6)和(7)，两个公式是等价的，在(6)中， kjk ki 表示两个服务同
时出现的次数。
记 (4)
200
记 (5)
记 (6)
205
在服务与服务的关系图中，在某一服务组中同时出现的的两个服务结点有两条有向边相
连，对于任意一条边 iS --> jS ，赋予其一个权值，用 ij 表示服务 jS 对于服务 iS 的关系。
另一条边权则用 ji 表示。
210
ki
ki
ki
DS
DS
,0
,1
{
0,,0
1,,1
{
kjki
kjki
ij k
k
i
kikN
k
ki
k k
kjki
ij
N
1
- 7 -
中国科技论文在线
(7)
215
其中， )1( kkjki N 表示了在第 k 个服务组中，与服务 iS 合作的所有服务中服务 jS
所占的比例。 ij 表示了服务 jS 与服务 iS 合作的概率大小。
推荐步骤
推荐过程主要分为 3 部分：数据处理；获取用户使用情况和服务之间的关系；服务推荐。
1)根据记录，取得用户集合 U{ 1U , 2U , 3U , … , iU , … }以及服务集合 S{ 1S ， 2S ，220
3S ，…， iS ，…}。根据用户使用服务得到服务组集合 SC{ 1SC ， 2SC ， 3SC ，…， iSC ，…}。
2) 根据处理的数据和统计服务和服务组的集合，统计计算服务与服务组的关系，然后
根据公式(7)计算统计每两个服务之间的关系。
3)推荐。推荐的主要输入是用户 iU 和当前正在使用的服务 iS 。然后根据服务之间的关
系对服务排序，选取 Top-k 服务作为推荐结果。 225
3 实验及分析
实验数据
假设系统存在着许多服务组合，分属不同的专业领域，能够完成 N 个不同专业领域中
的任务。生成用户数据，随机给用户设定 N 个领域之一，这个属性只是用来生成数据时用，
分类时根据公式(1)计算的用户关系为依据，通过 LPA 算法进行划分。然后用户以较大概率230
根据自己所在的领域去随机选择该领域中的服务组，当然用户也会有一定可能性去选择其他
领域的服务组，以满足用户可能同时分属于多个领域的可能情况。
首先通过 LPA 社区发现算法对用户进行分类，分类根据公式(1)计算用户关系并根据规
定的 LPA 社区发现算法步骤进行划分。
首先，实验将所有的服务组划分到四个不同专业领域，然后生成一百名用户数据，生成235
时随机给用户一个专业领域，用户选择服务时，以 60%概率选择所属专业的服务，同时选
择其他任意组服务，以满足用户使用服务时的多样性。所给组号只在生成时使用，并在使用
社区发现算法进行划分后进行对比，在进行社区发现时忽略，生成数据如下：
表 1数据初始状态
Source Data 240
组号 包含的用户 ID
0 6, 7, 15, 20, 26, 35, 47, 51, 53, 54, 58, 59, 65, 66, 70, 74, 75, 77, 78, 80, 88, 94, 98,
1 2, 9, 12, 13, 23, 25, 27, 30, 36, 37, 39, 40, 41, 45, 48, 56, 57, 60, 61, 68, 72, 76, 82, 83, 87, 89, 95,
97,
2 0, 1, 5, 10, 14, 16, 17, 19, 22, 24, 32, 33, 34, 38, 46, 52, 62, 69, 71, 81, 84, 86, 96, 99,
3 3, 4, 8, 11, 18, 21, 28, 31, 43, 44, 49, 50, 55, 63, 67, 73, 79, 85, 64, 90, 91, 92, 93,
社区发现结果
通过 LPA 算法进行社区发现，根据用户的影响力对用户排序，顺序即用户更新顺序，
- 8 -
中国科技论文在线
对应划分得到 4 个社区，四个社区分别对应的组如下表，存在有用户同时属于两个社区，表
中将其单独列出，通过对比可以看出，根据 LPA 算法得到的分组数据与生成的原始分组数
据一致，差别仅在于有 5 个用户被划分到了两个社区，但所属的其中一个社区仍与原始数据245
一致。
表 2社区发现结果
Result of finding community
最终保留标签集 ID 对应用户 ID 对应组号
<87, 1> 30,36,56,82,23,39,41,72,76,13,89,27,83,12,25,37,87,60,61,68,
40,2,97,45,48,95,9,57
1
<91, 1> 4,8,55,85,21,44,73,3,43,64,92,18,28,31,49,93,11,91,67,50,63,90,79 3
<99,1> 16,62,34,99,32,38,81,22,84,1,0,52,10,33,69,24,19,5,86,96,71,46 2
<75,1> 15,54,58,66,75,53,94,26,78,65,47,70, ,35,51,7,20,80,88,74,59,77,98 0
<99,>
<87,>
96,71,46 2，4
<75,>
<99,>
17,14 2,0
实验进行了 16 次更新得到了稳定的状态，表明初始化时通过部分节点赋予标签值的方250
法能够快速地完成社区发现，同时改进的 PLA 算法也能很准确地对加权的复杂网络进行重
叠社区的发现。
推荐结果
然后选取目标用户，对用户进行推荐，使用之前发表文章中的算法[9]。推荐时假定用户
进入系统，选择一个或者多个服务，然后通过算法推荐给用户可能要用到的其他服务。将结255
果与用户已经选择的服务所在服务组中的其他成员对照，根据其他成员是否在推荐结果中来
判断推荐是否有效，以覆盖率为最终判断标准。
实验选择用户分别选择某一用户在单一社区和某一用户同时属于多个社区进行推荐，反
复进行多次(在此重复了 100 次)推荐，根据社区包含用户数量的不同，当推荐目标用户所属
单一社区时，用户数约为 30，当用户所属两个社区时，用户数为 50，用户数为 100 表示不260
通过社区划分而直接进行推荐。通过推荐算法得到三个情况下的的平均覆盖率和最高覆盖率
分别如图 4。
可以看出，当对用户进行划分之后，确定用户社区，缩小目标用户的推荐范围，可以比
较有效地提高推荐结果的准确性。一方面减少了向用户推荐服务的数量，大量减少了不必要
的服务关系的计算，同时确定服务的范围，保证了推荐时不受到其他无关服务的影响。 265
- 9 -
中国科技论文在线
图 4 推荐结果 270
Result of recommendation
4 结论与展望
综上所述，本文提出了一种利用社区发现进行用户社区划分并根据目标用户所在的社区
进行推荐的算法，属于文献[9]的进一步扩展。算法通过对用户进行社区划分，以确定用户
的服务使用范围，确定用户使用服务的大致种类，缩小向目标用户推荐时的服务规模，以提275
高推荐的准确性。本文主要的研究工作在于根据建立的复杂网络模型，对 LPA 算法进行改
进，对边进行加权以区分用户与用户之间关系的不同，然后通过初始化时对部分节点赋予标
签的方法，达到了提高 LPA 算法稳定性，减少震荡以及加快划分的效果。同时，在用户经
过社区划分之后确实提高了推荐结果的准确性。
另一方面，本文也存在一些不足，算法中人为对服务进行分类，建立了较为理想化的模280
型。另一方面，本文着重依据服务的功能性属性来进行用户划分和推荐，并未考虑到服务的
非功能属性以及用户的个性化对于服务推荐的影响。
[参考文献] (References)
[1] SCOTT J. Social Network Analysis: A Handbook [M]. Sage Publications, London. 2000: 161-172. 285
[2] GIRVAN M, NEWMAN M EJ. Community structure in social and biological networks [J]. Proc Natl Acad Sci
USA, 2002, 99(12): 7821-7826.
[3] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks [J]. Physical Review
E, 2004, 69: 026-113.
[4] EKSEN K A, SIMONSEN I, MASLOVS, et a1. Modularity and extreme edges of the Internet [J]. Phys Rev 290
Lett, 2003, 90(14): 648-701.
[5] CHAUHAN S, GIRVAN M. Spectral properties of networks with community structure [J]. Phys Rev E, 2009,
80(5): 56-114.
[6] XIE J, SZYMANSKI B K. Community detection using a neighborhood strength driven label propagation
algorithm. Network Science Workshop [J]. 2011: 188-195. 295
[7] University of Bristol, Bristol BS81UB, UK. Finding overlapping communities in networks by label
propagation. Department of Computer Science [J]. New Journal of Physics. 2010, (12): 103-118.
[8] SANJEEV A, RONG G, SUSHANT S. Finding Overlapping Communities in Social Networks: Toward a
Rigorous Approach [J]. 2011, 10: 90-99.
[9] ZHANG C W, BIAN J L, LI L F. A Personalized Cloud Services Recommendation Based on Cooperative 300
Relationship between Services [J]. Journal of Software Engineering and Applications. 2013, 6: 623-629.
