《信任网络中的信任实体重要性发现方法①》由会员分享，可在线阅读，更多相关《信任网络中的信任实体重要性发现方法①（5页珍藏版）》请在金锄头文库上搜索。
1、2014 年 第 23 卷 第 5 期 http:/www.c-s- 计 算 机 系 统 应 用 Research and Development 研究开发 213 信任网络中的信任实体重要性发现方法 郭伟鹏, 龚卫华 (浙江工业大学 计算机科学与技术学院, 杭州 310023) 摘 要: 信任网络是开放网络环境下抵御恶意欺诈、降低用户交互风险的有效手段, 现有关于信任网络的研究集 中于信任评价的传播和计算策略, 对信任网络中实体重要性没有足够的重视. 本文提出一种信任序列模式挖掘 算法 T-Seq, 将信任传播过程作为信任序列, 通过序列挖掘方法有效找出信任网络中的重要信任节点. 实验表明
2、了 T-Seq 算法在信任序列模式挖掘和重要节点发现上的有效性. 关键词: 信任网络; 节点重要性; 信任传播; 信任路径; 序列挖掘 Important Nodes Discovery in Trust Network GUO Wei-Peng, GONG Wei-Hua (School of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China) Abstract: Trust network is an effective means of resisting
3、malicious fraud and reducing the risk of interactions between users. Most of existing researches focus on trust propagation and aggregation strategies, while pay little attention to the importance of agents. This paper presents a sequential pattern mining algorithm which called T-Seq, in which trust
4、 propagation process is regarded as trust sequences. It is effective in important nodes discovery through sequences mining. Experiments showed the effectiveness of T-Seq in sequential pattern mining and important nodes discovery. Key words: trust network; node importance; trust propagation; trust pa
5、ths; sequential mining1 引言 近年来, 在线电子商务、社交应用等深刻改变了 人们的社会活动和交流方式. 然而, 由于利益的驱使, 大量恶意用户的欺诈行为充斥于这些开放的网络环境 中, 所带来的信任危机和安全问题成为阻碍这些应用 系统发展的瓶颈. 信任网络结构 1 在抵御恶意欺诈、 降 低用户交互风险上的突出表现使其备受重视, 通过信 任评价信息的传播和聚合计算, 用户能综合判定目标 用户的可信程度, 从而决定是否与之进行交互. 信任网络本质上是一个社会网络, 由直接信任关 系和间接信任关系构成, 实体的交互决策不仅依靠个 体自身的直接交互历史, 还受到其他实体的影响 2
6、 . 现有研究大都集中于间接信任的路径查找分析和推理 聚合的计算方式 3-8 , 对信任网络中实体的重要性及信 任关联关系没有足够的重视, 而这对理解信任传播过 程、掌握信任网络结构和帮助抵抗恶意攻击有着重要 意义. 目前已有一些判断节点重要性的度量指标如度中 心性、特征向量中心性、介数等 9 , 但这些指标侧重于 从网络拓扑结构角度分析节点重要性, 没有考虑节点 之间的关联关系, 不能有效适用于信任网络中实体重 要性分析及关键信任路径的发现. 总体上看, 现有信 任网络研究存在的不足主要在于在信任传播和信任聚 合时对所有信任实体同等对待, 缺乏关于信任实体的 重要性分析, 也忽视了信任路径上
7、实体间的关联关系. 针对上述问题, 本文使用序列模式挖掘方法分析 信任网络中信任序列结构及节点重要性. 信任网络中 节点间的信任传递路径构成了信任序列, 其中一些信 任序列成为众多节点对的信任传递频繁经过的公共路 径, 因而在信任网络中占有重要地位, 相应地构成这 基金项目:国家自然科学基金(61070042);浙江省自然科学基金(LY13F020026,Y1080102) 收稿时间:2013-09-15;收到修改稿时间:2013-10-14计 算 机 系 统 应 用 http:/www.c-s- 2014 年 第 23 卷 第 5 期 214 研究开发 Research and Develo
8、pment 些信任序列的实体即为重要实体. 实验表明本文提出 的方法能有效发掘信任网络中的频繁信任序列, 准确 体现了信任实体的重要性. 2 相关工作 目前关于信任网络的研究大多关注的是间接(推 荐)信任关系的推理及其聚合计算. 如 Sunny 3 基于所 有路径估计目标节点的可信程度; 而 Verbiest等 5 则认 为路径越长其信任度越低, 因而提出了一种限制路径 长度的动态路径搜索算法, 即在聚合计算时仅考虑长 度不超过一定阈值的路径; Li 等 6 分析了影响信任评 价的多个因子, 使用加权移动平均(WMA)和有序加权 平均(OWA)算法动态分配多因子的权重. 此外, 间接 信任的计
9、算方法还有主观逻辑 7 、D-S 证据理论 8 等, 这些方法往往仅考虑信任强度和路径长度对信任传递 的影响, 忽视了地位不同的节点对信任传递的影响存 在较大差别这一事实, 且间接信任的推理和计算过程 还存在一些信息损失, 因而导致其信任评价不够可靠. 社会网络中度量节点重要性的常用指标有度、介 数、接近中心性、特征向量中心性等 9 , 这些指标从网 络拓扑结构出发, 以不同角度刻画节点重要性. 例如, 基于度的节点重要性度量方法强调节点的邻居节点的 数量, 但无法反映节点所处复杂环境对其重要性的影 响; 介数是基于经过节点的最短路径数体现其对网络 中信息流的控制能力, 但实际上多数网络中信息
10、的流 动并不仅仅依赖最短路径. 上述指标各有其优缺点, 但在复杂的信任网络中很难依靠单个指标判断节点重 要性. 另外一些研究则基于链接分析提出度量节点重要 性的方法, 其中最为经典的是 PageRank 算法 10 和 HITS算法 11 . PageRank算法认为一个节点的重要性取 决于指向它的其他节点的重要性, 每个节点的 PR 值 可由指向它的节点的 PR 值按出度大小加权计算得到. 而 HITS算法为每个网页节点分配两个指标: Hub值和 Authority 值. 节点的 Hub 值为它所指向的节点的 Authority 值之和, Authority 值则为指向它的节点的 Hub 值
11、之和, 二者是相互增强的关系. 这两种算法分 别依据节点的 PR 值或 Authority值进行节点重要性排 序, 在计算过程中都没有区分链接的重要性. 综上所述, 信任网络中实体间的信任关系由于受 多种因素影响而更加复杂, 上述节点重要性评价指标 并不适用于信任网络中的重要节点发现, 而从目前国 内外研究现状的调研情况看, 尚无信任网络重要实体 发现的相关研究. 因此, 本文提出一种信任序列模式 挖掘算法, 该算法从节点间的信任关系出发, 分析和 挖掘网络中所有节点对之间的信任路径中的频繁信任 序列, 并结合节点关联特征, 有效找出信任网络中的 重要节点. 3 信任实体重要性分析 信任网络中
12、陌生实体间信任关系的建立依赖于中 间实体的信任传递,这些相互关联和作用的实体形成 有向的信任路径, 频繁的公共信任路径及相关节点在 信任传递过程中起着枢纽作用. 挖掘和发现重要信任 实体对深入分析信任网络结构具有重要意义, 为此本 文提出一种信任序列模式挖掘算法 T-Seq, 以找出频 繁信任路径序列和相应的重要信任实体. 3.1 信任序列定义及表示 本文首先给出信任网络的形式化定义如下: 定义 1. 信任网络(Trust Network): 由代表实体的 节点以及它们之间的信任关系组成一个有向加权图, 表示为 TN=(V ,E), 其中 V为信任节点集, E为具有信任 值的有向边集. 从社会
13、关系角度看, 信任网络主要包含两类关系: 直接信任和间接信任, 其中边集 E 表示了直接信任关 系, 而陌生节点间的间接信任关系建立依赖于中间节 点的信任传递, 这些相互关联和作用的中间节点通过 若干个直接信任边连接形成有向的路径序列, 每一条 路径序列就是一个信任传播过程, 称之为信任序列. 定义 2. 信任序列(Trust Sequence): 信任网络中从 源节点 i经 k跳到达目标节点 j的 k条直接信任边相连 接所构成的一条有向路径序列, 可表示为: (1) 其中 ij W 是信任序列 k ij S 从源点 i到终点 j的间接信任 值, 取决于 k 条直接信任边上的信任权重 W, 采
14、用式 (2)计算, w 为信任阈值, 满足 0 1 w ik ij ij ik w P W W = 2014 年 第 23 卷 第 5 期 http:/www.c-s- 计 算 机 系 统 应 用 Research and Development 研究开发 215 定义 3. 频繁信任序列: 给定包含 n个信任序列的 集合 1 ,., n P P P = 和支持度阈值s , 如果存在一个 信任序列 k S 在 P 中出现次数满足支持度s 条件, 即 , , k k k i i S P S P S s $ $ , 则序列 S k 是频繁 k-信任序 列, 又称为 k-序列模式. 传统的频繁项定义
15、只需满足集合特性, 而本文所 定义的频繁信任序列是项集的有序列表, 序列中的节 点都保持有序性和关联性. 频繁 k-信任序列其具体意 义在于: 作为信任传播过程中的骨干, 该序列上所有 节点共同为网络中较多节点提供推荐信任评价. 相应 地构成频繁信任序列的节点也是网络中的重要节点. 3.2 频繁信任序列挖掘算法 本文通过信任序列模式挖掘方法获取信任网络中 的重要实体, 该方法主要分两步完成: (1)遍历信任网 络获取所有信任路径集合; (2)通过序列挖掘算法在信 任路径集合中筛选频繁信任序列集. 由于节点间传递 信任评价信息构成了信任路径序列, 为分析节点对整 个网络的信任传播影响程度, 故需要首先获取网络中 的所有信任路径. 本文基于深度优先搜索(DFS)获取 网络中的所有信任路径集合, 其过程描述如下. 算法 1. 信任路径集获取算法 GetPaths 输入: 信任网络 TN=(V ,E), 信任阈值w 输出: 信任网络 TN 中 n条信任序列集合 P=P 1 ,P n for each节点 iV do i 入栈 seq, visitedi=true; repeat 取栈 seq 的栈顶节点 u, 当前路径 P k 信任值 W
