基于社区划分的学术论文推荐模型

黄泳航 汤庸 李春英 汤志康 刘继伟

摘要：针对学术社交网络独有的社交性，构建了基于社区划分的学术论文推荐模型。模型选择社区复杂好友关系网络图中最大连通分量作为数据处理逻辑单元，在此基础上进行核心关系网划分，并采用非参数控制的方式，在所建立的核心关系网内建立标签，在学术社交网络中通过标签传播进行社区划分，根据社区划分结果在社区内部的用户之间推荐学术论文。该社区划分算法与经典社区划分算法在人工网络上进行仿真实验，结果表明该算法在不同特征的人工网络上皆能取得良好的社区发现质量。

关键词：核心关系网；社区划分；标签传播；自适应阈值；学术论文推荐

中图分类号：TP391.3 文献标志码：A

Abstract：An academic paper recommendation model based on community partition was proposed according to sociability in social network. The model regarded the largest connected component in complex network as the logic unit in data processing， and divided up the largest connected component into nonintersect kernel subnetwork. The labels would be established according to kernel subnetwork by nonparameter control mode. Communities were divided in scholar social network through label propagation， and academic papers were recommended among the users in the communities by the results of the community partition. The proposed community partition method was compared with the classic community partition method in the experiments on artificial network. The experimental results show that the proposed method can achieve good community partition qualities on different characteristic artificial networks.

Key words：kernel subnetwork； community partition； label propagation； selfadaptive threshold； academic paper recommendation

0 引言

近几年，社交网站发展迅速，已渗入主流文化以及人们的日常生活中，备受网民关注[1]。随着学术社交网络的兴起，学者在学术社交网络中发掘论文的需求激增。面对学术社交网络中海量的论文，学者难以检索高质量或获取自己感兴趣的论文；同时，优秀的推荐算法不仅可以为学者寻找其感兴趣的论文，而且也可以为学术社交网络谋取丰厚的利润。因此，发掘用户感兴趣的论文成为一个新的研究方向。

目前，关于社交网络的推荐算法，国内外的研究主要分为两个方面：一个方面是以现有的信息为基础，通过语义分析进行发掘建立推荐模型。例如，文献[2]提出的信息库学习自动机的推荐模型，该模型是利用连续型学习自动机在随机和高噪声环境中优化参数的卓越性能，代替原有的梯度下降算法进行大型稀疏矩阵的奇异值分解计算，使得重构矩阵与原矩阵之间的误差进一步降低，提高了后续预测算法的精确度。文献[3]对学生能力评估过程进行主题建模，采用局部社区发现算法对学生各方面能力进行合理的等级分类等。与此同时，以用户的使用习惯为基础，根据用户的登录信息等推荐模式也可以归为此类。例如，文献[4]通过考虑用户对服务的兴趣剖面以及服务对标签的满足度剖面，所提出的基于用户兴趣和服务满足度的服务搜索和推荐算法。文献[5]以用户所发表的内容建立学习自动机和训练样本，在训练样本的基础上进行推荐。文献[6]则以多用户所组成的群体为单位，根据群体所发表的信息与发表的地点建立的推荐模型等等。然而，这类算法建立于用户所填写的信息上，对一些缺乏信息的用户欠缺考虑。对于这部分在社交网络的惰性群体，认为对最后的好友推荐结果影响力不大，往往采取直接剔除的方法，使得算法数据集的准确性受到一定的影响，只能在具有大量活跃用户的社区进行推荐。另一方面是先在社交复杂网络中固有的拓扑关系图之上进行社区发现，划分社区之后再发掘其中潜在关系进行推荐。此方面的社区发现方式多种多样。例如，文献[7]利用拓扑图中的完全子图建立标签，根据标签在图中的节点传播结果划分社区。文献[8]则以拓扑图中的三角形拓扑结构为网络社区分层嵌套模式中的基本社区单元，经过粗化迭代，令网络拓扑结构图中的高阶多边形逐步向低阶多边形演化，最终演化成社区。与此成为对比，文献[9]则首先为每个节点赋予一个独立的标签，然后根据节点的影响力大小进行排序，在标签传播的过程中，综合网络的结构传播特性和节点的属性特征共同计算标签传播的概率，同时利用节点的历史标签记录修正标签更新结果，最后将传播后具有相同标签的节点划分为同一社区。也有部分学者利用物理分析的方法进行社区发现。例如，文献[10]把拓扑关系图上的节点视为粒子，在之间建立引力作用，通过彼此的引力关系划分社区；文献[11]则是对边建立多层光谱关系，通过一系列的数学分析求出社区。

然而，由于学术社交网络存在大量的学术论文可供分享，以上算法忽视单一学者与分享论文形成一对多的关系，导致最终学术论文推荐并不理想。因此，部分学者在此基础上，又针对学术论文推荐的特殊性提出不同的推荐模型：文献[12]介绍了一种根据论文摘要建立数据库索引，通过对索引进行语义分析得出推荐结果的方法；文献[13]则是基于论文的内容与引用关系进行推荐；文献[14]通过提取论文的特征，建立集成的科技论文推荐框架，为科研社交网络中的研究者提供个性化论文推荐服务；文献[15]则根据文档在主题上的分布概率，考虑主题之间的关联，发掘文档间的潜在关系建立垂直模型进行推荐；文献[16]则对PageRank算法和内容过滤进行改进，提出了一种面向论文投稿推荐的垂直搜索引擎的主要模块设计及实现方法。虽然上述的方法对于学术论文的推荐有一定的贡献，但是在推荐的过程中忽视了学术社交网络中的好友关系，造成一定程度上的精度丢失，从这些算法的推荐结果来看，为用户所推荐论文与该用户缺乏关联度，推荐结果不是很理想。

针对学术社交网络独有的社交性，本文拟构建一个基于社区划分的学术论文推荐模型。该模型以学术社交网络的好友关系拓扑图为基础，在其中发现核心关系子网。以核心关系网中节点的标签和权重为基础，更新整个学术社交网络中节点标签及权重。标签传播过程中采用自适应阈值方式剔除无意义标签进行社区发现。在学术社交网络中建立社区，在社区内好友间共享文献达到论文推荐的目的。

1 自适应标签传播算法

本模型着重考虑学术社区中的社交关系，在推荐学术论文之前根据学术社交网络中的好友拓扑关系图发掘其中的社区。因此，本文首先提出基于核心关系网的社区划分算法——自适应标签传播算法（Adaptive Label Propagation Algorithm， ALPA）。该社区划分算法在学术社交网络拓扑图中发掘核心关系网并对核心关系网中的节点赋予标签和权重，然后采用同步标签传播的方式计算全部节点的标签和权重，在算法的迭代过程中利用自适应阈值剔除不合理的标签，最终拥有同一个标签的节点属于同一个社区。

1.1 基本定义

定义1 完全图。学术社交网络的好友关系拓扑图由图G={V， E}表示，其中V表示用户的集合，E表示好友关系的集合。若图G存在子集Gs，且Gs中任意两点都相邻，则称此图为完全图。

定义2 核心关系网。在图G={V， E}中，以V中未赋予标签的度数最大的节点vi及其邻接节点中未赋予标签的度数最大的节点vj为初始边寻找完全图Gs。若GsG，且不存在任何完全图GtG，使得GsGt，则称Gs为核心关系网。

1.2 算法初始化

因为该算法是根据核心关系网建立社区，所以每一个社区至少包含一个核心关系网。据此，算法初始化的关键是在G中寻找核心关系网。具体过程如下所示。

1）对V中所有节点赋予label=0；

2）取V中label=0的节点，按照定义2寻找核心关系网。如果同时存在多个满足label=0且度数最大的点，则随机选取一个；

3）label=label+1；

4）将有序对（label，1）赋予给核心关系网节点对应的标签集，结果为{（label，1）}，其中label为节点的标签，1为该标签对应的权重；

5）重复2）～4），直到在G={V， E}中不存在核心关系网，过程停止。

1.3 标签传播

在核心关系网建立之后，利用自适应标签传播算法计算节点的标签和权重，达到极大限度地减少冗余标签，提高模型的稳定性的目的。采用稳定的同步标签传播方式，根据复杂网络小世界原则，节点在算法的多次迭代过程后一定会获得标签。标签权重的大小与节点在多个标签中的度数分布有关。为了避免标签被过度传播，一些权重较小的标签在算法迭代过程中不断被剔除。具体标签更新规则如下所示。

1.4 算法复杂度分析

设复杂网络图G有n个节点。初始化的时候，对点集V中所有的节点赋予label=0，时间复杂度为O（n）。在图中建立核心关系网，由于要取label=0的度数最大的节点v，先对V中的所有节点按度数进行排序，将消耗O（n2）的时间复杂度。算法初始化时，需要考察每一个节点v的邻接节点以建立核心关系网，需要O（n log n）的时间复杂度。最终对核心关系网中的点赋予（label，1）的权重，考虑到图的节点有可能都被划入核心关系网中，故将达到O（n）的时间复杂度。因此，建立核心关系网的时间复杂度为最高阶O（n2）。在标签传播阶段，每一个节点v的标签更新仅在其邻接矩阵中进行，此过程需要的时间复杂度为O（n log n）。最后删除重叠社区的子社区，时间复杂度同样为O（n log n）。综上，社区发现算法的时间复杂度为O（n）+O（n2）+O（n log n），近似为平方阶O（n2）。

2 实验分析

2.1 社区划分性能分析与评估

本文将设计实验对算法社区划分性能进行分析与评估。实验将采用Benchmark Graphs （BG）图集作为人工网络数据集。BG图集是利用特定参数产生的、社区规模不均一分布的复杂网络，其是在社区发现算法缺乏统一评价标准情况下的一种用于直接反应社区发现算法优劣的人工网络[17]。BG图集将产生一个固有的社区划分结果与其生成的人工网络相匹配。如果一个社区划分算法在BG图集产生的人工网络上划分结果，与BG图集固有的社区划分结果越为吻合，则说明该社区划分算法越为精准。

本文设置的BG图集人工网络具体参数如表1所示。n是网络的节点数，k为节点的平均度数，kmax为节点的最大度数，cmax是一个社区的最大节点数，cmin为一个社区的最小节点数。混合参数μ决定社区结构明显程度，其取值范围是[0，1]。取值越大，生成的人工网络社区结构越不明显。当取值为0时，整个网络是一个社区；当取值为1时，则是一个随机网络。如图4所示的，2个对应μ值分别为0.1和0.8的人工网络，从中可以非常直观地看出，μ值较小时，BG图集产生的人工网络社区结构明显；而当μ值较大时，人工网络的社区结构则变得模糊。随着设置的μ值增大，社区划分算法越难以在此类型的人工网络上实现社区划分，划分结果越难以与BG图集固有的社区划分结果吻合。

实验将本文算法与标签传播算法（Label Propagation Algorithm， LPA）[19]、 COPRA算法[20]、CFinder算法[21]等经典社区划分算法进行对比，对本文算法的社区划分性能进行评估。在实验运行之前，由于COPRA算法在提前预测重叠社区数x的值才能执行，考虑到设置的BG图集重叠社区数为4，所以将COPRA算法的x分别预设为x=4，以最适状态执行，同时设置x=5作为此算法不能在最适状态运行时的对照组。

在上述数据集上分别运行ALPA、COPRA算法（x=4）和COPRA算法（x=5）、LPA、CFinder算法各10次，使用式（1）计算NMI值，执行多次取平均值，用于消除各算法在标签传播时不稳定所造成的误差。各运行10次取平均值作最终的结果，考虑执行结果与BG图集固有的社区划分结果的吻合程度，从而评测各个算法的社区划分性能。各个数据集上的实验结果如图5所示。

当μ≥0.3时，LPA无法发现社区结构；同时当μ≥0.6时，COPRA算法无法发现社区结构。而本文所提出的ALPA无论社区结构是否明显，皆能保持一个良好的社区发现质量，虽然与此同时表现较好的CFinder算法也能够在各个μ值上的数据集上发现社区，但是社区发现性能随着μ值的加大而不如ALPA，并且在各个数据集中出现不稳定的现象。图5（c）和（d）显示的是在规模较小的人工网络上的社区发现质量。随着社区结构变得不明显，LPA、COPRA算法的性能不断下降，CFinder算法的性能在不稳定的同时，由始至终未能达到ALPA的高性能， ALPA则一直保持着较好的社区发现质量。无论社区结构如何，ALPA则仍然保持着良好的态势，能够稳定、良好地划分社区；同时ALPA无须像COPRA算法预设置复杂网络可能重叠社区数x，由于具有自适应的特点外，所以无论待发现复杂网络社区规模大小，社区结构是否模糊，皆能很好地发现社区。

2.2 推荐模型的应用

通过上述的社区划分性能分析与评估对比得知，ALPA具有良好的社区发现性能。因此可以将ALPA应用于自主开发的面向科研工作者的社交网络服务平台——学者网（http：//www.scholat.com），为用户发掘更多潜在学术论文。利用ALPA在学者网内的好友拓扑关系图上划分出社区结构，对同一社区中的用户分享的论文以点击率进行倒序排序，并选择点击率前10位的论文推送给社区内的每位学者。

本文在学者网用户数据中选取11000条好友关系数据，消除噪声之后共10920条数据进行实验。如图6（a）所示，在应用本算法之前，此10920条数据好友关系所构成的是一个未划分社区的好友关系复杂网络。在该复杂网络中，应用ALPA经历5次迭代，如图6（b）所示，最终划分出181个极大团，108个社区，对各个社区中的用户，推荐该社区内所有用户所发表的论文。

通过使用本文的潜在好友推荐方法，学者网已为其注册用户提供了有效的潜在学术论文推荐服务，如图7所示。这是本文算法为学者网中一位属于社区第1、2、3、7、28、56社区用户所推荐的学术论文的效果图，所推荐的学术论文皆是该用户的好友所分享的，该用户与其大多数好友之间存在共同兴趣与研究领域，必然会乐于接受推荐结果，如果该用户需要浏览更多推荐结果，可以点击下方的按钮，加载更多的论文推荐结果。

3 结语

本文设计了一种基于社区划分的学术论文推荐模型。首先对算法进行初始化，获得复杂网络中的全部核心关系网，再根据核心关系网中节点的标签和权重，采用同步标签传播方式更新网络中节点的标签和权重，最终将网络划分为若干个社区，并对社区内的用户推荐学术论文。ALPA采用自适应阈值的处理方式剔除无意义的标签，避免了预先输入参数对未知复杂网络的局限性，因此其更能够自适应于真实的社交网络。随着社交网络的蓬勃发展，社交网络中用户之间的关系也更加错综复杂，规模也在迅速增大。在此背景下，如何提高推荐算法的时间复杂度是一个可以继续研究的方向。另一方面，可以对该算法进行并行化处理，使其能够应对复杂网络大数据所带来的挑战。

参考文献：

[1]高娴子，蒋建国.近年来我国社交网络发展研究[D].广州：暨南大学，2011：1-61.（GAO X Z， JIANG J G. Research on the development of Chinas social network[D]. Guangzhou： Jinan University， 2011：1-61.）

[2]荆羽纯，葛昊，江文，等.一种基于学习自动机的推荐算法改进[J].计算机应用研究，2016，34（1）：32-34.（JING Y C， GE H， JIANG W， et al. Learning automatabased improvement for recommendation algorithm[J]. Application Research of Computers， 2016，34（1）：32-34.）

[3]石博，何楚，卓桐，等.慕课教学中基于局部社区发现的主题交互模型[J].计算机应用研究，2014，32（6）：1724-1727.（SHI B， HE C， ZHUO T， et al. Topic interaction model based on local community detection for MOOC teaching process[J]. Application Research of Computers， 2014，32（6）：1724-1727.）

[4]邓华平，赵海燕，陈庆奎， 等.基于用户兴趣和服务满足度的服务搜索和推荐算法[J].计算机应用研究，2014，32（9）：2613-2617.（DENG H P， ZHAO H Y， CHEN Q K， et al. Service search and recommendation algorithm based on users interest and service satisfaction[J]. Application Research of Computers， 2014， 32（9）：2613-2617.）

[5]HANG Y. Incorporating phraselevel sentiment analysis on textual reviews for personalized recommendation[C]// WSDM 2015： Proceedings of the 8th ACM International Conference on Web Search and Data Mining.New York：ACM， 2015： 435-440.

[6]YUAN Q， CONG G， LIN C. COM： a generative model for group recommendation[C]// KDD14： Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York：ACM， 2014：80-90.

[7]沈海燕，李星毅.一种新的基于标签传播的重叠社区发现算法 [J].软件导刊，2015，14（4）：59-62.（SHEN H Y， LI X Y. A new overlapping community structure detecting algorithm by label propagation[J]. Software Guide， 2015，14（4）：59-62.）

[8]康颖，于博，古晓艳，等.一种面向大规模社会信息网络的多层社区发现算法[J].计算机学报， 2015，38（1）：1-14.（KANG Y， YU B， GU X Y，et al. A multilevel community detection algorithm for largescale social information networks[J]. Chinese Journal of Computers， 2015，38（1）：1-14.）

[9]刘世超，朱福喜，甘琳.基于标签传播概率的重叠社区发现算法[J/OL].[2015-07-22].http：//www.cnki.net/kcms/detail/11.1826.TP.20150722.1205.014.html.（LIU S C， ZHU F X， GAN L. A labelpropagationprobabilitybased algorithm for overlapping community detection[J/OL]. [2015-07-22].http：//www.cnki.net/kcms/detail/11.1826.TP.20150722.1205.014.html）

[10]董宇欣，迟阔，印桂生.基于引力作用的可选粒度社区发现算法[J].哈尔滨工程大学学报，2015，36（6）：1-6.（DONG Y X， CHI K， YIN G S. Optional granularity community detection algorithm based on gravitation[J]. Journal of Harbin Engineering University， 2015，36（6）：1-6.）

[11]ZHANG X， NEWMAN M. Multiway spectral community detection in networks[EB/OL].[2015-01-22]. http：//arxiv.org/abs/1507.05108.

[12]HOXHA K， KIKA A， GANI E， et al. Towards a modular recommender system for research papers written in Albanian[J]. International Journal of Advanced Computer Science and Applications， 2015，5（4）：160-168.

[13]蔡阿妮，周傲英. 基于内容与引用关系的学术论文推荐[D].上海：华东师范大学，2014：1-82.（CAI A N， ZHOU A Y. Recommending research paper based on content and citation graph[D].Shanghai： East China Normal University， 2014：1-82.）

[14]孙见山，刘志迎，马建.科研社交网络中的论文推荐[D].合肥：中国科学技术大学， 2014：1-101.（SUN J S， LIU Z Y，MA J. Article recommendation in research social network[D].Hefei： University of Science and Technology of China， 2014：1-101.）

[15]黄泽明，鲁明羽.基于主题模型的学术论文推荐系统研究[D].大连：大连海事大学， 2013：1-68.（HUANG Z M， LU M Y. Research on recommended system of scholar paper based on topic model[D].Dalian： Dalian Maritime University， 2013：1-68.）

[16]徐镇，李廉.基于垂直搜索引擎的论文投稿推荐系统研究[D].兰州：兰州大学，2014：1-67.（XU Z，LI X. Research on a recommendation system for paper submission based on vertical search engine[D]. Lanzhou： Lanzhou University， 2014：1-67.）

[17]LANCICHINETTI A， FORTUNATO S， RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E， 2008，78（4）：046110.

[18]LANCICHINETTI A， FORTUNATO S， KERTESZ J. Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics， 2009，11（3）：033015.

[19]RAGHAVAN U， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in largescale networks[J]. Physical Review E， 2011，84（3）：036103.

[20]GREGORY S. Finding overlapping communities in networks by label [J].New Journal of Physics， 2010， 12（10）：103018.

[21]PALLA G， DERENYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature， 2005， 435（7043）： 814-818.