构建本地信任网络的优化方法

图4-1　一个简单的社交网络示例

用户的社交网络关系存在很多类别，如在图4-1中，用户之间存在朋友、亲戚、邻居、同事等社交关系，不同的社交关系具有不同的信任程度。很多情况下，用户不愿对社交关系进行标注，如在微信中，很多用户都不会对联系人进行标注分类，而且用户间的社交关系信息也常常难以获得。为了识别出用户社交网络中的可信用户群体，我们需要对用户的个人社交网络进行重构，对网络中每个用户的信任度进行区分。

为了构建目标用户的本地信任网络，我们首先需要为目标用户信任容量分配。为了方便处理，在本章中，我们将源节点的信任容量设为1。用户节点间的信任强度采用公式4-1计算。

其中，Wi，j是节点i和j信任边的权重，表示i对j的信任强度，interi，j表示i和j的互动次数，表示i与其他节点的最大互动次数，SoSimi，j表示i对j的社交圈子相似度。当节点i和j的互动次数为0时，则采用SoSimi，j来表示Wi，j。在社交网络中，有些用户虽然互动次数不多，但信任程度却往往很高，比如亲戚关系和师生关系，他们的社交圈子相似程度都很高。SoSimi，j采用公式4-2、4-3进行计算。

(www.xing528.com)

其中，JaSimi，j为节点i与j基于Jaccard系数的社交圈子重合程度，avg（JaSim）为整个社会网络中的平均社交圈子重合度。So（i）、So（j）为节点i与j的社交关系集合，包括节点自身，如图4-1中节点A的社交关系So（A）包括A、B、E三个节点。公式4-3反映的是用户i与j的社交圈子相似程度。

信任流量的传递涉及2个因素，前节点信任容量的大小及信任流量的大小。后续节点的信任容量采用公式4-4进行计算。

其中，Capv代表后续节点v的信任容量，Wk，v为节点k到v的信任强度，即信任流量。如果源节点u到v大于1跳距离，则采用文献[143]Ford Fulkerson算法的思想，选择一条信任流量最大的路径进行信任流量传递，得到节点v的信任容量。

在图4-2中，源节点u的信任容量为1，源节点u到节点A的信任权重Wu，A为0.67，则节点A的信任容量CapA=1×0.67=0.67，同样根据公式4-4可以计算得到节点B、C、D的信任容量。在对节点G进行信任容量计算时，因为存在两条信任流量传播路径，需要分别计算Pathu，B，G和Pathu，C，G的信任流量传播结果，并选择一条信任流量最大的传播路径。其中，Pathu，B，G的计算结果为0.5612，而Pathu，C，G的计算结果为0.748，因此，节点G的信任容量为0.748。根据文献[148]的小世界理论分析，任意两个用户的人际关系距离不超过6，因此，本章将信任流量的最大传播路径深度设置为6，即目标用户本地信任网络中的朋友距离最多为6跳。

图4-2　信任流量传递中的路径选择