东北大学学报（自然科学版）
Journal of Northeastern University(Natural Science)
Vol. 39 ,No. 8Aug. 2 0 18
doi： 10. 12068/j.issn. 1005 -3026.2018.08.008
基于二分网络社团划分的推荐算法
陈东明，严燕娬，黄新宇，王冬琦
(东北大学软件学院，辽宁沈阳110169)
摘 要：传统的基于用户的协同过滤（User-based CF)推荐算法的推荐效率随着数据的不断增加而降
低.本文在User-based CF算法中引人二分网络社团发现理论，提出一种基于二分网络社团划分的推荐算法 (RACD).首先通过用户与项目之间的关系建立用户-项目二分网络，然后通过RACD对该网络进行社团划 分，得到用户的社团信息，最后通过同一社团中的其他用户对目标用户进行项目的推荐.在经典网络数据集上 的实验结果表明，RACD能够有效提髙推荐系统实时推荐效率.关键词：推荐算法;二分网络;社团划分;协同过滤;复杂网络中图分类号：TP 391
文献标志码：A
文章编号：1005 -3026(2018)08 -1103 -05
Recommendation Algorithm Based on Community Detection in Bipartite Networks
CHEN Dong-ming，YAN Yan-bin，HUANG Xin-yu，WANG Dong-qi
(School of Software，Northeastern University，Shenyang 110169，China. Corresponding author： HUANG Xin-
yu， E-mail： neuhxy@163.com)
Abstract ： The efficiency of traditional user-based collaborative filtering ( user-based CF) recommendation algorithm is reduced with data increasing. This paper proposes a recommendation algorithm based on community detection (RACD) in bipartite networks by introducing bipartite network community detection theory into user-based CF recommendation algorithm. Firstly，the user-item rating matrix is mapped into user-item bipartite network. Then, the community information of each user is obtained by using RACD to divide the user-item network. Finally， the items are recommended to the target user according to other users in the same community. Experiments on real-world classic network datasets show that the RACD can effectively improve real-time recommendation efficiency of the recommendation system.Key words： recommendation algorithm; bipartite network； community detection； collaborative filtering; complex network随着互联网技术的发展，网络中的数据呈指 数型增长,虽然以Google、百度为代表的信息检 索系统能够帮助用户获取很多的信息，但不同用 户检索出的结果是相同的.为了满足不同用户的 差异化需求，个性化推荐系统得到推广，它的出现 使得用户不再迷茫于浏览各种各样的网页，而是 在系统的协助下快速发现感兴趣的信息[1].目 前，国内外很多大型网站都使用了个性化推荐技 术，例如:Amazon，GroupLens，淘宝,百度等.
对推荐系统的推荐质量起决定作用的是推荐
收稿日期：2017 -03 -30
基金项目：辽宁省自然科学基金资助项目（20170540320);辽宁省教育厅科学研究项目（L20150167). 作者简介：陈东明（1968 -)，男，安徽怀宁人，东北大学教授.
算法，例如:Schedl等[2]通过分析用户的年龄、性 别、国籍等属性，以及用户听音乐的频率、时间等 行为提出了一种音乐推荐算法;Zheng等[3]通过 分析学生的历史借阅信息和图书之间的相似性等 信息提出了一种图书推荐算法.迄今为止,推荐系 统使用的推荐算法主要有协同过滤（collaborative
filtering，CF)算法[4-5]、基于内容（content-based)
的推荐算法[6-7]、混合推荐算法[8-10]等.User-
based CF 算法[||] 是 CF 算法中的一种， 传统的 User-based CF算法将所有用户对项目的评分数
1104东北大学学报（自然科学版)第39卷
据转换为评分矩阵,然后通过该矩阵获取用户之 间的相似性,进而根据相似性高的用户完成项目 的推荐.但是,实际数据的稀疏性影响了推荐精度 和效率.因此，学者们提出了不同的优化算法[12]. 近些年，有些学者提出了基于社团划分的协同推 荐算法[13]，但是这些算法中的社团划分算法需要 事先知道社团的数量或只适合小规模的网络，其 适用性有局限性.实际上，推荐系统中存在的网络 数据大多数可以抽象成二分网络,如“用户-商 品”网络，但针对这样的二分网络先进行社团划 如下：
Begin
Initialization ： Obtain the structure of the network, and get the initial node v = getFirstNode
()；
stepl: / *获得每个节点的最相似节点*/
getMaxSimilartityNodeSet() {
while (one of the neighbor nodes of v has
not been visited) {
set_tag. add (node);
分，然后再推荐的算法并不多.文献[14]提出了 一种基于结构相似性的二分网络社团划分算法 (BSSCD算法），该算法将相似性高的节点划分 到同一个社团中，而User-based CF算法的核心就 是寻找相似用户集合；因此,本文将BSSCD算法 与User-based CF算法进行结合，提出一种基于二 分网络社团划分的推荐算法（称为RACD),该算 法能够有效提高推荐系统实时推荐的效率.
1模型和方法
大多数推荐系统中的数据都可以抽象成二分 网络,“用户-商品”网络、“用户-电影”网络等 都属于二分网络.这些网络的用户之间往往会有 潜在的联系，如行为相似.社团划分算法能够发现 网络中可能存在的用户群体，推荐算法可以基于 这些群体进行产品的推荐.社团划分算法与推荐 算法之间存在着必然的联系.
社团划分算法可以在大规模网络中挖掘出节 点所属的社团信息，同一社团中节点之间的联系 比较密切.例如在依据兴趣爱好构建的社交网络 中进行社团划分，那些兴趣爱好相似的人往往被 划分到同一个社团.另一方面，User-based CF算 法中最核心的部分就是寻找相似用户集合，从社 团的角度来说，就是寻找与目标用户属于同一社 团的其他用户，然后针对同一社团中的其他用户 进行产品推荐.因此,在推荐算法中根据已划分的 社团结构寻找目标用户的相似用户集合,返回一 个数量级更小并且更加精确的与目标用户相似的 用户集合.返回的相似性用户集合形成内部连接 紧密的社团结构，根据该相似性用户集进行推荐, 能够改善推荐精度和效率.
二分网络社团划分（BSSCD)算法根据二分 网络的结构特征计算二分网络中每个节点的相似 性，然后通过聚类的方式将网络中相似性高的节 点划分到同一个社团中.BSSCD算法的步骤
s = getMaxSimilarity( node)；
set. add (node);set. add( s)；list. add (set);
node = v. getNextNeigborNode();}}
step2: / *从邻居节点扩展节点集合* /
for (Node node: set_tag) {
if( node.hasAllVisited()) {
nodelistl = combine (set_tag, list);
} else {
go to stepl;}}
In the same way, get nodelist2; step3: / *合并社团* /
mergeCommunity (nodelistl ,nodelist2) { for (List list: nodelist2) {
community =
getMaxSimilarityCommunity (list, nodelistl);
merge (list, community);}}
End
2 RACD的思想与实现
2. 1
算法思想
User-based CF算法在电子商务网站中得到
广泛应用，但仍存在一些问题，数据稀疏性就是其 中之一.例如:假设某个电影推荐网站中包含几百 万部电影，而平均每个用户评价过的电影只有几 百部，显然,得到的“用户-电影”矩阵十分稀疏. 基于这样的稀疏矩阵给用户推荐电影，推荐的质 量并不高.如果用户和电影的数量不断增加，数据 的稀疏程度也会随之增加，推荐算法的效率就会 更低.User-based CF算法的推荐过程见图l.
User-based CF算法中的一个关键步骤是获
取每个用户的相似用户集合.图2是由用户和项 目（比如商品，电影等）所构成的一个简单的二分 网络，网络中的节点有用户和项目，连边表示用户
第8期陈东明等：基于二分网络社团划分的推荐算法1105
对项目的“动作”，比如购买行为、观看行为等.
n
o
算法对图2所示的网络进行社团划分，会得到如 下划分结果：
社团1:用户1，用户2,用户3,项目1，项目 2,项目3;社团2:用户4,用户5,用户6,项目4, 项目5,项目6,项目7;社团3:用户7,用户8,用
000
相似用户列表
目标用户用户关系矩阵
心
1,立
实际推荐的项目用户关系数据用户偏好数据
圍
日志
户9,用户10,项目8,项目9,项目10.
在用户5的邻居用户中，用户4和用户6与 用户5在同一个社团中，而用户1和用户2却在 另一个社团中，这也证明了用户5与用户4和用 户6的相似度高于用户1和用户2.所以,在推荐 被推荐的项目及推荐值用户偏好集合
图1基于用户的协同过滤的推荐过程
Fig. 1 Recommendation process of user-based
collaborative filtering
图2中，当获取用户5的相似用户集合时,
User-based CF算法首先通过用户5与其邻居用
户的相似性来获取其邻居用户集合，用户5的邻 居用户包括用户4、用户6、用户1和用户2.假设 选取用户4、用户6、用户1和用户2作为用户的 相似用户集合，那么最终系统可能会根据用户4 推荐项目4给用户5;根据用户6推荐项目7给用 户5;根据用户1和用户2推荐项目2和项目3给 用户5.当计算项目的推荐度时，项目4和项目7 的推荐度要远高于项目2和项目3,因为通过相 似性计算，用户5与用户4和用户6的相似度高 于与用户1和用户2的相似度.在实际中,推荐系 统也会优先推荐用户感兴趣程度更高的产品.
项目1项目2项目3
图2
用户和项目构成的网络
Fig. 2 Network composed of users and items
社团划分的目的是把那些联系紧密的节点划 分到同一个社团中，在社交网络中可以理解成把 用户偏好类似的一些用户划分到同一个社团中. 所以，在获取目标用户的相似用户集合之前，可以 通过社团划分算法提前获得目标用户的社团信 息，同一社团中的用户与目标用户之间的相似度 相对较高，这样能够过滤掉一些与目标用户不在 同一社团（即相似度很低）的用户.使用BSSCD
算法中，事先通过社团划分算法对数据集进行过 滤处理，然后根据社团划分的结果去获取目标用 户/的相似用户集,不但可以过滤掉那些虽是目 标用户;'的邻居但相似度却不高（不在同一个社 团中）的用户，得到一个更精确的相似用户集，而 且能够减少一些不必要的计算开销，从而提高推 荐系统实时推荐的效率.
2. 2 RACD 描述
输入:用户对项目的评分数据，目标用户^输出：给目标用户;'进行项目推荐的列表.
1)
根据用户与项目之间的关系建立“用项目”二分网络；
2)
使用BSSCD算法对二分网络S进行社
划分，得到用户所在的社团；
3) 建立用户对项目的评分矩阵；4) 得到目标用户的相似用户集合；5)
计算与目标用户/相似度较高的前用户作为推荐用户集合；
6) 通过相似用户集合得到所有推荐项目以及项目的推荐度，按照项目推荐度的高低返回目 标用户;'的项目推荐列表.
RACD的推荐模型如图3所示.
目标用户与
项目的萃取相似用户集
推荐度
合中所有用户的相似性
图3 RACD的推荐模型
Fig. 3 Recommendation model of RACD
户
个
1106
2. 3 RACD 实现
东北大学学报（自然科学版)第39卷
[ key] ， key] )
reeommand_list. sort (reverse = True) return [ k [1] for k in reeommand_list ]
获取相似性用户集和建立推荐列表是算法的 两个核心步骤.
2. 3. 1
获取推荐对象的相似用户集
首先通过BSSCD算法得到用户所在的社 团，社团划分结果保存为Communities字典;然后 在同一社团内部获得推荐对象的相似用户集合.
def getNeighbors ( uld，user _ diet，item _ user， communities)：
3实验及其结果与分析
实验平台使用Intel(R)Core(TM)i7-
4790 @3. 60 GHz四核处理器,8 GB DDR3内存，
Windows10 64位操作系统，使用Python 3. 5. 1编
^ =[]
user_eommunityId = communities [ uld] for item in user_diet [ uld ]：
for neighbor in item_user[item[0]]: neighbor_eommunityId = communities [ ]
(if neighbor ! = uId and neighbor not in neighbors and user_eommunityId == neighbor_eommunityId):
#添加相似邻居节点
neighbors. append(neighbor)
neighbors_dist =[] for i in neighbors：
#获取相似性
dist = getSimilarity (user_diet [ uId ]，
user_diet [ i ]
neighbors_dist. append([dist，neighbor])
#按照相似性从高到低排序
neighbors_dist. sort (reverse = True)
return neighbors_dist #返回相似用户
2.3.2建立推荐列表
def reeommendByUserFC(neighbors，k)：
#建立推荐字典
reeommand_diet = { } for neighbor in neighbors：
neighbor_user_id = neighbor [ 1 ] items = user_diet [ neighbor_user_id ] for item in items：
if item [ 0 ] not in reeommand_diet ：
reeommand _ diet [ item [0]]= neighbor [ 0 ]else：
reeommand _ diet [ item [0]] + = neighbor [ 0 ]
#建立推荐列表
reeommand_list =[]
for key in reeommand_diet ：
reeommand_list. append ([ reeommand_diet
程语言实现.
采用GroupLens提供的MovieLens数据 集[15]，该数据集包含943个用户和1 682部电影 的100 000条评分记录.
本实验中使用的数据分为3个数量级，分别 是5 000条、2万条和10万条评分数据.首先针对 各个数据集进行处理，形成二分网络，然后使用 BSSCD算法对该网络进行社团划分，得到每个用 户的社团信息，算法运行时间为：5 000条数据， 21.48 s; 2万条数据，56.50 s; 10万条数据， 231. 13 s.可见，随着数据量的增大，BSSCD算法 的处理时间成倍地增加.但是，在RACD的推荐 模型中，BSSCD算法对MovieLens数据的处理过 程一般是在线下完成的，社团数据保存在文件中， 在系统推荐时，通过读取该文件获得用户的社团 数据.所以，在实时推荐时，系统消耗的时间是读 取用户社团信息文件的时间，而不是社团划分消 耗的时间.
给定用户i，通过运行RACD给用户i推荐的 前10部电影的结果如图4所示.
movie id
movie name release
79Fugitive，The (1993)
01-01-1993
222Star Trek：First Contaet(1996)22 -11 -1996
95Aladdin (1992)01 - 01 - 1992153Fish Called Wanda，A(1988)01 - 01 - 1988173prineess Bride，The(1987)01 - 01 - 1987403Vatman( 1989)01 - 01 - 1989294Liar Liar(1997)21 - 03 - 1997258Contaet(1997)11 - 07 - 1997118Twister (1996)10 - 05 - 1996433
Heathers (1989)
01 - 01 - 1989
图4
用户/的推荐结果
Fig. 4 Recommendation result for user /
由于RACD在User-based CF基础上考虑了社团信息，因此推荐结果相对而言更精确.
在不同数据量下，User-basedCF算法与在其
第8期陈东明等：基于二分网络社团划分的推荐算法1107
基础上作了改进的RACD的运行时间如表1所 示.运行时间是完成对数据集中所有用户进行推 荐所花费的时间.
运行时间对比
Table 1 Comparison of running time 数据量
5x1031.453.71
5x10414.9657. 85
1 x 10531. 13145. 35
[7] [5 ]
2010: Advances in Artificial Intelligence. Berlin： Springer， 2010：476 -485.
Chee S H S， Han J， Wang collaborative filtering method
K. RecTree ： an [ J ].
efficient
Lecture Notes in
表1
Computer Science，2001，2114：141 -151.
s
[6] Balabanovi M，Shoham Y. Fab： content-based，collaborative recommendation [ J]. Communications of the ACM，1997，40 (3) ：66 -72.Lops P， de
Gemmis
M， Semeraro
G.
Content-based
RACD算法User-based CF 算法
recommender systems： state of the art and trends [ M]// Recommender Systems Handbook. [ S. l. ]： Springer US， 2011:73 - 105.
与User-based CF算法相比，RACD的运行[8] Soboroff IM， Nicholas C K. Combining content and
时间大幅减少，从而验证了在推荐系统进行实时
推荐时，RACD的推荐效率比User-based CF算法的推荐效率更高.
4结 语
为了解决传统推荐算法存在的一些关键性的 问题,提高推荐系统的性能,本文把二分网络社团 发现算法与推荐算法相结合，提出了基于二分网 络社团划分的推荐算法，对User-based CF算法进 行了改进.采用社团划分算法对数据进行预处理， 得到一个数量级更小并且更加精确的相似用户集 合,提高了数据的相关性，从而减少算法的计算开 销.与User-based CF算法相比，本文算法的实时 推荐效率更高.参考文献：
[1 ]
Adomavicius G， Zhang J. Stability of recommendation
algorithms [ J]. ACM Transactions on Information Systems，
2010,30(4) ：47 -54.
[2 ]
Schedl M，Hauger D，Farrahi K，et al. On the influence of user characteristics on music recommendation algorithms [C ] //European Conference on Information Retrieval. Vienna，2015：339 -345.
[3
]
郑祥云，陈志刚，黄瑞，等.基于主题模型的个性化图书推荐算法[J].计算机应用，2015,35(9):2569 -2573.
(Zheng Xiang-yun，Chen Zhi-gang，Huang Rui，et al. Personalized book recommendation algorithm based on topic model [ J ]. Journal of Computer Applications，2015,35(9)： 2569 - 2573. )
[4]
Cai X，Bain M，Krzywicki A，et al. Collaborative filtering for people to people recommendation in social networks [ C] //AI
collaboration in text filtering [ C/OL ] //Proceedings of the LJCAI’ 99 Workshop on Machine Learning in Information Filtering，1999. [2017 -01 - 23]. http://citeseerx. ist. psu. edu/viewdoc/download? doi = 10. 1. 1. 640. 3677 & rep = rep1&type = pdf.
[ 9 ] Girardi R， Marinho L B. A domain model of Web
recommender
systems
based
on
usage
mining
and
collaborative filtering [ J ]. Requirements Engineering，2007，
12(1) ：23 -40.
[10]
Papagelis M，Plexousakis D. Qualitative analysis of user- based
and
item-based
prediction
algorithms
for
recommendation agents [ J ].
Engineering Applications of
Artificial intelligence，2005，18(7) ：781 -789.
[ 11 ] Zhao Z D， Shang
M.
User-based
collaborative-filtering
recommendation algorithms
on
hadoop [ C ]//
IEEE
International Conference on Knowledge Discovery and Data Mining.Phuket，2010：478 -481.
[12]
孟桓羽，刘真，王芳，等.基于图和改进K近邻模型的高协同过滤推荐算法[J].计算机研究与发展,2017,54(7):
1426 - 1438.
(Meng Huan-yu，Liu Zhen，Wang Fang，et al. An efficient collaborative filtering algorithm based on graph model and improved KNN [ J ].
Journal of Computer Research and
Development，20H，54(1) :1426 -1438.)[13] Wang Q，Li
W， Zhang
X，et
al.
Academic
paper
recommendation based on community detection in citation- collaboration networks [ C]//Asia-Pacific Web Conference: Web
Technologies
and
Applications.
Suzhou， 2016:
124 -136.
[14]
Chen D M，Yan Y B，Wang D Q，et al. Community detection algorithm based on structural similarity for bipartite networks [C] // Proceedings of 7th IEEE International Conference on Software Engineering and Service Science. Beijing ,2016: 173 - 177.
[ 15 ]
Vozalis M G， Margaritis K G. Using SVD and demographic data for the enhancement of generalized collaborative filtering[J]. Information Sciences,2007,177(15) :3017 -3037.
效
因篇幅问题不能全部显示，请点此查看更多更全内容