Web社会网络论文

1、Web社会网络中的信任模型

已有的一些信任模型都依赖于一个前提，即信任是可传递的［5］．如何利用信任网络评估两个用户之间的信任程度是信任模型关注的重要问题［6］．TidalTrust模型［2］通过广度优先搜索算法，如潮汐的涨落一般，在节点形成的信任网络中寻找所有的最短信任路径，将他们加权求和计算信任值，具有较高的准确度，但算法是以目标节点为核心，将中间节点进行迭代计算；MoleTrust［3］模型对此进行了改进，递推过程与TidalTrust相反，以源节点为核心计算信任值；RN－Trust模型［4］模拟电阻电路，将用户间的信任看成是电阻中通过的电流值，用计算电流的方式综合所有的信任路径计算信任值，但信任关系无法完全用电阻电路来模拟；为了能尽可能多利用信息同时也能够不受噪音信息的干扰并合理地利用信任网络，TrustWalker［7］通过随机游走的方式预测源用户对目标项目的评分，它不仅考虑目标用户的评分还考虑其他相似用户的评分，不过上述模型均没有考虑到群体对信任计算的影响．文献［8］认为不同的人由于一些共同的属性或者相似的行为聚集成群，用户主观地构建这些群，每个群代表一种特定的形象认识（如教师是诚实的），这种群仅仅提供了一种信任印象，而不能真正地从周围用户中获得群体关于目标用户的信任信息；一些推荐系统通过对比目标用户与群组的相似程度来预测信任，如文献［9，10］通过分析群内用户的同质度（affinity）预测信任评分．本文将这些基于同质度的信任模型称为G－Affinity信任模型．同质度表示用户之间关于一些特别的属性的同质程度，也就是类似程度．一个同质群（affinitygroup）也就是由一些具有共有属性的用户所组成的群组．如果目标用户属于群组，则即使没有过直接的交互也会很信任对方．文献［10］中应用LP算法（LinkPrediction）预测两个用户之间的信任关系，并以此构建信任网络，采用聚类算法将高密度的用户聚类成一个小型社区，并根据社区中边的数量计算同质度．文献［9］中根据属性相似性划分群组，并根据群组内的同质度结合用户本身的行为特征预测信任度．以上的模型都对群组的限制过多，并且，同质度不能反映群组内用户之间的紧密程度，也不能反映群组的信任倾向，更多的是侧重用户各个属性之间的相似度，因此本文重点研究凝聚群对用户进行决策时产生的影响，综合考虑群与群之间的信任度，构建出能够联系用户和群体的信任模型．

2、相关定义

2．1凝聚群相关定义

假设两个节点间的关联度是这两个节点直接交互行为的综合，等同于节点间的直接信任度，详见下节．Web社会网络包含着一个庞大的用户集，这些用户随着交互的深入而形成不同的关联度，在关联度的作用下会逐渐形成多个以某些用户为中心的簇集．这些簇集具有簇内连接紧密、簇间连接相对稀疏的特点．定义1（凝聚群）：凝聚群是由Web社会网络中关联度较高的用户（节点）聚集形成的簇集．本文中认为凝聚群之间相互独立不重叠，每个用户属于且仅属于一个凝聚群．我们将凝聚群整体记为O．下文中将节点i的凝聚群记为O（i）．每个凝聚群内部节点之间的关联度不同，因此引入群凝聚度的概念．定义2（群凝聚度）：一个凝聚群的群凝聚度是该凝聚群内节点之间关联度的平均值相比于群内节点和群外节点之间关联度平均值，记为η．一般认为节点之间之所以能构成一个凝聚群是因为他们之间的关联度大于他们与群外节点之间的关联度，因此有η≥1．一个凝聚群内的节点之间的关联度越高，群凝聚度就越高．在高凝聚度的群体里，每个节点都倾向于表现出相同的信念［11］．凝聚群作为整体具有群凝聚度，同时，凝聚群内的每个节点与它所属的凝聚群之间也存在不同的关联度，与所在凝聚群之间的关联度越大，在群内的影响力就越大．定义3（影响力）：节点在凝聚群内的影响力CO（i），i是它对凝聚群内其他节点之间关联度之和相比于凝聚群内所有节点之间的关联度之和的比值．对于凝聚群的划分采用的是MFC（MaximumFlowCommunity）算法［13，14］，该算法的基本假设是：网络中的最大流量由网络“瓶颈”的容量决定，而在具有簇结构的网络中，网络“瓶颈”由簇间连接构成．经过反复识别并删除簇间连接，网络簇能够被逐渐分离开来［13］．根据MFC算法，我们认为凝聚群内部是一个弱连通图［12］．一旦划分好凝聚群就会形成一张映射表，每个节点都可以在映射表中查找到相关凝聚群的所有成员信息，若i不属于任何凝聚群，则可以看成是特殊的凝聚群———只包含一个节点的凝聚群．一个群体的凝聚群划分示例如图1所示．图1中包含3个凝聚群G1、G2和G3．凝聚群内的粗线表示高关联度．G1和G3之间的浅色细线代表存在一定的交互，但是关联度不高，G1与G2完全不存在交互．

2．2信任度相关定义

假设有节点i（称为源节点）与节点j（称为目标节点）．定义4（直接信任度）：若节点i对节点j具有直接交互历史，则i对j的直接信任度是节点i根据交互历史信任节点j的程度，记为Di，j．定义5（群信誉度）：若节点i、j分别属于不同的凝聚群，则节点i对凝聚群O（j）中与i有过直接交互的节点的直接信任度综合，称为群信誉度TGi，O（j）．群信誉度如图2中所示．其中虚线代表节点间有直接交互历史，红色节点代表i，黄色节点代表j．定义6（群直接信任度）：群直接信任度是凝聚群O（i）内所有与节点j存在直接交互的节点对于j的直接信任度综合，记为DTO（i），j．上述定义6中，j节点可以是群内也可以是群外．群直接交互情形如图3中所示．定义7（群间直接信任度）：群间直接信任度是凝聚群O（i）中的凝聚群代表对凝聚群O（j）的群信誉度．记为GdTO（i）O（j）．由于凝聚群之间不一定存在直接相连的信任路径，因此我们引入群间间接信任度．定义8（群间间接信任度）：群间间接信任度是凝聚群O（i）通过其他与凝聚群O（j）直接相连的凝聚群获得的群直接信任度的综合．记为ITO（i）O（j）．由于计算群间间接信任度的公式可以包括群间直接信任度的情况，本文将他们统称为群间信任度ITO（i）O（j），群间信任度如图4所示．图4（a）为两个凝聚群直接相连的情况，图4（b）为两个凝聚群之间通过第3个凝聚群连接，其中k为中间凝聚群内的一个节点．定义9（凝聚信任度）：凝聚信任度GTO（i），j是凝聚群O（i）对节点j的群直接信任度与群间信任度的综合．凝聚信任度的概念相对应于传统信任模型中的综合信任度．上述定义中出现的符号和说明见表1．

3、GC－Trust模型设计

3．1模型主要思想

GC－Trust模型主要考虑的是群与群之间、群与节点之间的这两种信任关系，通过关联度较高的节点聚集形成凝聚群，从源节点i所属凝聚群的角度帮助i判断目标节点j是否能够信任，能够令模型更好地体现出凝聚群的作用．假设已经存在多个凝聚群：1）搜索是否存在从O（i）到O（j）的路径（路径上最小单位均为凝聚群），若不存在则将信任度设为0．5；2）若存在凝聚群的路径，则节点i、j之间一定存在着某种关联（根据弱连通图的特性可以证明）分为下面两种情况计算凝聚信任度GTO（i），j：a）若j在O（i）内，则GTO（i），j等于群直接信任度DTO（i），j；b）若j在O（i）外，综合群直接信任度DTO（i），j和群间信任度ITO（i）O（j）计算GTO（i），j．GC－Trust模型的框架图如图5所示．主要包括5个部分：凝聚群的划分、凝聚度与影响力计算、群直接信任度计算、群间信任度计算以及凝聚信任度计算．系统会在信任度计算开始之前就划分好凝聚群，当用户需要进行信任度计算时，首先根据凝聚群内的成员用户计算凝聚度以及相应的影响力，接着从凝聚群内的角度出发计算对目标用户的群直接信任度，再从凝聚群之间的交互计算群间信任度，最后将3者综合得到凝聚信任度．

3．2群凝聚度的计算

群凝聚度η决定了节点依赖凝聚群的程度．凝聚群的群凝聚度越大，节点也就越倾向于相信群体的直接信任度，反之则节点就越不相信群体．群凝聚度的度量也存在多种方式．例如信任关系与环境关系密切，人在陌生的环境中，会非常依赖朋友以及其他信任关系，而在熟悉的环境中则不会．因此，凝聚群的凝聚强度应该与群所处的外在环境相关．在实际应用中，一个节点通常具有非常不均衡的出入度，交互也存在多种形式，甚至是单向的交互，如微博上的关注就可以单向的，因此凝聚度采用平均值的方式来计算：信任度计算群直接信任度和群间信任度群直接信任度是将凝聚群O（i）看作一个整体，只要O（i）内存在与j直接交互过的节点，即可根据式中：max为路径强度；O（s）为凝聚群O（i）的邻居凝聚群．计算群间直接信任度GdTO（i）O（j）时，选举凝聚群O（i）的群代表k，通过计算k对O（j）的群信誉度来代表O（k）对O（j）的信任度．凝聚群代表既需要有一定的群内影响力又需要对目标凝聚群内节点数量接触得尽量多．

4、相关对比实验

采用Advogato数据集进行仿真实验，验证本文所提出的GC－Trust的准确度．Advogato数据集中将评分共分为4个不同的等级：Observer、Ap－prentice、Journeyer以及Master．比较3种算法：GC－Trust、TidalTrust［2］以及基于AffinityGroup［9］的信任预测准确度，并对结果进行分析评价．实验的硬件配置为：Intel（R）Core（TM）2DuoCPU2．20GHz，2GB内存；软件环境为Windows7，开发工具为Eclipse3．5．本文进行了2组实验，第1组实验是基于同一数据集进行3种算法对比实验；第2组是基于特定特征的凝聚群进行对比实验．

4．1基于同一数据集的对比实验分析

将数据集表示为有向加权图，共包含有14016个节点和51398条边，并将信任等级映射为0．1、0．3、0．6、0．9．由于原始数据集中高信任度的节点过于集中，且具有较高的出入度，凝聚群的划分效果不理想．而在本实验期望的数据集中，高信任度节点形成的凝聚群能够尽量分散，尽量少的交集．因此首先对数据集进行预处理．将4个信任等级分别映射为0．9、0．3、0．6、0．1，同时将数据集中的度为0节点删除，在剩下5000多个节点中采用MFC算法进行凝聚群划分，得到凝聚群共有2042个，其中划分失败的凝聚群共有271个（我们认为群凝聚度小于1即为划分失败），占到总凝聚群的13．2％，失败的主要原因是由于真实的数据集中凝聚群是可重叠的，而本文中限定凝聚群相互独立不重叠．

4．2基于特定特征的对比实验

第2组实验选取划分效果最好的20个凝聚群，即将群凝聚度与凝聚群规模相乘后的值最大的20个．一个好的凝聚群不仅仅体现在凝聚度高，而且还应该具有一定的规模．在每个凝聚群中随机选择5条测试评分数据（包括对凝聚群外节点的评分）中比较3个算法的平均绝对偏差．实验结果如图8所示．从图8中明显可见，随着凝聚群的规模和凝聚度的增加，GC－Trust的MAE明显下降，凝聚群的划分越合理，群凝聚度越高，规模越大，则GC－Trust的准确度就越高．因此可以判断凝聚群划分的好坏严重影响着信任预测的准确度．由于TidalTrust计算的信任度是从源节点出发信任路径返回的，而凝聚度越高群体内，节点之间的信任度均较高，因此Tidaltrust的准确度存在一定上升的趋势．G－Affinity的模型虽然由于数据集的原因表现不佳，但是也能够观察到凝聚度高对该算法也产生了积极的影响．

作者：白云璐 翟玉庆 单位：东南大学计算机科学与工程学院 东南大学计算机网络和信息集成教育部重点实验室