基于边演化的信任链时序预测模型

孙特点

（上海海事大学经济管理学院,上海 201000）

0 引言

在网络交易中，信任和信誉机制显得尤为重要。甘早斌[1]提出了电子商务下的信任网络构造与优化，通过Visual Studio提供了信任化网络的自动生成工具，很好地揭示了电商环境下的信任关系。莫家庆[2]运用改进的Einstein算子，给出信上实体的评估过程。马尧[3]用多维向量通过买家的记录构建直接信任度，给出了动态环境下的信任算法。

近年来，链路预测研究方法受到了极大关注。张丰基于马氏链[4]对信任进行了预测。郭景峰[5]等利用链接之间的结构信息引入时间序列预测了通信网络链接。陈莎等人考虑共同邻居及偏好，基于混合相似性[6]指标提高了链路预测的精度。邓志宏用链路预测误差[7]描述了网络演化趋势，对链路预测结果进行了修正。许岗等人提出了时间敏感的机会网络拓扑图[8]预测方法，结果表明有较高精度。针对以上成果及问题，本文将在信任网络条件下，以时间序列的历史信息建立马尔科夫链，预测下一步的网络状态。

1 问题描述

在复杂的企业社会网络中，企业之间存在着由两个实体的直接交易形成的直接信任度和通过传递或推荐形成的间接信任度所共同构成的信任关系，经过组合、交叉等方式将形成由多个企业连接而成的有向信任链。在实际的交易过程中，由于环境的突变通常无法保证链路的稳定性，例如节点的移动、关闭及随机突发事件都可能使链路拓扑处于动态和间歇性局部连通的状态，因此节点之间可能不再保持原有的端到端完整路径，必须通过移动和其他节点相遇，形成新的信任链。为了实现企业快速度响应信任链的变化，减少不必要的损失，提高市场相率，必须建立信任链的演化机制，以图的模型考察其随时间演化的特性。

定义1信任链 在企业网络中，信任是用户关系维护的核心，先给出信任链的关键元素。（1）信任路径：在信任网络中，从节点s到节点t的一条真路为信任路径，记为ls,t。（2）信任链：信任链是连接节点的有向关系链，它由一条或者多条信任路径组成。可以分为原子信任链和组合信任链。原子信任链是不包含中间节点的两个实体之间的信任链，实体之间的信任关系是直接朋友关系(fd(i,j))。组合信任链是指由若干条原子信任链组成包含了多个连接点的信任链，源节点和目标节点之间的关系是间接朋友关系(fid(i,k))。（3）信任度：表示节点与节点之间的信任值。如，若l=(s,e1,e2,…,ek,t)为节点s与节点t之间的一条路径，其中为边ei的建立时间，信任传递的路径与各边的建立时间持续相关，因此可为每条边以其在观察的时间段内发生的变化和持续时间为权值构造连接图。

定义2演化网络 定义G为由n个时间片段组成的演化网络，gt表示在时刻t时演化网络的快照，V(gt)表示gt的节点集，E(gt)表示gt的边集。给定一种链路预测方法，就是要对任意节点对(vx,vy)在下一时刻产生的新的连边或者消除已有的连边的可能性给出一种度量方法，记这种可能性为sxy，时序链路预测方法可以用一个映射表示：

其中G'⊂G是已观测到的历史信任链路拓扑信息，是信任链演化预测的历史依据，S表示连边的可能性矩阵，反映了对未来链路的拓扑结构的猜测。

定义3时间窗 时间窗n是一个周期时间的集合,其中 m 是自然数集N，通常情况下选择具有一定规则的时间窗。P是一个周期表达式，Δt是一个时间段，表示作用于p时间点的上界，下界面。

基于图的分析模型其着眼点是，即使链路演化过程的拓扑难以预测，但是可以利用节点的动态变化过程建立一个“边过程”连接图，该图包含节点相遇过程的历史信息，包括起始时间和持续时间，基于这些信息进而判断下一步的演化结果。采用离散马尔科夫模型及生灭过程对信任链的拓扑演化及边的演化时间相关性进行建模。信任链的演化过程可以表示为如图1所示的连续时间步上的序列：在t0时刻，存在状态G0，是一条包含了n个节点的信任链l0，经过时间Δt，与若干个新的节点相遇，形成G1所示状态的信任链l1，再经过Δt，某个节点消失，新的节点加入，形成新的信任链l2，进而给出边独立演化的动态链路的演化性质。

2 信任链时序预测模型的建立

2.1 信任网络演化图

信任网络关系拓扑具有四元组G=((V,E),F,L)映射，各元素含义分别为：

（1）V是信任网络节点集为网络中节点vi和节点vj之间的社会关系，其强度为 vi和 vj的信任值 Trust，给出因素集U(U1,U2,…Un)和综合评判集V(V1,V2…Vn)，对因素集赋予权重w(w1,w2…wn)，其中w1+w2+…wn=1，因此信任值可以根据公式（1）计算：

（3）状态分配映射函数是总节点数量，vi为网络中的移动节点。

（2）E是信任网络边集，边集由节点之间建立信任关系后表示的连接边构成，将信任值映射为5个状态，描述节点间信任的强度。

（4）标记函数L(eij)将节点vi,vj之间的建立的连接命名为边eij，表示信任关系的建立。

图1 连续时间步上的信任链图序列

设为有限离散时间序列，Gi为时间间隔信任网络的一个状态图SG={}Gi，则为一个在时间区间上的离散时间演化图。

2.2 信任的动态计算

考虑电子商务企业中共享信息的特点，给出因素集U{基本信息，交易量，用户评价}，综合评判集V{完全信任，信任，一般信任，不信任，完全不信任},分别用5.4.3.2.1表示。马尔科夫转移矩阵中的元素代表着节点之间的连接边e从行所代表的信任等级转移到对应列所代表的等级的可能性pij。初始状态下pij=1/v，本文中v=5。第N次交易后马尔科夫转移矩阵的元素pN

ij可依据公式（2）得到：

对于每次交易前计算出的马尔科夫矩阵有因此：

2.3 马尔科夫状态转移矩阵的建立

以节点对之间的社会关系变来判断演化是否符合马尔科夫链，对于个n节点构成的信任链，对节点对之间的演化序列图进行统计，经过计算对边e建立马尔科夫状态转移概率矩阵如下：

且有：

2.4 算法步骤

本文研究信任链演化图模型的计算过程如下所示：

①给出时间窗P的划分范围。

②将全部的交易的用户反馈评价根据时间段分类，按公式（1）评估，以获取该时间域内节点间的信任值，并分配给状态函数F(eij)。

③根据前一次的交易评价建立当前状态矩阵，由公式（2）获得信任等级转移概率 pij。信任值Trust和转移概率pij同时大于设定阈值即建立连接边。

④连续时间步内的一系列状态组成一条马尔科夫链，一个时刻的状态对应一个演化子图，对节点间社会关系的历史信息进行统计，建立状态转移概率矩阵，结合公式（3）和公式（4）预测下一个时间片的关系状态。

3 验证与分析

3.1 预测正确率分析

为了进行对比，选取了不同时间片内的预测结果，仿真结果如表1、表2所示。

表1 边预测结果

3.2 算法性能评估

表1为不同时间片内的ROC曲线值，可以看出，仿真的时间片越长，ROC曲线越接近左上角，拟合效果越好。表2为不同时间片内AUC的值，随着运行时间的增加，预测精度也会提高。

图2 不同时间片内的ROC曲线

表2 不同时间片AUC的值

4 结语

本文在已有的信任值动态计算的研究成果上，提出了一种基于马尔科夫时间序列的链路预测方法，将信任关系映射为网络拓扑，考虑其历史信息对预测关系的影响，相比单纯的链路预测问题，将复杂链路赋予了实际意义；相比信任值的动态计算问题，将信任转化为了社会关系网络拓扑图，为企业网络的动态合作提供了决策依据。

[1]甘早斌，曾灿等.电子商务下的信任网络构造与优化[J].计算机学报，2012,35（1）：10.3724.

[2]莫家庆，胡忠望等.基于模糊理论的可信计算信任评估方法研究[J].计算机应用，2013,33（1）：142-145.

[3]甘早斌，马尧等.基于信任网络的C2C电子商务信任算法[J].软件学报，2015,26（8）：1946-1959.

[4]张丰，王箭等.基于马氏链的信任预测算法[J].计算机科学，2014,41（4）：155-158+183.

[5]郭景峰，代军丽等.针对通信社会网络的时间序列链接预测算法[J].计算机科学与探索，2010,4（6）：552-559.

[6]陈莎，朱福喜等.一种基于混合相似性指标的网络动态链路预测方法[J].小型微型计算机系统，2016，37.1798-1801.

[7]邓志宏，老松杨等.基于预测误差修正的时序链路预测方法[J].电子与信息学报,2014,36（2）：325-331.

[8]许岗，金海和等.时间敏感的机会网络社会关系拓扑演化研究[J].计算机科学与探索.2015,9（16）：1483-1493.