１、Ｗｅｂ社会网络中的信任模型
已有的一些信任模型都依赖于一个前提，即信任是可传递的［５］．如何利用信任网络评估两个用户之间的信任程度是信任模型关注的重要问题［６］．ＴｉｄａｌＴｒｕｓｔ模型［２］通过广度优先搜索算法，如潮汐的涨落一般，在节点形成的信任网络中寻找所有的最短信任路径，将他们加权求和计算信任值，具有较高的准确度，但算法是以目标节点为核心，将中间节点进行迭代计算；ＭｏｌｅＴｒｕｓｔ［３］模型对此进行了改进，递推过程与ＴｉｄａｌＴｒｕｓｔ相反，以源节点为核心计算信任值；ＲＮ－Ｔｒｕｓｔ模型［４］模拟电阻电路，将用户间的信任看成是电阻中通过的电流值，用计算电流的方式综合所有的信任路径计算信任值，但信任关系无法完全用电阻电路来模拟；为了能尽可能多利用信息同时也能够不受噪音信息的干扰并合理地利用信任网络，ＴｒｕｓｔＷａｌｋｅｒ［７］通过随机游走的方式预测源用户对目标项目的评分，它不仅考虑目标用户的评分还考虑其他相似用户的评分，不过上述模型均没有考虑到群体对信任计算的影响．文献［８］认为不同的人由于一些共同的属性或者相似的行为聚集成群，用户主观地构建这些群，每个群代表一种特定的形象认识（如教师是诚实的），这种群仅仅提供了一种信任印象，而不能真正地从周围用户中获得群体关于目标用户的信任信息；一些推荐系统通过对比目标用户与群组的相似程度来预测信任，如文献［９，１０］通过分析群内用户的同质度（ａｆｆｉｎｉｔｙ）预测信任评分．本文将这些基于同质度的信任模型称为Ｇ－Ａｆｆｉｎｉｔｙ信任模型．同质度表示用户之间关于一些特别的属性的同质程度，也就是类似程度．一个同质群（ａｆｆｉｎｉｔｙｇｒｏｕｐ）也就是由一些具有共有属性的用户所组成的群组．如果目标用户属于群组，则即使没有过直接的交互也会很信任对方．文献［１０］中应用ＬＰ算法（ＬｉｎｋＰｒｅｄｉｃｔｉｏｎ）预测两个用户之间的信任关系，并以此构建信任网络，采用聚类算法将高密度的用户聚类成一个小型社区，并根据社区中边的数量计算同质度．文献［９］中根据属性相似性划分群组，并根据群组内的同质度结合用户本身的行为特征预测信任度．以上的模型都对群组的限制过多，并且，同质度不能反映群组内用户之间的紧密程度，也不能反映群组的信任倾向，更多的是侧重用户各个属性之间的相似度，因此本文重点研究凝聚群对用户进行决策时产生的影响，综合考虑群与群之间的信任度，构建出能够联系用户和群体的信任模型．
２、相关定义
２．１凝聚群相关定义
假设两个节点间的关联度是这两个节点直接交互行为的综合，等同于节点间的直接信任度，详见下节．Ｗｅｂ社会网络包含着一个庞大的用户集，这些用户随着交互的深入而形成不同的关联度，在关联度的作用下会逐渐形成多个以某些用户为中心的簇集．这些簇集具有簇内连接紧密、簇间连接相对稀疏的特点．定义１（凝聚群）：凝聚群是由Ｗｅｂ社会网络中关联度较高的用户（节点）聚集形成的簇集．本文中认为凝聚群之间相互独立不重叠，每个用户属于且仅属于一个凝聚群．我们将凝聚群整体记为Ｏ．下文中将节点ｉ的凝聚群记为Ｏ（ｉ）．每个凝聚群内部节点之间的关联度不同，因此引入群凝聚度的概念．定义２（群凝聚度）：一个凝聚群的群凝聚度是该凝聚群内节点之间关联度的平均值相比于群内节点和群外节点之间关联度平均值，记为η．一般认为节点之间之所以能构成一个凝聚群是因为他们之间的关联度大于他们与群外节点之间的关联度，因此有η≥１．一个凝聚群内的节点之间的关联度越高，群凝聚度就越高．在高凝聚度的群体里，每个节点都倾向于表现出相同的信念［１１］．凝聚群作为整体具有群凝聚度，同时，凝聚群内的每个节点与它所属的凝聚群之间也存在不同的关联度，与所在凝聚群之间的关联度越大，在群内的影响力就越大．定义３（影响力）：节点在凝聚群内的影响力ＣＯ（ｉ），ｉ是它对凝聚群内其他节点之间关联度之和相比于凝聚群内所有节点之间的关联度之和的比值．对于凝聚群的划分采用的是ＭＦＣ（ＭａｘｉｍｕｍＦｌｏｗＣｏｍｍｕｎｉｔｙ）算法［１３，１４］，该算法的基本假设是：网络中的最大流量由网络“瓶颈”的容量决定，而在具有簇结构的网络中，网络“瓶颈”由簇间连接构成．经过反复识别并删除簇间连接，网络簇能够被逐渐分离开来［１３］．根据ＭＦＣ算法，我们认为凝聚群内部是一个弱连通图［１２］．一旦划分好凝聚群就会形成一张映射表，每个节点都可以在映射表中查找到相关凝聚群的所有成员信息，若ｉ不属于任何凝聚群，则可以看成是特殊的凝聚群———只包含一个节点的凝聚群．一个群体的凝聚群划分示例如图１所示．图１中包含３个凝聚群Ｇ１、Ｇ２和Ｇ３．凝聚群内的粗线表示高关联度．Ｇ１和Ｇ３之间的浅色细线代表存在一定的交互，但是关联度不高，Ｇ１与Ｇ２完全不存在交互．
２．２信任度相关定义
假设有节点ｉ（称为源节点）与节点ｊ（称为目标节点）．定义４（直接信任度）：若节点ｉ对节点ｊ具有直接交互历史，则ｉ对ｊ的直接信任度是节点ｉ根据交互历史信任节点ｊ的程度，记为Ｄｉ，ｊ．定义５（群信誉度）：若节点ｉ、ｊ分别属于不同的凝聚群，则节点ｉ对凝聚群Ｏ（ｊ）中与ｉ有过直接交互的节点的直接信任度综合，称为群信誉度ＴＧｉ，Ｏ（ｊ）．群信誉度如图２中所示．其中虚线代表节点间有直接交互历史，红色节点代表ｉ，黄色节点代表ｊ．定义６（群直接信任度）：群直接信任度是凝聚群Ｏ（ｉ）内所有与节点ｊ存在直接交互的节点对于ｊ的直接信任度综合，记为ＤＴＯ（ｉ），ｊ．上述定义６中，ｊ节点可以是群内也可以是群外．群直接交互情形如图３中所示．定义７（群间直接信任度）：群间直接信任度是凝聚群Ｏ（ｉ）中的凝聚群代表对凝聚群Ｏ（ｊ）的群信誉度．记为ＧｄＴＯ（ｉ）Ｏ（ｊ）．由于凝聚群之间不一定存在直接相连的信任路径，因此我们引入群间间接信任度．定义８（群间间接信任度）：群间间接信任度是凝聚群Ｏ（ｉ）通过其他与凝聚群Ｏ（ｊ）直接相连的凝聚群获得的群直接信任度的综合．记为ＩＴＯ（ｉ）Ｏ（ｊ）．由于计算群间间接信任度的公式可以包括群间直接信任度的情况，本文将他们统称为群间信任度ＩＴＯ（ｉ）Ｏ（ｊ），群间信任度如图４所示．图４（ａ）为两个凝聚群直接相连的情况，图４（ｂ）为两个凝聚群之间通过第３个凝聚群连接，其中ｋ为中间凝聚群内的一个节点．定义９（凝聚信任度）：凝聚信任度ＧＴＯ（ｉ），ｊ是凝聚群Ｏ（ｉ）对节点ｊ的群直接信任度与群间信任度的综合．凝聚信任度的概念相对应于传统信任模型中的综合信任度．上述定义中出现的符号和说明见表１．
３、ＧＣ－Ｔｒｕｓｔ模型设计
３．１模型主要思想
ＧＣ－Ｔｒｕｓｔ模型主要考虑的是群与群之间、群与节点之间的这两种信任关系，通过关联度较高的节点聚集形成凝聚群，从源节点ｉ所属凝聚群的角度帮助ｉ判断目标节点ｊ是否能够信任，能够令模型更好地体现出凝聚群的作用．假设已经存在多个凝聚群：１）搜索是否存在从Ｏ（ｉ）到Ｏ（ｊ）的路径（路径上最小单位均为凝聚群），若不存在则将信任度设为０．５；２）若存在凝聚群的路径，则节点ｉ、ｊ之间一定存在着某种关联（根据弱连通图的特性可以证明）分为下面两种情况计算凝聚信任度ＧＴＯ（ｉ），ｊ：ａ）若ｊ在Ｏ（ｉ）内，则ＧＴＯ（ｉ），ｊ等于群直接信任度ＤＴＯ（ｉ），ｊ；ｂ）若ｊ在Ｏ（ｉ）外，综合群直接信任度ＤＴＯ（ｉ），ｊ和群间信任度ＩＴＯ（ｉ）Ｏ（ｊ）计算ＧＴＯ（ｉ），ｊ．ＧＣ－Ｔｒｕｓｔ模型的框架图如图５所示．主要包括５个部分：凝聚群的划分、凝聚度与影响力计算、群直接信任度计算、群间信任度计算以及凝聚信任度计算．系统会在信任度计算开始之前就划分好凝聚群，当用户需要进行信任度计算时，首先根据凝聚群内的成员用户计算凝聚度以及相应的影响力，接着从凝聚群内的角度出发计算对目标用户的群直接信任度，再从凝聚群之间的交互计算群间信任度，最后将３者综合得到凝聚信任度．
３．２群凝聚度的计算
群凝聚度η决定了节点依赖凝聚群的程度．凝聚群的群凝聚度越大，节点也就越倾向于相信群体的直接信任度，反之则节点就越不相信群体．群凝聚度的度量也存在多种方式．例如信任关系与环境关系密切，人在陌生的环境中，会非常依赖朋友以及其他信任关系，而在熟悉的环境中则不会．因此，凝聚群的凝聚强度应该与群所处的外在环境相关．在实际应用中，一个节点通常具有非常不均衡的出入度，交互也存在多种形式，甚至是单向的交互，如微博上的关注就可以单向的，因此凝聚度采用平均值的方式来计算：信任度计算群直接信任度和群间信任度群直接信任度是将凝聚群Ｏ（ｉ）看作一个整体，只要Ｏ（ｉ）内存在与ｊ直接交互过的节点，即可根据式中：ｍａｘ为路径强度；Ｏ（ｓ）为凝聚群Ｏ（ｉ）的邻居凝聚群．计算群间直接信任度ＧｄＴＯ（ｉ）Ｏ（ｊ）时，选举凝聚群Ｏ（ｉ）的群代表ｋ，通过计算ｋ对Ｏ（ｊ）的群信誉度来代表Ｏ（ｋ）对Ｏ（ｊ）的信任度．凝聚群代表既需要有一定的群内影响力又需要对目标凝聚群内节点数量接触得尽量多．
４、相关对比实验
采用Ａｄｖｏｇａｔｏ数据集进行仿真实验，验证本文所提出的ＧＣ－Ｔｒｕｓｔ的准确度．Ａｄｖｏｇａｔｏ数据集中将评分共分为４个不同的等级：Ｏｂｓｅｒｖｅｒ、Ａｐ－ｐｒｅｎｔｉｃｅ、Ｊｏｕｒｎｅｙｅｒ以及Ｍａｓｔｅｒ．比较３种算法：ＧＣ－Ｔｒｕｓｔ、ＴｉｄａｌＴｒｕｓｔ［２］以及基于ＡｆｆｉｎｉｔｙＧｒｏｕｐ［９］的信任预测准确度，并对结果进行分析评价．实验的硬件配置为：Ｉｎｔｅｌ（Ｒ）Ｃｏｒｅ（ＴＭ）２ＤｕｏＣＰＵ２．２０ＧＨｚ，２ＧＢ内存；软件环境为Ｗｉｎｄｏｗｓ７，开发工具为Ｅｃｌｉｐｓｅ３．５．本文进行了２组实验，第１组实验是基于同一数据集进行３种算法对比实验；第２组是基于特定特征的凝聚群进行对比实验．
４．１基于同一数据集的对比实验分析
将数据集表示为有向加权图，共包含有１４０１６个节点和５１３９８条边，并将信任等级映射为０．１、０．３、０．６、０．９．由于原始数据集中高信任度的节点过于集中，且具有较高的出入度，凝聚群的划分效果不理想．而在本实验期望的数据集中，高信任度节点形成的凝聚群能够尽量分散，尽量少的交集．因此首先对数据集进行预处理．将４个信任等级分别映射为０．９、０．３、０．６、０．１，同时将数据集中的度为０节点删除，在剩下５０００多个节点中采用ＭＦＣ算法进行凝聚群划分，得到凝聚群共有２０４２个，其中划分失败的凝聚群共有２７１个（我们认为群凝聚度小于１即为划分失败），占到总凝聚群的１３．２％，失败的主要原因是由于真实的数据集中凝聚群是可重叠的，而本文中限定凝聚群相互独立不重叠．
４．２基于特定特征的对比实验
第２组实验选取划分效果最好的２０个凝聚群，即将群凝聚度与凝聚群规模相乘后的值最大的２０个．一个好的凝聚群不仅仅体现在凝聚度高，而且还应该具有一定的规模．在每个凝聚群中随机选择５条测试评分数据（包括对凝聚群外节点的评分）中比较３个算法的平均绝对偏差．实验结果如图８所示．从图８中明显可见，随着凝聚群的规模和凝聚度的增加，ＧＣ－Ｔｒｕｓｔ的ＭＡＥ明显下降，凝聚群的划分越合理，群凝聚度越高，规模越大，则ＧＣ－Ｔｒｕｓｔ的准确度就越高．因此可以判断凝聚群划分的好坏严重影响着信任预测的准确度．由于ＴｉｄａｌＴｒｕｓｔ计算的信任度是从源节点出发信任路径返回的，而凝聚度越高群体内，节点之间的信任度均较高，因此Ｔｉｄａｌｔｒｕｓｔ的准确度存在一定上升的趋势．Ｇ－Ａｆｆｉｎｉｔｙ的模型虽然由于数据集的原因表现不佳，但是也能够观察到凝聚度高对该算法也产生了积极的影响．
作者：白云璐 翟玉庆 单位：东南大学计算机科学与工程学院 东南大学计算机网络和信息集成教育部重点实验室
相关专题：福建体育科技投稿邮箱 中国律师网
