基于隐性社会网络社团划分的推荐方法研究

王扶东　杨宏一　薛　冰

（东华大学旭日工商管理学院，上海200051）

·信息资源开发与利用·

基于隐性社会网络社团划分的推荐方法研究

王扶东杨宏一薛冰

（东华大学旭日工商管理学院，上海200051）

结合社会网络分析的推荐方法研究已成为热点。电子商务中用户的动态行为异常丰富，隐含了用户的关联关系 ，利用这些信息进行商品推荐是个新研究思路。分析电子商务系统中用户动态行为关联关系及用户间明确好友关系形成复杂隐性社会网络，将社团划分算法应用到该网络中，则社团内部用户联系紧密且具有更相似的消费偏好 ，据此设计了电子商务中社团内部的推荐方法，应用 R语言进行了算法的验证并与传统的协同过滤算法进行比较。实验表明 ，该推荐算法提高了推荐的质量 ，缓解了传统推荐算法中数据稀疏性及冷启动问题等。

隐性社会网络；社团划分 ；个性化推荐

社会网络为电商的推荐提供了一个协作的社会环境［1］，目前社会网络分析与推荐方法结合的研究成为研究热点。Fengkun Liu等［2］通过实验表明融合社会网络信息与推荐算法，能有效提高推荐的准确度。乔秀全等［3］将社会学与心理学中人们之间信任的产生过程结合到社会网络服务中 ，提高了信任度计算的合理性以及有效性。有学者从多维社会网络出发以提高相似性的计算准确度。Pasquale De Meo等［4］提出了基于SIS的社会网络来收集用户信息。张华青等［5］提出了一种多维加权社会网络的个性化推荐算法。Jianming He等［6］利用社会网络中的信息提出了一种推荐系统的新范式。Yu Shian Chiu等［7］提出了一个Social Networkbased Serendipity推荐系统，这个系统利用社会网络中用户和朋友之间的交互信息 ，找出用户感兴趣但自己却不容易发现的项目推荐给用户。由于数据的庞大，对于推荐速度问题 ，赵学臣［8］和杨长春［9］等学者通过研究社会网络中社团发现，提出高效的推荐模型。

结合社会网络中社团划分的朋友推荐已有很多研究，这为在电商推荐中结合社团划分思想提供了新的思路。网络社团也被称为网络模块、内聚组等［10－11］，它被广泛应用于社会学、计算机图形学等领域 ，根据人们的兴趣特点而形成的社团在网络中呈现出多样性［12］。复杂网络中的社团发现算法很多，目前有代表性的由WH算法［13］和GN算法［14］等，其中GN算法是一种层次分裂算法，应用最广泛，该算法的基本思路是为网络中的每一条边计算边介数，通过不断地从网络中移除边介数最大的边，将整个网络分解为不同的社团［15］。之后Newman陆续提出了Newman快速算法［16］和利用矩阵的特征向量来发现网络社团结构［17］。

随着社会网络的发展，电子商务中不断集成社交网络服务平台，使得电子商务中的用户行为除了简单的对项目评分外，还有很多复杂的用户动态行为，本文通过对电子商务系统中丰富的用户动态行为信息挖掘分析，构建电子商务系统中的隐性社会网络并进行网络社团的划分 ，得到联系更加紧密且用户之间具有更高相似消费偏好的网络社团。根据网络社团的特性进行个性化商品推荐，将有助于提高推荐的质量。

1　隐性社会网络定义

近年来，随着电子商务的发展，在电子商务系统中，不同的用户会对同一件商品进行浏览、购买等行为，这些行为将原来独立的用户联系起来，形成了电子商务中隐性社会网络的一部分 ，即用户之间的弱关系，如图1。同时社会学和心理学研究表明，人们更愿意信任自己的好友，采纳自己好友的意见。社会网络服务电子商务系统中的集成，给我们挖掘并利用真实的人际关系提供了有利的条件 ，故本文将电子商务系统中用户之间明确的好友关系形成隐性社会网络的另一部分，即用户之间的强关系，如图2。

图1　RR电子商务系统中用户弱关联关系图

图2　RR电子商务系统中用户强关联关系图

其中，a，b，c…表示电子商务系统中用户之间存在的弱关联关系类型：a搜索、b浏览、c收藏、d购买、e评价、f参加过同一活动，等等。

最后，由电子商务系统中用户间的这些强弱关系构成了电子商务中的隐性社会网络 （The recessive social network）。隐性社会网络中的点和边分别由电子商务中的用户和用户间强弱关联关系构成。随着用户在电子商务系统中用户行为数据的增多，隐性社会网络规模越来越大，网络密度也逐渐变大。由于本文构建的隐性社会网络与一般社会网络本质上具有类似的性质 ，因此同样可以进行网络社团的划分 ，进而对社团内部进行个性化商品推荐。

2　算法思想与设计

2.1算法的基本思想

由于通过网络社团划分得到的各个社团中的用户之间存在更强的相似性 ，因此社团内部成员之间的推荐更容易被采纳。对电子商务系统中存在的稀疏而庞大的隐性社会网络通过传统的Newman快速算法［16］进行网络社团的划分，找到具有相似兴趣爱好的团体，当有新项目加入进来时，若有用户对其产生行为 ，则搜索网络找到该用户所在社团，再将该项目推荐给社团内其他成员 ，可以缓解传统推荐算法中存在的基本问题。

2.2算法的设计

（1）对隐性社会网络利用Newman快速算法思想进行网络社团划分 ，并通过模块度Q来度量社团划分的合理性。

Newman定义模块度为社区内部的总边数和网络中总边数的比例减去1个期望值，模块度Q的计算［16］如公式 （1）：

其中 ，kv表示点v的度；cv表示点v所在的社区；δ函数δ（cv，cw）的取值定义为：如果 v和w在一个社区，及cv=cw则为1，否则为0。m为网络中边的总数。

本文采用一个向上聚集的方法 ，设定网络 N个独立的社团，即初始化网络社团为一个用户为一个社区。用 N维单位矩阵表示网络社团结构，定义两个变量，如公式 （2）和 （3）：

其中，公式 （2）表示社区 i和社区j内部边数目的和与总边数的比例；公式 （3）表示社区 i内部的点所关联的所有的边数目与总边数的比例。则模块度 Q的计算简化为公式 （4）：

按照Newman的定义，当 Q近似于0时，表示该网络社团划分效果不佳，相反，若 Q接近于1，则表示该网络社团划分最优。

（2）根据网络社团划分算法，对电子商务系统中用户间存在的整个隐性社会网络进行划分，取模块度 Q值最大时得到的网络社团。网络社团结构用二维矩阵来表示，如图3。

图3　RR网络社团结构矩阵

其中矩阵中的行代表网络社团，列代表用户 ，其中数值1表示用户在相应的社区内，相反0表示不在社区内。

（3）当系统中某个用户 j对某个项目i进行了某种行为，根据社团内部成员之间具有较高相似性的特点，通过遍历找到该用户所在的社团，向该社团内部其他成员推荐该项目。

3　实验设计及验证

3.1实验数据集说明

本文的研究对象是电商中的隐性社会网络，对该网络的分析需要用户对项目的行为信息及用户间关系信息等进行收集，而真实数据涉及商业机密，故难以获取。而由明尼苏达大学的GroupLens研究小组收集的MovieLens网站的电影评分数据集是用于验证推荐算法的经典数据，包括了用户对电影作品的评分信息，评分值为1～5分，分值越高表示用户越喜欢该电影，反之，表示用户不喜欢该电影。该数据集本质上和电商中用户对商品的评分相似，故本文实验验证数据集中的用户对项目行为信息中的评分信息由MovieLens数据集中的用户对项目评分信息获得具有一定的合理性。又因为真实电子商系统中用户的行为符合随机分布的特点，因此用户其他行为 ，如浏览、搜索等数据以及用户间关系信息由随机模拟产生。

3.2实验评价标准

本文采用推荐的准确率和全面性去衡量推荐算法的效用。

用查全率 （Recall Ratio，RR）衡量推荐的全面性，即针对某项目v，推荐算法得到的推荐用户集中实际购买了该项目的用户数量 qr与测试数据集中购买该项目v的用户总数量Qt的比值。计算公式 （5）：

用查准率 （Precision Ratio，PR）衡量推荐准确度，即针对某项目v，推荐算法得到的最终推荐用户集中实际购买了该项目的用户数量 qr与推荐算法得到的最终推荐用户集中用户总数量Qr的比值。计算公式如 （6）：

其中查全率和查准率值越大 ，表示本文的推荐算法具有越好的推荐效果。

3.3实验方案

本文将实验数据集分为训练集和测试集两部分 ，训练集用来训练模型，测试集用来评估模型。为了验证算法的推荐效果，本文在原始实验数据集中随机选取5组训练集和测试集，并在每组数据集上进行5次实验，最后取平均值作为实验的最终结果。

在训练集中，以隐性社会网路中某用户 Ui的行为为触发点，若用户Ui对某项目Ij有浏览、收藏等行为信息，通过对网络社团划分后的隐性社会网络中进行宽度优先遍历发现用户 Ui所在的网络社团 ，再将项目 Ij推荐给该社团内的其他所有用户。最后通过与测试数据集中的数据进行查全率与查准率的计算 ，来评估本文算法的效果。

3.4实验结果及分析

使用R语言对算法进行编程实验，首先对隐性社会网络进行网络社团划分 ，结果如表1，再对模块度 Q值变化趋势进行分析，得到变化曲线图4：

表1　RR模块度Q值列表

从表1可知，当社团个数为8时，模块度 Q取得最大值 ，表明网络社团划分效果达到最优。划分的社团如下：

社团［1］：1，2，3，4，5，6，7；

社团［2］：8，9，10，11，12，13，14，15；

社团［3］：16，17，18，19；

社团［4］：20，21，22，23，24，25，26，27，28，29，30；

社团［5］：31，32，33，34，35，36；

社团［6］：37，38，39，40，41，42，43；

社团［7］：44，45，46，47，48，49，50，51；

社团［8］：52，53，54，55，56，57，58，59。

得到最优网络社团后，对社团内成员进行推荐 ，并通过查全率 RR和查准率PR对推荐效果进行验证。通过测试数据集对推荐效果进行验证 ，得到查全率和查准率数据如表2所示。

图4　RR模块度随社区个数变化曲线图

表2　RRRR和PR值

如表2所示，5次实验的查全率 RR和查准率PR的平均值分别为：0.74和0.54，评价指标的值均大于0.5，表明本文的推荐算法有较好的推荐效果。

另外，当有一个新的项目进入系统时，由于缺乏历史评价信息，传统的协同过滤推荐算法无法对其进行推荐。本文提出的基于隐性社会网络社团划分的推荐方法 ，利用社会网络社团划分算法得到用户间具有更紧密关系的网络社团。并通过社团内部用户行为触发产生推荐，大大缩小的推荐的范围，使得推荐具有针对性，从而缓解了冷启动问题并提高了推荐的准确度。

3.5与传统协同过滤算法比较

推荐系统的主要目的就是对用户未来的喜好进行预测，从而进行精准的推荐。因此推荐的准确度是衡量一个推荐算法性能好坏的重要方面。

对于推荐准确度的评价采用平均绝对偏差 （Mean Absolute Error，MAE），通过计算目标用户的预测评分与实际评分间的偏差来衡量预测的准确性，MAE的值越小，预测评分与实际评分的偏差越小，推荐的准确度也就越高。MAE定义如下：

其中， 是用户 u对项目i的真实评分； 是用户 u对项目i的预测评分； 为实验数据中的测试集。

应用相关相似性计算方法［18］计算出用户之间的相似度，记为Sim（u，v）。

其中，Sim（u，v）代表用户 u和用户v之间的相似性；iu，v代表用户u和用户v共同评过分的项目集合；Ru，i代表用户u对项目i的评分；¯Ru表示用户u的平均评分。

根据用户间相似度对目标用户未评分的项目进行评分预测 ，预测评分的计算［19］公式如下 ，得到用户——项目预测评分矩阵，采用上述的数据集产生推荐并与本文中的算法 ，运用R语言进行5次实验对比比较，结果如图5：

其中 ，这里的¯Ru，¯Rv分别代表用户u和用户v在自己所有评分项目上的平均评分；N（u）代表用户 u的最近邻居集。

通过将本文推荐算法与传统的协同过滤推荐算法比较，验证本文推荐算法的准确性。实验结果表明，本文提出推荐算法比传统的协同过滤算法具有更高的推荐准确度，并在一定程度上缓解了传统协同过滤推荐算法中的数据稀疏性问题。

4　结束语

基于 “通过网络社团划分得到的各个社团中的用户之间存在更强的相似性，因此社团内部成员之间的推荐更容易被采纳”的思想，本文利用网络社团划分的方法对电子商务系统中隐性社会网络进行划分 ，并提出了基于隐性社会网络社团划分的个性化商品推荐方法。在模型验证时使用MovieLens数据集借助R语言对算法进行了有效性验证。实验结果表明，本文提出的基于隐性社会网络社团划分的个性化商品推荐方法，对推荐的质量的提高有一定的辅助作用。

图5　RR文本算法与传统协同过滤算法的对比

通过一定的社会网络分析方法 ，对隐性社会网络进行网络社团划分，可以得到联系更加紧密的网络社团，而划分后的网络社团内部的用户之间具有更加相似的消费偏好，以及更强的信任度。在今后的工作中，可以通过一定的方法对网络中用户的消费偏好进行分析，构建消费偏好模型 ，根据该模型结合传统的推荐算法进行商品推荐，将更加符合用户的需求，达到更加高效的个性化商品推荐。

［1］R.Zheng，F.Provost，A.Ghose.Social Network Collaborative Filtering：Preliminary Results［A］.In proceedings of the 6th Workshop on e－Business，2007：47－55.

［2］Fengkun Liu，Hong Joo Lee.Use of social network information to enhance collaborative filtering performance［J］.Expert Systemswith Applications 2010，37：4772－4778.

［3］乔秀全 ，杨春 ，李晓峰 ，等.社交网络服务中一种基于用户上下文的信任度计算方法 ［J］.计算机学报 ，2011，34（12）：2403－2413.

［4］Pasquale De Meo，Antonino Nocera，Giorgio Terracina，Domenico Ursino.Recommendation of similar users，resources and social networks in a Social Internetworking Scenario［J］.Information Sciences 2011，181：1285－1305.

［5］张华青 ，王红 ，滕兆明 ，等.多维加权社会网络中的个性化推荐算法 ［J］.计算机应用 ，2011，9（31）：2408－2428.

［6］Jianming He，Wesley W.Chu.A Social Network－Based Recommender System（SNRS）［J］.Annals of Information Systems，2010，（12）：47－74.

［7］YuShian Chiu，KueiHong Lin，JiaSin Chen.A Social Networkbased Serendipity Recommender System［J］.International Symposium on Intelligent Signal Processing and Communication Systems（ISPACS），2011，（12）：7－9.

［8］赵学臣 .在线社会网络挖掘及个性化推荐研究 ［D］.济南 ：山东师范大学，2012.

［9］杨长春，孙婧 .一种新的基于用户群体关系挖掘的随机漫游社会推荐模型 ［J］.小型微型计算机系统 ，2012，33（3）：65－70.

［10］刘军.社会网络分析导论［M］.北京：社会科学出版社，2004：12－30.

［11］Fu F，Liu L H，Wang L.Empirical analysis of online social networks in the age ofweb2.0［J］.Physica A：StatisticalMechanies and its Applications，2008，387（2）：675－684.

［12］Ganley D，Lampe C.The ties thatbind：Socialnetwork principles in online communities［J］.Decision Support Systems，2009，47（3）：266－274.

［13］Wu F，Huberman B A.Finding communities in linear time：a physics approach［J］.The European Physical Journal B－Condensed Matter and Complex Systems，2004，38（2）：331－338.

［14］Newman M E J.Analysisofweighted networks［J］.Physical Review E，2004，70（5）：056131.

［15］Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Physical review E，2004，69（2）：026113.

［16］Newman M E J.Fast algorithm for detecting community structure in networks［J］.Physic Rev E，2004，69（62）：066133.

［17］Newman M E J.Finding community structure in networks using the eigenvectors of matrices［J］.Physical Review E，2006，74（3）：036104.

［18］Resnick P，Iacovou N，Suchak M，et al.Grouplens：An open architecture for collaborative filtering of netnews［C］∥Proceedings of the 1994 ACM conference on Computer supported cooperative work.. ［S.l.］：［s.n.］，1994：175－186.

［19］Paolo Buono，Maria Francesca Costabile，Stefano Guida.Integrating User Data and Collaborative Filtering in aWeb Recommendation System ［C］.Revised papers from the international Workshops OHS－7，SC －3，and AH－3 on Hypermedia：Openness，Structural Awareness，and Adaptivity，2001：315－321.

（本文责任编辑：孙国雷）

Research on Personalized Recommendation Method Based on Community Partition in the Recessive Social Network

Wang Fudong Yang Hongyi Xue Bing
（College of Business Administration，Donghua University，Shanghai200051，China）

Recommended method combined with social network analysis has become a hot spot.The dynamic behavior of users is unusually rich in e－commerce implied the user's relationship andwith the useof the information for recommendation is a new research idea.According to this can construct a complex recessive social network by the user dynamic behavior relationship and clear relationship between users of the e－commerce and using community partition algorithm on it，the internal users are linked closely and havemore similar consumption preference，and design a recommendedmethod based on community partition. Using R language for the validation of the proposed algorithm and comparisonwith the traditional collaborative filtering algorithm. Experiments show that the recommendation algorithm improves the quality of the recommendation and alleviates the data sparseness and cold start problem in traditional recommendation algorithm.

recessive social network；community partition；personalized recommendation

王扶东 （1974－），女，副教授，硕士生导师，研究方向 ：商业智能与电子商务 ，发表论文10余篇。

10.3969/j.issn.1008－0821.2015.05.009

TP39

A

1008－0821（2015）05－0049－05

2015－01－18

中央高校基本科研业务费专项资金资助 （项目编号：14D110801）。