基于社区发现的个性化推荐技术研究

闵磊

摘  要：随着互联网的发展，网络上各平台的数据规模日益增大，由此产生了信息过载问题，个性化推荐技术是解决该问题的一种有效手段。该文利用社区发现技术“物以类聚、人以群分”的特点，将可能使人们产生相似兴趣的物品进行聚类，并在此基础上研究了基于社区结构的个性化推荐算法。该算法可对推荐物品的新颖性进行调节，并可以缓解冷启动问题。

关键词：社区结构  社区发现  个性化推荐  聚类算法

中图分类号：TP391                           文献标识码：A文章编号：1672-3791（2020）10（c）-0217-03

Abstract： With the development of the Internet， the data scale of platforms on the network is increasing， which leads to the problem of information overload. In this paper， we take advantage of the aggregation for similar objects in community， in which clustering items may arouse similar interests of people， and propose a personalized recommendation algorithm based on community structure. The algorithm is effective for regulating novelty and relieving cold-start problem of recommendation.

Key Words： Community structure; Community detection; Personalized recommendation; Clustering algorithm

在互联网高速发展的背景下，众多行业迎来了前所未有的发展机遇，“互联网+X”正逐渐成为促进社会经济前进的重要因素。网络在为各行业带来契机的同时，其不断增长的数据规模也迫使人们不得不面对一些急需解决的问题。例如，对于线上电子商城中数以万计的商品，如何推送给真正需要它的顾客;在线教育环境下，学习者怎样在海量资料中准确找到对自己确实有帮助的学习资源;浩如烟海的新闻资讯应用中，用户如何高效定位自己感兴趣的报道等。

对于这些由于庞大的数据规模所带来的信息爆炸问题，如果能够采用智能的方式进行自动推荐，那么可以在很大程度上将用户从信息过载的迷茫中解放出来。这种对用户进行的智能推荐，被称为个性化推荐技术[1]。目前，个性化推荐技术在很多方面已取得成功，例如，亚马逊网上商城通过该技术明显提升了销售量，大规模在线教育平台上对个性化推荐技术的应用也极大地促进了个性化学习模式的发展等。

1  个性化推荐技术分析

按照实现的基本原理，个性化推荐技术一般分为基于内容的推荐、基于协同过滤的推荐以及基于网络结构的推荐[2]等。基于内容的推薦技术，对物品或者用户的属性特征进行分析，依据属性的相似性进行推荐，由于该方法对属性数据的要求较高，因此在属性数据不易获取的场景下其应用受到一定限制。基于协同过滤的推荐是目前使用较为广泛的一种技术，它通过物品或者用户彼此之间的协同信息挖掘将有用推荐项过滤过来，该方法准确度较高，但对刚进入系统的实体存在冷启动问题。基于网络结构的推荐，是近年来发展较为迅速的一类方法，它通过网络的拓扑结构体现实体之间的关联关系，其直观性和有效性使其具有较大的发展潜力。

该文基于网络结构，分析了一种利用社区发现进行个性化推荐的方法。该方法充分利用了社区发现算法中“物以类聚，人以群分”的特点，将被用户同时感兴趣的物品进行聚类，以直观可解释的方式向用户推荐感兴趣的物品。由于聚类物品本身蕴含着较强的共现关系，因此对于刚进入系统的用户，也可通过较少的历史兴趣数据进行推荐，在一定程度上可以缓解个性化推荐算法的冷启动问题。

2  基于社区结构的个性化推荐算法

2.1 社区发现技术

社区发现是复杂网络领域一项十分重要的数据挖掘技术，它通过实体间的关联关系将节点按照“物以类聚，人以群分”的机制进行划分，形成社区结构。在社区发现中，实体被表示为网络中的节点，实体之间的关联关系被视为节点之间的连边，以此构建蕴含复杂逻辑的网络结构。

目前社区发现技术较为成熟，包括GN算法、谱分析方法、基于模块度的优化方法、标签传播方法[3-4]等。其中标签传播方法以其线性的时间复杂度，使其成为一种较为高效的算法。考虑到互联网数据的规模性，该文推荐采用标签传播算法进行社区发现。

2.2 网络结构的构建

具备蕴含关联关系的网络结构，是进行社区发现的数据基础。因此，在利用社区结构进行个性化推荐时，首先需要构建这样的网络。我们假定，当用户对物品进行选择、较高评分等操作时，表示他对物品具有一定偏好。如果用户对m个物品具有偏好，则这m个物品之间的连边权值加1（如果两物品间之前无连边，则建立权值为1的边）。对于所有用户，重复此过程，会得到所有物品所构成的加权网络。

在这样的加权网络中，节点表示物品，两节点间如果存在连边则表示它们被相同用户感兴趣。节点之间连边权值越大，说明他们被用户同时感兴趣的概率越大。按照社区发现的基本特征，同一社区中节点之间的连边较为稠密，不同社区节点之间连边较为稀疏。因此，依据这种性质的网络进行社区挖掘，那么同一社区中的节点（物品）被用户同时具备偏好的可能性相对较大。

2.3 利用社区结构进行个性化推荐

对于蕴含节点（物品）共现关系的网络，我们采用加权社区发现算法进行社区结构的挖掘。这里对标签传播社区发现算法进行改进，使之能应用于加权网络。首先，对网络中的各节点赋予不同的标签。然后，按照随机序列对网络中的各节点进行异步标签更新。更新标签时，对邻居节点中各标签按照一定概率进行选择，该概率值为相同标签对应权值之和与当前节点所有邻居节点对应权值之和的比值。最后，在标签更新过程达到稳态或者更新震荡幅度小于一定阈值时，更新过程结束。此时，不同标签所对应的区域即为社区划分的结果。

完成了网络构建和社区发现之后，我们会得到两类数据。一是能体现节点（物品）共现关系的加权网络;二是能体现物品共现密集性的社区结构。基于社区结构的个性化推荐过程，即是依据这两类数据进行。推荐算法描述如下。

输入：加权网络结构、社区发现结果、用户u及其所偏好的物品（节点）集合{Vi}、需要对用户u推荐的物品个数N。

输出：对用户u推荐的N个物品。

步骤1：根据实际情况设置合适的参数α。α表示推荐时偏向于选择同一社区的程度，取值范围可设定为[1]，值越大表示越偏向于选择同一社区的物品进行推荐，当值为0.5时，表示不考虑社区的影响。

步骤2：对于网络中除节点集合{Vi}之外的所有节点Vj，按照公式1计算用户对它的偏好值大小βj。

步骤3：对于集合{Vj}中的所有节点，按照βj值进行倒序排序，取前N个作为推荐输出。

为了考虑社区结构对推荐结果的影响，算法对当前计算的节点与用户已偏好的节点在同一社区时的权值贡献进行了系数处理。该系数α用于衡量社区结构对于推荐力度的影响程度，值越大越偏向于推荐同一社区的物品。设定该系数的目的在于，根据实际需求可以选择对社区结构的作用进行强化，或者为了提高推荐的新颖性而降低社区结构对推荐结果的正向作用。因此，该算法可对推荐的新颖性进行可控调节。

此外，对于较为缺乏偏好数据的用户，该算法也可以进行有效推荐。在仅知道用户较少偏好物品的情况下，由于已经计算出社区结构，因此对于处于同一社区中的物品自然存在较高的推荐概率，可以按照该算法进行推荐。对于这类用户进行的有效推荐，实际上缓解了历史数据欠缺情况下的冷启动问题。

2.4 算法时间复杂度分析

该算法的计算工作主要集中在网络结构的建立、社区发现以及推荐程度的计算和排序上。对于网络结构的建立，如果有N个节点，每个用户平均偏好M的物品，则网络结构建立的时间复杂度为O（MN）;对于社区发现过程，由于采用了近似线性的标签传播算法，因此时间复杂度近似于O（N）;对推荐程度的计算和排序，时间主要用于排序上，排序算法时间可以达到O（Nlog（N））。因此，该算法总的时间复杂度近似为O（MN）+O（N）+O（Nlog（N）），即O（MN）+O（Nlog（N））。

3 结语

在互联网时代，海量数据所带来的信息过载问题，极大地影响了信息技术的应用效率。而个性化推荐技术，是解决该问题的一种有效方式。该文利用社区发现技术“物以类聚、人以群分”的特点，将共现性较强的物品进行聚类，并利用该聚类性质进行个性化的推荐。该算法除了可以提供有效的推荐外，还可对推荐的新颖性进行调节，并可在一定程度上对冷启动问题进行缓解。

参考文献

[1] 王绍卿，李鑫鑫，孙福振，等.个性化新闻推荐技术研究综述[J].计算机科学与探索，2020，14（1）：18-29.

[2] 黄乐乐，马慧芳，李宁，等.基于二分图划分联合聚类的协同过滤推荐算法[J].计算机工程与科学，2019，41（11）：2040-2047.

[3] 张蕾，钱峰，赵姝，等.基于边权的稳定标签传播社区发现算法[J].小型微型计算机系统，2019，40（2）：314-319.

[4] 郑文萍，车晨浩，钱宇华，等.一种基于标签传播的两阶段社区发现算法[J].计算机研究与发展，2018，55（9）：1959-1971.

[5] 檀亞宁，金泽明，陈辉.基于项目协同过滤的电视产品营销推荐模型[J].科技资讯，2019，17（32）：214-215，217.

[6] 肖小月.浅谈个性化推荐系统[J].科技创新导报，2018，15（2）：148，150.