基于“小世界”网络原理约简在线社交网络的算法研究

徐常福　万一红　钟叶　胡文蓓　林容如

摘要：本文主要考虑到直接在大规模在线社交网络下评估用户个体问信任成本太高，因此，我们提出一种基于“小世界”网络原理约简在线社交网络的算法。为验证该方法的有效性，我们在Epinions数据集上进行了多方面的实验测试。实验结果表明，约简后的信任网络可以较好地评估原始在线社交网络中用户个体问的信任程度。

关键词：社交网络；“小世界”；约简社交网络；信任评估

0引言

随着Internet的普及和盛行，每天都有数以万计的新用户加入到在线社交网络中，来与其他用户进行信息交流和交互，其中很多是互不相識的用户。因此，评估这些用户之间的信任程度，对提高社交网络服务质量和加强其安全性具有非常重要的作用。本文提出一种基于“小世界”网络原理约简在线社交网络的算法（SWRSN）。该算法对原始社交网络进行了约简，采用了用户活动域（domain）信息，该信息相对于其它信任信息来说是客观的、稳定的。因此，该算法具有较低的复杂度，并且对恶意攻击也有一定的鲁棒性。

1算法模型

本算法主要包括三个关键步骤：（1）原始社交网络的约简，即根据“小世界”网络原理约简原始社交网络；（2）计算信任网络中用户个体问的信任值，即通过计算约简的信任网络中用户个体问的信任值，从而间接评估原始社交网络中用户个体问信任程度。

1.1约简原始社交网络

约简原始社交网络的整个过程其主要是原始的信任网络基础上，根据“小世界”网络原理，采用广度优先算法搜索尽可能多的源节点到目标节点之间的短路径（最大步长Max Length=6），并且删除路径中任意一条边的信任值小于给定信任阈值（一般设置信任阈值th=0.5）的路径。

1.2计算信任网络中用户个体问的信任值

在本节中，主要是在约简的信任网络基础上，计算源节点要目标节点的预测信任值。这里我们采用4种较为常见的信任评估策略，如表1.1所示。下面介绍信任传播和信任整合操作。

信任传播操作：从source节点到target节点路径中用户的信任传播。两种较为常见的传播操作是取最小值（Min）传播和取乘积传播（Multi）。前者是指取路径上最小的推荐信任值，后者是指取路径上所有推荐信任值的乘积。

信任整合操作：从source节点到target节点中所有路径的信任整合。两种较为常见的信任整合操作为取最大值（Max）和取加权平均值（WAve）。前者是指取所有路径中最大的信任传播值，后者是指取所有路径的信任传播值的加权平均值。

2实验评估

2.1实验设计

本论文主要采用留一法进行实验。采用数据集为Epinions，该数据集为社交网络中较为典型的实验测试数据集。如果Sollrce到target之间有一条直接的信任边，则这条边将被隐去。这时，source到target之间的信任值将通过它们之间信任图来计算。

本实验采用了较为常见的四个精度指标来评估本论文提出的算法的有效性，分别为：绝对误差（Absolute error）、精度（Precision）、召回率（Re-call）和F分数（F-Score），计算公式如表2.1所示。其中表示实际中信任的用户集，表示当前算法预测为信任的用户集。

由表2.2可知，最小的Precision为0.7248，说明本论文提出的BDSWRSN算法具有较好的信任预测精度。此外，最小的F-Score为0.5875，剩下F-Score都在0.62以上，这也说明BDSWRSN算法的可以较为有效地帮助预测在线社交网络中用户个体问信任程度。

3结论

在本文中，我们采用了一种标准的留一法评估技术和社交网络测试中常用的Epinions数据集，采用信任预测精度作为衡量指标，对本文提出的基于“小世界”网络约简在线社交网络算法（SWRSN）进行了有效性地评估。实验结果显示，采用Multi-Wave信任评估策略，约简后的信任网络的F-Score为0.6504，这说明SWRSN算法可以较好地评估原始在线社交网络中用户个体间的信任程度。