基于信任度的并行化社区发现算法

余紫丹，虞慧群

(1．华东理工大学计算机科学与工程系，上海200237;2．上海市计算机软件评测重点实验室，上海201112)

1 概述

社交网络作为人类最复杂的网络之一，与其他的网络的不同之处在于，它是由多个社区组成的。社区形成的原因多种多样，但社区最重要的基础，是信任关系。信任是人类社会活动的基石，社区内的信任关系维系了社区的存在、发展。

目前社会性网络中对信任的研究还处于起步阶段，研究成果较少，鲜有提供准确计算信任度的度量方法。文献［1］提出利用FOAF(Friend of a Friend)在基于Web的社交网络中计算没有直接联系用户之间的信任度关系，但是其信任度仅有信任、不信任两种取值使其很难用于现实的社交网络环境中;文献［2］提出了在基于地理位置的社会性网络中结合链接关系与社会声誉来决策信任度的机制，但该机制只适用于特定的网络，缺乏普适性。文献［3］提出的PGP(Pretty Good Privacy)模型把信任的主动权留给用户自己，通过基于推荐者的网状信任模型来进行信任等级的判断。

然而，在PGP的信任模型内，信任链的长度最大为2，信任度衡量粒度也只有信任、不信任2种选择，难以应用在社交网络上。针对于此，目前已有不少根据信任推荐模型的社交网络信任度计算方法，例如文献［4］提出一种如何挑选可信赖用户进行信任推荐的算法。文献［5］利用节点之间的链接关系来发现2个目标用户之间的最优可信信任路径，但未考虑次要信任路经对两者信任关系带来的影响。……