信任网络中基于节点重要性的层次化划分方法
2015-10-24龚卫华郭伟鹏裴小兵杨良怀
龚卫华,郭伟鹏,裴小兵,杨良怀
(1.浙江工业大学计算机学院,浙江杭州310023;2.华中科技大学软件学院,湖北武汉430074)
信任网络中基于节点重要性的层次化划分方法
龚卫华1,郭伟鹏1,裴小兵2,杨良怀1
(1.浙江工业大学计算机学院,浙江杭州310023;2.华中科技大学软件学院,湖北武汉430074)
针对信任网络目前面临的严峻的恶意攻击和安全防御问题,提出基于网络结构特性的信任网络节点层次化划分方法.从网络节点间的关联关系出发,分析和评价不同信任路径的信任值及其传播影响力.结合考虑这2种因素挖掘出关键信任序列,按照节点重要性依次将信任网络层次化划分成4类节点:核心节点、重要节点、关联节点和无关节点.该方法能够克服传统节点重要性评估指标的缺陷,准确体现网络中信任节点的重要性和关联性.实验结果表明:采用提出的划分方法能够有效地检测和发现恶意攻击对信任网络结构特性的影响.
信任网络;节点重要性;层次化划分;恶意攻击
随着在线电子商务、社交应用的普及,大量恶意用户行为所造成的严重信用危机和安全问题成为阻碍这些应用发展的瓶颈.信任网络在提供信任评价服务、降低用户交互风险方面的突出表现使其具有重要的研究意义和应用价值.然而,在潜在的巨大利益驱使下,针对信任网络的恶意攻击也复杂多样,如不诚实评价、共谋攻击等恶意行为导致节点间无法建立可靠的信任关系,使得各类在线应用出现“劣币驱良币”现象,极大地影响了信任网络的安全性和信任机制的有效发挥.
目前,国内外学者大都侧重于研究如何提出准确的信任值计算方法[1-3]和信任推理模型[4-6],忽略了从拓扑结构角度考虑信任网络结构关系的重要性,针对信任网络的安全保护研究还未引起人们足够的重视.不同信任路径上的关联节点对信任网络安全的影响差异显著,在大规模的信任网络中实现对所有节点同等程度的监测和保护通常代价巨大而收效甚微,因此,在考虑信任网络节点自身信任值的同时,提出有效区分不同关联节点重要性方法是应对信任网络安全问题的新途径.然而,现有研究缺乏针对信任网络重要节点的评估和发现方法,为此本文基于网络结构关系提出一种信任网络节点层次划分方法,从网络节点间的关联关系出发分析和评价不同信任路径的信任值及其传播影响力,并将信任网络节点划分成4类:核心节点、重要节点、关联节点和无关节点.
1 相关工作
近年来,信任网络一直面临着复杂多样的安全问题.国内外学者已提出了一些抵御这些恶意攻击的方法,如Eigentrust模型[4]采取预置可信节点的方法,帮助节点摆脱共谋团体的攻击.基于节点相似性[5-7]的方法则是过滤不诚实评价、识别共谋团体的一种有效手段,即通过比较请求服务节点与提供服务或推荐节点之间的信任评价行为相似度判断推荐节点是否可信.另外,还有一些研究依赖信任机制来识别和抑制恶意节点.王海艳等[8]提出了一种利用信任模型来构建邻居用户的可信联盟的方法实现可靠的服务推荐.窦文等[9]通过节点的入度、相应的权值以及推荐节点自身的重要性来判断目标节点的全局可信度.Wang等[10]提出的DoubleFace模型通过节点的出度大小和出度邻居节点的恶意程度确定节点的推荐可靠度,并使用类似于PageRank(PR)算法[16]的链接分析方法计算节点的信任度排名.Caverlee等[11]提出的Social Trust除了考虑反馈信任评价外,对存在高质量社会关系链接的节点和存在低质量关系链接的节点区别对待,有效提高了抵抗不诚实评价的能力.Koohborfardhaghighi等[12]提出一种结合实体交互频次和社会影响的信任推荐方法,利用介数中心性和特征向量中心性提高推荐评价的质量.Zhang等[13]利用入链构成的联合推荐链接结构扩展可信节点集,避免筛选到恶意节点.Jin等[14]提出一个基于反馈信任和服务信任的双度量信誉机制,通过比较反馈信任值和服务信任值的一致性来抑制恶意反馈.总体上看,以上方法仅从节点信任度评估的角度考虑来达到抑制恶意攻击的目的,而没有考虑和分析处于网络中不同地位的节点对信任网络安全的影响和防御恶意攻击的作用.
现有的度量节点重要性方法大多源于复杂网络研究,常用的度、介数、接近度等指标从网络拓扑结构分析节点重要性[15],没有考虑节点间的关联关系和关系强度,难以适用于复杂的信任网络环境.一些研究从网页链接关系角度分析节点重要性,其中最为经典的是PageRank算法[16]和HITS算法[17],这2种算法分别根据节点的PR值或权威(Authority)值与中心(Hub)值进行节点重要性的高低排序,缺点是都没有区分链接的重要性和考虑节点内容的相关性.此外,针对节点影响力的研究也是节点重要性判定的常用途径,K-Shell分解法[18]被认为在判断节点影响力方面优于度、介数等指标.Liu等[19]还提出一种改进的K-Shell方法计算节点影响力.赵佳等[20]综合考虑节点度和节点间的互动行为等因素,基于贝叶斯模型和半环代数计算节点影响力.张玥等[21]在PageRank算法的基础上结合用户行为特征及其关联网络特征,提出基于多属性的用户影响力排序算法.Romsaiyud[22]采用序列模式挖掘方法分析社交网络中单个节点的影响力,但没有深入讨论节点重要性和节点间的关联关系对整个网络的影响.
基于对以上研究现状的分析,本文从信任网络中节点间的关联关系出发,结合信任路径的信任值和影响力,提出一种信任网络节点层次化划分方法.先选取网络中频繁信任路径上的Top-k相交节点作为核心节点集,再根据信任关联程度由核心节点集向外依次获取重要节点集、关联节点集和无关节点集,据此采取分层的监测和保护措施有效提高信任网络防御恶意攻击的能力.
2 信任网络及相关定义
信任网络本质上属于社会网络,是由用户节点及其信任关系构成的关系网络结构.针对信任网络的建模分析有助于深入分析节点地位重要性及其信任关系结构,信任网络的形式化定义如下.
定义1 信任网络(trust network):由代表用户的节点以及节点之间的信任关系组成一个有向加权图,记为G=(V,E),其中V为信任网络的节点集,E为具有信任值的有向边集,其中Wxy表示节点x与节点y间的信任值:
从社会关系角度看,信任网络主要包含2类关系:直接信任和间接信任.其中边集E表示直接信任关系,而陌生节点间的间接信任关系的建立则依赖于中间节点的信任传递,这些相互关联和作用的节点通过若干直接信任边连接形成有向的路径序列,每一条路径序列就是一个间接信任关系.一些路径序列由于作为连通多个节点之间的公共路径,在信任网络中具有十分重要的地位和影响.为此,引入传播影响力概念来说明信任网络中路径序列的重要性.
定义2 传播影响力(propagation influence):信任网络中由节点i经l跳到节点j的一条有向路径序列对整个网络信任传递的影响程度,记作I p,形式化定义为式中:P是整个网络的信任路径序列集,Ind(u)表示节点u的入度集合,表示路径序列P在集合P中出现的频次,即该路径作为信任网络中公共路径的频繁程度.由于节点入度大小直观地体现了该节点对于信任路径连接的影响力,(Ind(u))表示取路径中节点的最小入度.
由定义2可知,一条路径序列的传播影响力与其在路径序列集中出现的频次以及该路径上节点最小入度这两者密切相关,因此,路径序列的传播影响力大小即表明其在信任网络中的重要性.
式中:W′ij表示信任序列上源点i到终点j的间接信任值,取决于l条直接信任边上的信任权重W的连乘积,即按式(3)计算获得;ω为信任度阈值,σ为传播影响力约束:
关键信任序列作为具有一定影响力和可信度的频繁公共路径,不仅为网络中的许多陌生节点对建立间接信任关系提供推荐信任评价信息,且序列的传播影响力约束也进一步表明其重要性.
3 信任节点层次化划分方法
为了有效区分信任网络中不同关联节点的重要性,将结合信任值和传播影响力等因素提出一种信任网络节点层次化划分方法.
3.1 关键信任序列获取方法
为了获得定义3的关键信任序列,本文在给定的整个网络信任路径序列集P中,按信任度阈值ω和传播影响力阈值σ这2个约束条件进行筛选,逐渐挖掘和发现所有符合条件的关键信任序列,其过程可根据定理1在由频繁(L-1)-信任序列合并产生候选L-信任序列时进行有效的搜索空间剪枝.
定理1 如果一条有向路径序列是关键信任序列,则它的任一子序列也是关键信任序列.
由于
⇒W′uv≥W′ij≥ω,即子序列的信任值满足阈值ω.(Ⅰ)
即:
式中:m、r、t分别表示所属集合的元素.
关键信任序列挖掘算法TrustSeq伪代码如下.
算法1 关键信任序列挖掘算法(TrustSeq)
输入:信任网络G中e条路径序列集合P={P1,…,Pe};
输出:关键信任序列集TS={S1∪S2∪…∪SL}
①初始化:L=1;S1=Φ;
②for each候选边Wij∈Pido
⑥end for
⑦删除集合P中未出现S1中1-关键信任序列的路径序列;∥削减非关键信任序列集
⑧repeat
⑨ L=L+1;
⑩ SL=SL-1∞SL-1;∥L-1关键信任序列经自然连接生成候选的L-序列集
⑯end for
⑰until SL=Φ;
⑱TS={S1∪S2∪…∪SL}.∥输出所有的L-关键信任序列集
算法1的计算复杂度分析:设路径集合P有e条路径,平均长度为l,序列集合S1规模为m,则该算法的计算代价主要分3个阶段:
1)步骤② ~ ⑥产生初始的频繁l-序列集阶段,该操作需要时间复杂度为O(m·e·l);
2)对于步骤⑦删除P中非关键信任序列操作,在步骤④中统计路径序列频次时已做标记,因此删除操作所需时间复杂度为O(e);
3.2 信任节点分层划分算法
获得关键信任序列集TS后,再根据节点重要性高低将信任网络进行层次化划,分成4类:核心节点集CO、重要节点集IM、关联节点集AN和无关节点集ON.
对于核心节点和重要节点这2类都包含于TS集中的节点,具体区别在于核心节点是否为多个关键信任序列之间的相交节点.本文取TS集中信任序列相交频次最大的前k个节点即Top-k作为核心,可表示成
重要节点集IM则是TS所包含的节点集合V′中除CO外剩下的节点集,可以表示为
IM=V′-CO.
AN是与关键信任序列集TS中节点存在密切联系的出度邻居节点,以集合TS中CO与IM的共同邻居节点的关联程度作为筛选关联节点的标准,假设节点i与核心节点和重要节点间的关联度计算将分别由它们的入度信任边权重决定,可表示为
式中:Ind(CO(i))表示指向节点i的核心节点集基数,Ind(IM(i))表示指向节点i的重要节点集基数,α为核心节点集的权重:
式中:Outlink(CO∪IM)为CO和IM并集的出度集合.
除上述3类节点集外,无关节点集ON为信任网络中的剩余节点,对信任网络的重要性影响最低处于网络最外层,由排除法可得,无关节点集
本文提出的基于节点重要性的层次化划分算法level Div如下.
式中:d(u)为节点u的度数,u为核心节点集CO的子集,而d(v)为节点v的度数,v为集合TS的子集.
当与关键信任序列集TS关联的节点i满足条件R(i)≥φ(关联度阈值)时,则称节点i属于关联节点集,即
算法2 网络节点层次化划分算法(levelDiv)
输入:信任网络G=(V,E)和关键信任序列集TS
输出:层次化的4类节点CO、IM、AN、ON
③ end for
④ 从节点集V′中取相交频次最大的Top-k个节点加入集合CO中;
⑤ 求出重要节点集IM=V′-CO;
⑥for each node i∈Outlink(CO∪IM)∧i∉V′
⑦ 按式(4)计算关联评分R(i);
⑧ if R(i)≥φthen AN={i}∪AN;
⑨end for
⑩求无关节点集ON=V-CO-IM-AN;
假设TS中包含的序列条数为m,节点数为V′ ,则步骤①~③的代价为O(m·V′).步骤④筛选核心节点需要对节点度进行排序,耗时约O(V′·logV′).步骤⑥~⑨筛选关联节点操作则需要判断信任网络G中除CO和IM外的其他节点是否为关联节点,则该过程最坏情况为O((V-k-V′)·m).总体上看,由于V≫V′≫k,该算法总的时间复杂度约为O(V·m+m·V′+V′·log V′).
4 仿真实验及分析
采用Advogato数据集构建信任网络进行实验与分析,该数据集包含7 431个节点和56 654条有向边,同时有向边上的信任评价权重共分成4个级别:游客级(Observer)、新手级(Apprentice)、行家级(Journeyer)和大师级(Master).为便于处理,将其映射到[0,1]区间的离散值,即Observer=0.4、Apprentice=0.6、Journeyer=0.8、Master=1.0.为了获得信任网络的关键信任序列集TS,在运行算法一时分别取ω=0.4和σ=0.006 8.算法二中从节点集V′里取Top-k当k=50的核心节点集CO,关联度阈值φ=0.55.在此实验条件下,验证信任网络层次化划分结构对恶意攻击的感知和防御能力的有效性.
如图1所示为信任网络进行层次化划分前、后的对比效果,图1(a)为原始网络中信任节点的分布情况,度数越高的节点呈现点越大、边密度越高.如图1(b)所示为将不同节点划分后聚集一起并呈现出层次分明的效果.其中,最内层节点表示核心节点集CO、次内层亮点表示重要节点集IM、次外层表示关联节点集AN、依附于AN集的最外层稀疏节点表示无关节点集ON.
为了验证本文算法检测由恶意攻击造成网络结构变化的有效性,实验中随机选取不同数量的节点进行恶意化处理(即将原先节点的信任评价值反转),对比节点恶意化前后算法所获得的网络不同层次结构的节点变化情况.图2(a)、(b)、(c)分别是当核心节点集Top-k取k=25、50、75时,网络受到恶意节点攻击后所重新划分的4类节点的变化情况,图中D表示节点变化数量,N表示恶意节点数.由图2可知,随着恶意节点增多,关联节点集AN在遭受恶意攻击后数量变化最大,重要节点集IM次之.由此可见,信任网络中的关键信任序列集对恶意攻击的反应敏感.
图1 信任网络层次化划分前、后对比Fig.1 Comparison of trust network before and after hierarchical partition
本文进一步给出关键信任序列上受恶意节点影响最大的核心节点集的变化率结果,图3中核心节点变化率μ在恶意节点规模N≤400时较小但不稳定,而当k=75时,变化率μ在恶意节点数600以上维持较高水平但保持相对稳定.因此,核心节点集受小规模恶意节点的影响较小,而当k增大时大规模恶意攻击对核心节点集的影响较大,但其响应敏感度较低.
以恶意节点的假负率(false negative rate,Fnr)判断本文划分算法levelDiv在恶意节点检测与判断方面的误报程度,Fnr定义如下:设恶意节点集为X,本为恶意节点而被划分为某一类节点的集合为Y,则
图2 不同规模恶意节点下4类节点划分的变化情况Fig.2 Change of 4 types of classified nodes when bad nodes increase
图3 不同数量恶意节点下的核心节点变化率Fig.3 Change rate of core nodes in different numbers of malicious nodes
如图4所示为不同规模的节点恶意化后被误划分到不同层次节点集的分布情况,随着恶意节点数量N的增大,核心节点集CO和重要节点集IM中的Fnr始终维持在非常低的水平,而关联节点集AN和无关节点集ON中的Fnr则一直处于较高水平,并且这些恶意节点被划分到信任网络中4类层次节点集中的比例关系有
由此可见,恶意节点很少能进入到关键信任序列集中,本文所提出的节点层次化划分方法具有很强的抵御恶意节点能力.
在不同规模恶意攻击数情况下,本文比较了算法所挖掘的关键节点波动率(key nodes fluctuation rate,Knfr)指标变化,Knfr定义如下:设恶意攻击前、后关键节点集分别表示为X′和Y′,则
选取3种典型的节点重要性判定算法K-Shell、PageRank和HITS与本文算法levelDiv,分别在恶意攻击前、后选取同等数量的关键节点进行Knfr指标比较,结果如图5所示.
图4 不同规模恶意节点时的假负率Fig.4 False negative rate results of different scales of malicious nodes
图5 4种算法在不同恶意节点数下的关键节点波动率比较Fig.5 Comparison of key nodes fluctuation rate results for four algorithms under different numbers of malicious nodes
随着恶意边规模N的增大,K-Shell、PageRank和HITS这3种算法的Knfr都非常低且基本一致,而算法level Div的Knfr一直较高,表明层次划分算法能有效检测不同规模的恶意攻击.这是由于算法K-Shell、PageRank、HITS对节点进行重要性排序时主要取决于节点间的度分布,而与边上的信任权重变化无关,因此,这3种算法对边恶意化反应并不敏感;算法levelDiv综合考虑了节点度、边的信任权重及路径频次等信息,因而能敏感地发现边恶意化对网络的不利影响,从而有效地抵御了恶意攻击.
5 结 语
由于目前缺乏信任网络重要节点的评估和发现方法研究,本文从信任网络节点间的关联关系出发,结合信任路径的信任值和影响力因素提出一种信任网络节点层次化划分方法,按节点重要性高低将信任网络节点划分成4种类别:核心节点、重要节点、关联节点和无关节点.该方法不仅克服了传统的节点度、介数等度量指标的缺陷,而且能更全面地体现网络中信任节点的重要程度和关联性.仿真实验表明:本文提出的方法能准确划分信任网络的层次结构,有效提高了信任网络抵御恶意攻击的能力.
下一步工作将从2个方面进行提升:1)在复杂多样恶意攻击条件下测试算法对信任网络划分的有效性;2)深入讨论算法中相关阈值参数的优化问题,减少人工设置经验值.
(References):
[1]AUDUN J,ROSS H,POPE S.Trust network analysis with subjective logic[C]∥Proceedings of the 29th Australasian Computer Science Conference(ACSC 2006).Hobart:Australian Computer Society,2006:85- 94.
[2]KIM Y A,SONG H S.Strategies for predicting local trust based on trust propagation in social networks[J].Knowledge Based Systems,2011,24(8):1360- 1371.
[3]VERBIEST N,CORNELIS C,VICTOR P,et al.Trust and distrust aggregation enhanced with path length incorporation[J].Fuzzy Sets and Systems,2012,202:61- 74.
[4]SEPANDAR D K,MARIO T S,HECTOR G.The Eigentrust algorithm for reputation management in P2P networks[C]∥Proceedings of the 12th International Conference on World Wide Web(WWW’03).New York:ACM,2003:640- 651.
[5]XIONG L,LIU L.Peer Trust:supporting reputationbased trust for peer-to-peer electronic communities[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(7):843- 857.
[6]田春岐,江建慧,胡治国,等.一种基于聚集超级节点的P2P网络信任模型[J].计算机学报,2010,33(2):345- 355.
TIAN Chun-qi,JIANG Jian-hui,HU Zhi-guo,et al.A novel super-peer based trust model for peer-to-peer networks[J].Chinese Journal of Computers,2010,33(2):345- 355.
[7]冯景瑜,张玉清,陈深龙,等.P2P声誉系统中Good Rep攻击及其防御机制[J].计算机研究与发展,2011,48(8):1473- 1480.
FENG Jing-yu,ZHANG Yu-qing,CHEN Shen-long,et al.Good Rep attack and defense in P2P reputation systems[J].Journal of Computer Research and Development,2011,48(8):1473- 1480.
[8]王海艳,杨文彬,王随昌,等.基于可信联盟的服务推荐方法[J].计算机学报,2014,37(2):301- 311.
WANG Hai-yan,YANG Wen-bin,WANG Sui-chang,et al.A service recommendation method based on trustworthy community[J].Chinese Journal of Computers,2014,37(2):301- 311.
[9]窦文,王怀民,贾焰,等.构造基于推荐的Peer-to-Peer环境下的Trust模型[J].软件学报,2004,15(4):571- 583.
DOU Wen,WANG Huai-min,JIA Yan,et al.A recommendation-based peer-to-peer trust model[J].Journal of Software,2004,15(4):571- 583.
[10]WANG Y,NAKAO A,VASILAKOS A V.Doubleface:robust reputation ranking based on link analysis in P2P networks[J].Cybernetics and Systems,2010,41(2):167- 189.
[11]CAVERLEE J,LIU L,WEBB S.The Social Trust framework for trusted social information management:architecture and algorithms[J].Information Sciences,2010,180(1):95- 112.
[12]KOOHBORFARDHAGHIGHI S,KIM J.Using structural information for distributed recommendation in a social network[J].Applied Intelligence,2013,38(2):255- 266.
[13]ZHANG X,LIANG W,ZHU S,et al.Automatic seed set expansion for trust propagation based antispam algorithms[J].Information Sciences,2013,232(20):167- 187.
[14]JIN Y,GU Z,BAN Z.Restraining false feedbacks in peer-to-peer reputation systems[C]∥Proceedings of International Conference on Semantic Computing(ICSC’07).Irvine:IEEE,2007,304- 312.
[15]CHEN D,LU L,SHANG M,et al.Identifying influential nodes in complex networks[J].Physica A:Statistical Mechanics and its Applications,2012,391(4):1777- 1787.
[16]BRIN S,PAGE L.The anatomy of a large-scale hypertextual web search engine[J].Computer Networks and ISDN Systems,1998,30(1):107- 117.
[17]KLEINBERG J M.Authoritative sources in a hyperlinked environment[J].Journal of the ACM(JACM),1999,46(5):604- 632.
[18]KITSAK M,GALLOS L K,HAVLIN S,et al.Identification of influential spreaders in complex networks[J].Nature Physics,2010,6(11):888- 893.
[19]LIU J G,REN Z M,GUO Q.Ranking the spreading influence in complex networks[J].Physica A:Statistical Mechanics and its Applications,2013,392(18):4154- 4159.
[20]赵佳,喻莉,李静茹.社交网络中基于贝叶斯和半环代数模型的节点影响力计算机理[J].物理学报,2013,62(13):1- 7.
ZHAO Jia,YU Li,LI Jing-ru.Node influence calculation mechanism based on bayesian and semiring algebraic model in social networks[J].Acta Physica Sinica,2013,62(13):1- 7.
[21]张玥,张宏莉,张伟哲,等.识别网络论坛中有影响力用户[J].计算机研究与发展,2013,50(10):2195- 2205.
ZHANG Yue,ZHANG Hong-li,ZHANG Wei-zhe,et al.Identifying the influential users in network forum[J].Journal of Computer Research and Development,2013,50(10):2195- 2205.
[22]ROMSAIYUD W,PREMCHAISWADI W.Applying mining fuzzy sequential patterns technique to predict the leadership in social networks[C]∥Proceedings of 9th International Conference on ICT and Knowledge Engineering.Bangkok:IEEE,2012:134- 137.
Hierarchical classification method of trust networks based on nodes importance
GONG Wei-hua1,GUO Wei-peng1,PEI Xiao-bing2,YANG Liang-huai1
(1.School of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China;2.School of Software Engineering,Huazhong University of Science and Technology,Wuhan 430074,China)
A hierarchical classification method for trust network nodes was proposed based on the network structural features,aiming at the serious problems of malicious attacks and defense mechanisms suffered by the trust networks presently.From the view of relevant relations existing in different nodes of trust network,this method was used to analyze and evaluate the trust values and the power of influences in different trust paths.The key trust sequences were mined with these two factors considered.According to the extents of importance ranking measured by correlations,all nodes in trust network were divided into four groups:core nodes,important nodes,associated nodes and others.This method could completely overcome the shortcomings of the traditional evaluation index of node importance,and exactly reflect the node importance levels and the correlations between nodes.The experimental results show that the proposed method can effectively detect and discover the structural fluctuations of trust network influenced by malicious attacks.
trust network;nodes importance;hierarchical classification;malicious attacks
10.3785/j.issn.1008-973X.2015.09.001
TP 391
A
1008- 973X(2015)09- 1609- 07
2014- 07- 27. 浙江大学学报(工学版)网址:www.journals.zju.edu.cn/eng
浙江省自然科学基金资助项目(LY13F020026,Y1080102,LY14F020017,LQ15F020007);国家自然科学基金资助项目(61070042).
龚卫华(1977-),男,副教授,博士,从事社交网络、数据挖掘研究.ORCID:0000-0001-6272-0976.E-mail:whgong@sohu.com