基于蚁群算法的社会网络信任关系模型

基于蚁群算法的社会网络信任关系模型摘要由于我们处在一个开放的社会网络环境中,建立可靠的社会网络信任关系模型以及寻找最优的信任路径成为了业界人士研究的重中之重。基于蚁群算法的寻找信任路径的算法,不同于传统推荐信任模型中单纯采用平均得到推荐信任值的方法,而是通过多次循环选出多条较优的独立信任路径,在一定程度上可有效防止联合欺诈行为,并通过实验证明了它的有效性,在性能和可靠性上也优于其它算法,适应现实的复杂网络环境动态变化。1概述1.1社会网络简介（1）社会网络的定义社会网络（SocialNetwork）按其基本定义，是由多个节点（通常是个人或组织群体）构成的社会结构，它们由一个或多个特定类型的相互关系来建立纽带，连接在一起，比如（共同的）价值观、理念、思想、金钱交易、友谊、绑架、厌恶、冲突、贸易等。（2）社会网络的三个维度网络饱和度---一个网络结构中，“实际存在的朋友关系”与“可能存在的朋友关系”之间的比例。网络控制度---一个网络结构中，“实际存在的朋友间关系”与“可能存在的朋友间关系”之间的比例，比例越高，个人对所处网络的控制度越低。网络扩张度---“朋友们的社会网络结构中不重复的朋友总数”与“直接朋友总数”的比例，比例越高，网络扩张度越大，理论上可接近的朋友越多。1.2信任关系简介信任：一般说来，如果一个实体假定另一个实体会准确地像它期望的那样表现那么久说它信任那个实体。信息关系：当俩个认证机构中的一方给对方的公钥或双方给对方公钥颁发证书时建立。信任是关系的资本化，它的学理作用是降低缔约费用。人际信任是个体在人际互动过程中建立起来的对交往对象的言词、承诺以及口头或书面的陈述的可靠程度的一种概括化的期望。信任可减少处于人际互动过程中个体间由于时空分离所造成的距离感,它是良好人际互动的前提。2理论基础2.1社会网络理论基础（1）六度分隔理论(SixDegreesofSeparation)美国著名社会心理学家StanleyMilgram于20世纪60年代最先提出。“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。”“六度分隔”说明了社会中普遍存在的“弱纽带”，但是却发挥着非常强大的作用。（2）150法则（RuleOf150）从欧洲发源的“赫特兄弟会”是一个自给自足的农民自发组织，这些组织在维持民风上发挥了重要作用。有趣的是，他们有一个不成文的严格规定：每当聚居人数超过150人的规模，他们就把它变成两个，再各自发展。“把人群控制在150人以下似乎是管理人群的一个最佳和最有效的方式。”150成为我们普遍公认的“我们可以与之保持社交关系的人数的最大值。”2.2蚁群算法蚁群算法(AntColonyAlgorithm,ACA)是一种新型的模拟进化算法,它是在对自然界中真实蚁群集体行为的研究基础上,由意大利学者Dorigo等人首先提出的。像蚂蚁这类群居昆虫虽然没有视觉,却能找到由蚁巢到食物源的最短路径。仿生学家经过大量细致观察研究发现,蚂蚁个体之间通过一种称之为外激素(pheromone)的物质进行信息传递,蚂蚁在运动过程中能够在它所经过的路径上留下该物质,而且蚂蚁在运动过程中能够感知这种物质的存在及其强度,并以此指导自己的运动方向,蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法模拟真实蚁群的协作过程,算法由许多蚂蚁共同完成,每只蚂蚁在候选解的空间中独立地搜索解,并在所寻得的解上留下一定的信息量,解的性能越好蚂蚁留在其上的信息量越大,信息量越大的解被选择的可能性也越大。在算法的最初阶段所有解上的信息量是相同的,随着算法的推进较优解上的信息量增加使得算法渐渐收敛。蚁群算法已成功解决了一系列问题,如TSP问题、分配问题、Job-shop问题,所取得的结果无论是在解的质量上,还是在收敛速度上都要优于或至少等效于演化算法(EA)、模拟退火算法(SA)以及其它一些启发式方法。这些初步研究已显示出蚁群算法在求解复杂组合优化问题方面具有并行化、正反馈、鲁棒性强等优越性。3基于蚁群算法的社会网络信任关系模型3.1社会网络信任关系模型模型1：仅存在与ego的朋友关系，无朋友间关系模型模型2：较简单模型，朋友间存在直接（一步）关系模型3：中等复杂模型，朋友间全部存在相互直接关系模型模型4：较复杂模型，朋友间全部存在相互直接关系，且朋友拥有与ego无关系的其他朋友关系3.2蚁群算法基本思想在复杂的社会信任网络拓扑图中,找到所有的信任路径会花费很多时间,同时许多信任路径的值都很低,对最终的信任值的贡献不大,而且当有联合欺诈行为时,对综合评估信任值还会起反作用。但只利用一条信任路径综合计算得到一个节点的综合信任值又会不准确,因此需要得到多条较优的信任路径,并且既能反映真实情况,又能防止联合欺诈行为。以长度length限制搜索范围,利用蚁群算法找到多条最优的信任路径。把信任关系网络拓扑图抽象为图G=((V,E),s,t,b),V为节点集,每个节点代表一个实体,E为矢量集,代表信任关系。每个矢量值的范围是[0,1],ijrt代表节点i对节点j的推荐信任值,例如ijrt=0.85代表节点i对节点j的推荐信任值为0.85。s∈V,t∈V,s代表源节点,t代表目标节点,b代表信任路径的最大长度,信任路径s→c1→c2→…→11c→t的长度为l,l≤b。一条信任路径上的推荐信任值为:（1）这里kE为路径kP上的矢量集。多条信任路径1P,2P,…,kP综合计算后得到的最终推荐信任值为（2）设m是蚂蚁的数量,ijd为节点间的距离。ij(t)表示t时刻路径i→j上残留的信息素量,物理意义为节点i对节点j的推荐信任值,初始时刻ij(0)=Vij。m只蚂蚁全部从节点s出发,运动过程中,按照公式(3)计算的概率转移。（3）其中kijp表示在t时刻蚂蚁k由节点i转移到节点j的概率Jk为蚂蚁k目前尚未访问过的节点集合;参数α、β分别用来控制信息素浓度和距离的相对重要程度。当蚂蚁到达目标节点t时,蚂蚁停止运动,当蚂蚁走的长度大于b时,也要停止运动。当所有的蚂蚁都停止寻径时一次循环结束。随着时间的推移各个向量上原有的信息素会逐渐降低,有蚂蚁经过的路径信息素会相应增加,用参数1-ρ表示信息素的降低程度。各个向量的信息素按下列公式调整:（4），（5）这里表示ij第k只蚂蚁本次循环中,在向量ij上信息素的增量。经过多次循环选出信息素浓度最高的路径,也就是最优的信任路径。然后图G中去掉这条路径中的中间节点,得到G′,再利用蚁群算法找到次优的信任路径,像这样循环k次,得到k条独立的较优信任路径,按公式(2)得到最终的推荐信任值。算法描述：4总结基于蚁群算法的寻找信任路径的算法,不同于传统推荐信任模型中单纯采用平均得到推荐信任值的方法,而是通过多次循环选出多条较优的独立信任路径,在一定程度上可有效防止联合欺诈行为,并通过实验证明了它的有效性,在性能和可靠性上也优于其它算法,适应现实的复杂网络环境动态变化。参考文献[1]杨剑峰.蚁群算法及其应用研究[D].浙江大学,2007.[2]杨丽锦.浅析蚁群算法的原理及应用方向[J].电脑知识与技术,2009,06:1455-1456.[3]何娟,涂中英,牛玉刚.一种遗传蚁群算法的机器人路径规划方法[J].计算机仿真,2010,03:170-174.[4]刘波.蚁群算法改进及应用研究[D].燕山大学,2010.[5]张美玉,黄翰,郝志峰,杨晓伟.基于蚁群算法的机器人路径规划[J].计算机工程与应用,2005,25:34-37.[6]王芳.蚁群算法的原理及其应用[J].潍坊教育学院学报,2005,02:70-72.[7]荚恒松.蚁群算法及其应用研究[D].江南大学,2008.[8]曾海群.蚁群聚类算法研究[D].中南大学,2008.