基于协同过滤的Web服务动态社区发现算法

　　0引言

　　社会网络是人与人之间为达到某种特定目的而实现信息沟通的复杂网络。Web服务社区发现是为了将社会网络划分为若干个互相分离的社区，通过挖掘用户社会网络结构、分析用户之间的连接关系来发现用户社区，寻求用户社区中与目标用户相近的用户集合。它是一种解决用户需求个性化问题的可行方法，近年来成为了研究者所关注的焦点。

　　目前，网络社区发现的算法主要有谱平分法、KernighanLin算法、层次聚类算法和GN（GivernNewman）算法。但谱平分法在每次实施网络分割时只能对其进行平分，使得复杂网络在进行社区分割时的效率大大降低；KernighanLin算法只能在知晓所分割社区大小的前提下才能进行网络分割；层次聚类算法中的单连接法难以控制和掌握算法的起始，无法确定最终划分得到的网络社区数量，完全连接法由于时间复杂度高，操作十分困难；GN算法因为其没有有效定义网络拓扑结构，且需要进行重复计算，不适用于大规模的社会网络。总的来说，上述社区发现算法都只把社区发现问题简单地描述为普通聚类，且大都通过构建静态模型进行相似度度量，没有考虑其动态性。

　　针对静态社区算法中把社区发现简单描述为普通聚类的问题，国内外众多学者在考虑网络节点多样性的基础上将研究重心放在重叠社区动态发现算法上，纷纷在上述经典算法的基础上提出了新的社区发现算法。例如团渗算法（CliquePercolationMethod，CPM）[1]、基于局部扩展的重叠社区挖掘算法（LFM）[2]、UEOC（UnfoldandExtractOverlappingCommunities）算法[3]、基于连边相似度的重叠社区发现算法（EGN）[4]、基于信息熵的社区发现（CommunityDetectionBasedonEntropy，CDBE）算法[5]、贪婪的团扩张（GreedyCliqueExpansion，GCE）算法[6]等。然而，这些算法都没有从用户兴趣相似性的角度实现Web服务社区发现，且对于社区规模不同的网络呈现出的有效性各不相同；

　　另外，随着混合参数数值的增加，部分算法的挖掘精确度迅速下降。因此，这些算法在挖掘的社区质量上仍存在不完善之处。

　　协同过滤算法是通过分析用户之间的兴趣相似性来进行项目推荐，其基本思想是通过评分来反映用户对项目的兴趣，利用与用户兴趣相似的若干最近邻用户的评分来推导该用户对未知项目的评分[7]。它主要是基于其他用户的偏好完成商品推荐，因此，只需要计算用户之间的相似性[8]。目前协同过滤算法在Web服务上的应用非常广泛，例如预测Web服务的服务质量（QualityofService，QoS）值[9-10]、建立基于协同过滤的个性化推荐系统[11-12]和识别与优先大软件项目中的需求[13]等。

　　本文提出了基于节点相似性的动态社区发现算法，并使用对社会网络中用户节点的动态描述来计算目标用户和其他用户间的相似度。该算法结合了Web服务的特点以及用户社会网络中节点的多样性，将协同过滤和社会网络应用于Web服务选择领域以解决目前Web服务选择算法的不足。

　　1用户社会网络构建

　　对于Web服务推荐系统来说，挖掘用户社区能够帮助目标用户找到兴趣相投、习性相近的消费用户，同时通过适当的推荐方法对社区中的成员进行有类别的有效推荐。本文考虑将协同推荐算法中的“用户—项目评级矩阵”投射到用户社会网络中，利用“用户—项目评级矩阵”计算出各用户之间的相关性，并以此为基础得到用户的关系矩阵，如图1所示。

　　2基于中心节点的重叠社区动态挖掘

　　本章以用户社会网络中连接节点最多的中心节点为起始网络社区，以社区贡献度为衡量指标考察中心节点的连接节点，通过不断地比较、增添、扩大和更新形成多个全局贡献度饱和的社区，使用重叠度计算将相似度高的社区进行合并，以此来减少社区覆盖率，精确用户分组情况，从而实现对用户社会网络的社区分类和发现不同用户社区之间的不同特点。该重叠社区挖掘主要经历社区挖掘阶段和重叠社区调整阶段。

　　3基于节点相似性的动态社区发现算法

　　由于网络中的节点会随着时间的变化而变化，这就导致了包括社区结构在内的网络结构的动态演化。本章在前面挖掘得到的若干个用户社区的基础上，提出基于节点相似性的动态社区发现算法，从而获得与目标用户位于同一个社区且相关性高的用户组。