【word】 改进的随机游走模型节点排序方法

【word】 改进的随机游走模型节点排序方法 改进的随机游走模型节点排序方法 ComputerEngineeringandApplications$’l”算机与应用 改进的随机游走模型节点排序方法 何建军,李仁发 HEJianjun,LIRenfa 湖南大学计算机与通信学院,长沙410012 DepartmentofComputerandCommunication,HunanUniversity,Changsha410012,China HEJianjun.LIRenfa.Modifiednodesrankingmethodusingrandomwalkmode1.ComputerEngineeringandAppfica- tions,2011,47(12):87.89. Abstract:Nodesimportancerankingincomplexnetworkisoneofthemostimportantaspectsofstudyingthepropertiesof complexnetwork,whichhasbeenwidelyusedindatamining,websearching,analysisofsocialnetworkandSOon.Thepaper putsforwardanewmodifiedrandomwalkmodelnodesrankingalgorithmbasedonfieldtheoryfromthephysicssubjectto computetheMarkovtransfermatrixofrandomwalkmodelbythefieldforcebetweentheinteractingnodes,whichcangive moreexactandactualevaluationfornodesimportance.Preliminaryexperime ntalresultsshowthatthenodesimportancemea- surementismorereasonabletointerpretthenodesimportanceandcallcomput etheresultsofnodesimportancemoreprecisely~ Keywords:complexnetwork;nodesimpo~ance;fieldtheory;randomwalkm ode1 摘要:复杂网络节点重要性排序是研究复杂网络特性的重要方面之 一,被广泛应用于数据挖掘,Web搜索,社会网络分析等众 多研究领域.基于物理学场论模型,提出改进的随机游走模式的节点 重要性排序算法,即通过节点之间相互作用的场力来确定 随机游走模型中的Markov转移矩阵,这样可以对节点重要性排序作 出更加准确真实的评估.实验结果表明,所采用的节:最重要 性评估方法能更合理地解释节点重要性的意义,并且可以给出更加 真实精确的节点重要性的评估结果. 关键词:复杂网络;节点重要性;场论;随机游走模型 DOI:10.37788.issn.10028331.2011.12.026文章编 号:1002.8331(2011)12.0087.03文献标识码:A中图分类号:TP393.0 l引言 自然界中存在的大量复杂系统都可以通过形形色色的网 络加以描述.最近几年,由于计算机数据处理和运算能力的 飞速发展,科学家们发现大量的真实网络既不是规则网络,也 不是随机网络,而是具有与前两者皆不同的统计特征的网络, 其中最有影响的就是小世界网络(smallworldnetwork)和无 标度网络](scale.freenetwork),这样的一些网络被科学家们 称为复杂网络.有效地评价和度量网络节点的重要性,不仅 是网络化数据挖掘研究面临的首要问题,也是复杂网络,系统 科学,社会网分析和互联网搜索等领域中一个值得研究的方 向,具有广泛的应用价值. 2相关工作 评价复杂网络中节点重要性的度量方法很多,本质上都 是起源于图论”以及基于图的数据挖掘】.在现实网络中已经 存在很多种节点重要性的度量方法,主要包括节点的度,中心 度,介数以及基于随机游走模型的Pagerank算法嘲. 用节点的度来衡量节点的重要性,度越大,相应的节点也 就越重要,但它不能很准确表达网络中节点的重要程度,例 如,一个节点的度值虽然很高,但是连接它的其他节点却并不 重要,则这个节点并不一定重要;中心度,顾名思义,反映了节 点在网络中居于中心的程度,中心度越大,节点越重要,缺陷 是对网络的拓扑结构依赖性很大;Or数是节点重要性度量的 另一种方法,节点的介数定义为网络中所有最短路径经过此 节点的路径数目,其计算复杂度非常高,为O(N3),其中?为节 点数目,并且由于其方法的特殊性,对没有在最短路径范围内 节点的重要I生赋值为零,显然不符合实际情况. 基于随机游走模型的Pagerank算法则是Google的核心, 其基本出发点是试图为搜索弓l擎所覆盖的所有网页赋予一个 量化的PageRank值,每个网页的PageRank值是通过迭代计算 的方式来定义的,由所有链接指向它的网页的PageRank值决 定,PageRank值计算如下式: PR(i)=e?D(f)+(1一s)?(1)Ji’,J, 其中是所有指向i的网页集合,指网页.,出链的总数,冲 i . 浪者以概率s不再跟随链接浏览而从D(9分布中挑选—个网页 重新开始浏览,以0一的概率跟随当前网页的链接继续浏览. 由式(1)可以看出,Pagerank算法对每一个链出网页节点 都给予了同等的重要性,却没有考虑网页节点之间的相似度 基金项目:教育部科研重点项目 (KeyResearchProjectsoftheMinistryofEducationunderGrantNo.108168). 作者简介:何建军(1983一),男,硕士生,主要研究领域为复杂网络,链接分析;李仁发(1957一),男,教授,博士生导师.E~mail:shjtdxhjj826@126.corn 收稿日期:2009.08.19;修回日期:2009.12—14 ComputerEngineeringandApplications计算机工程与应用 而给予链接不同的权重.通常情况下,不相似的网页间不应 该存在链接,在考虑相似度的情况下,指向高质量的网页节点 应该赋予更大的转移概率,即,既要考虑网页节点问的相似 度,也要考虑网页节点自身的质量. 从物理学场论知识方面出发,提出了一个新颖的基于物 理学场论模型的节点排序算法,基于随机游走模型的情况,用 节点问的相互作用力来衡量节点之间的转移概率:节点b对 节点a的作用力越大,则表明从节点a跳转到节点b的趋势也 就越大,这样可以很好地从物理学的角度来解释节点之间边 的现实意义,本文考虑的是无向图中的随机游走模型. 3改进的基于随机游走模型的节点排序算法 经典物理学认为,场是物质的一种形态,同时与物质的另 一 种形态——实物存在着密切的联系,场论分为自然场和社 会场,其中,物理场有电场,磁场,引力场等,社会场有文化场, 经济场等.本文正是从自然场论角度出发,来重新看待节点 间边的连接.节点1到达节点2的概率被认为是节点2对节点 1的作用力,即节点2产生的信息场对节点1的作用,相应地, 节点2产生的信息场对节点1的作用越大,就表示节点越相 关,从而从节点1跳向节点2的概率也就越大,由此得出的转 移概率矩阵能克~pagerank中同等对待每一链出边链接的不 足,同时也考虑到节点自身的因素,比如质量等. 依据适用于无向图中修正的场论知识,提出的节点重要 性排序算法如下: 输入复杂网络结构图G1 输出节点的NodeRank值 (1)由复杂网络结构图G求出对应的相似度图G,,对应 的矩阵表示分别为和. (2)结合复杂网络结构图G,对相似度图G,进行化简,得 出最终的相似度图G,对应矩阵为. (3)对G运用修正的场论理论,求出作用力矩阵. (4)对作用力矩阵.进行归一化得到转移矩阵l订an. (5)根据转移矩阵求出复杂网络节点的NodeRank值. 3.1场论模型 一 种物质对其他物质产生的作用力其实也就是这个物质 在其自身周围产生特定的场,作用于处于该物质场域范围内 的其他物质. 地球上存在万有引力场,任意两质点间的引力可由公式 F:一G--M~rM:一G:一G,(2)2-q- r—r 表示,它与库仑定律公式形式类似: F=一去=一,O=一等,? 都是与距离平方成反比,与自身物质性质成正比的力,并且可 以计算出这种作用力的旋度为零. v×F=CV×(4) (c为常数),所以这两种力都是保守力,相应的力场都是保守 力场,因而这种场力必然存在势和势能,综上,场力的统一公 式为: Fa~,bK r Mr(5) M表示物质自身的性质,比如质量,电量,重要性等,是一 个常系数,r是两物质之间的”距离”. 3.1.1相似度图及距离, 对于式(5)中距离,,采用节点问的相似度来衡量r,本文 纯粹是从复杂网络拓扑结构图来考虑节点之间的相似度,其 中利用图的拓扑结构来计算图节点之间的相似度在数据挖 掘,推荐系统方面得到了广泛的关注.衡量节点之间相似 度常用的方法主要有Co.citatioff,Bibliographiccouplingt】, SimRanktin,PageSim等. 本文采用最简直而有效的Co—citation衡量方法,它是衡量 邻接节点间相似度的一种方法,其对应的相似度度量公式为: NodesSim(a,b)=Numbercomm.础(口, (6) 节点之间的距离用节点之间的相似度来衡量,两节点越 相似,表示之间的距离越短,反之亦然,所以有: 瓦丽1 3.1.2物质特性M (7) 衡量节点自身的特性无疑便是该节点的质量,质量越小, 自身的重要性也就越小,质量越大,自身的重要性也就越大. 正常情况下,节点度越大,表示其重要性也就越大,度越少,其 重要性则越小,即: =,(口)(8) 3.2作用力矩阵 若节点a与节点b之间存在边的连接,节点1到达节点2 的概率等同于节点2对节点1的作用力,即节点2产生的物质 场对节点1的作用,相应地,如果节点2与节点越相似,并且节 点2的质量越大,则节点2产生的物质场对节点1的作用越大, 就表示节点越相关,从而从节点1跳向节点2的概率也就越 大,对场力统一公式进行修改,得到节点b对节点n的场力的 公式: M.1 b=K丽 K*Ib*NodesSim(a,6)=K*Ib,NumberComm呲删(9) 由于每一项都有公共的常数,在不影响结果的情况下,为方 便起见,去除常数,得到: 丝 r =— 1/Nodes L Sim(a,b)= Ib*NodesSim(a,b)=1b,Numbercb.札.?(10) 最终得到作用力矩阵.,其中(a,6)=Fa.+. 3.3概率转移矩阵 因为Pagerank算法是基于Markov游走过程,所以概率转 移矩阵也就对应了Markov状态转移矩阵,Markov状态转移矩 阵的相关性质也就决定了不能直接用作用力矩阵.来直 接代替概率转移矩阵M,必须对它进行归一化处理,最终 得到: (f,:(11) -orc( 3.4Noderank计算 得出状态转移概率矩阵后,便可求出节点各自最终 的NodeRank值. 何建军,李仁发:改进的随机游走模型节点排序方法2011,47(12)89 x=?+(1一A)E 其中是所有节点的NodeRank值向量. (12) 4实验 4.1实验条件及方法 所采用的实验条件是真核细胞新陈代谢网络-,,见图1, 其中节点代表蛋白质,如果两个蛋白质参与了同,活动,它们 之间存在一条边,网络共有607个节点792条边,取其一个网 络模块,该模块有30个节点,34条边,在Noderank计算式(12) 中,取通常的经验值0.85.对这个模块分别采用度,中心度, 介数,Pagerank以及本文方法求出前十个最重要的节点,实验 结果见表1. 图1真核细胞新陈代谢网络中的一个模块 表1使用五种方法计算出的前lO个节点 4.2实验结果及分析 由表1可以看出,使用基于随机游走模型算法计算出的 前十个节点中后续节点的顺序与度,中心度,介数三种方法有 很大的不同,区别主要在于基于随机游走模型的算法不仅注 重度的大小,还考虑到连接节点的重要性;而在基于随机游走 模型的算法中,Pagerank算法和本文算法也有很大区别,比如, 使用Pagerank算法和本文算法计算出的排名第三的节点分别 是节点26和节点22,虽然节点22的度没有节点26的度大,但 是节点22跳向节点9的概率大,所以得到节点9重要性的概率 也就大,这两种方法的差别在于转移矩阵构造方法的不同, Pagerank算法对每一个连接都同等对待,这显然是不符合实际 的,而本文的方法从节点相似度和节点自身特性来确定节点 问的转移概率,所以能有效地克服Pagerank算法的不足. 5结语 为了解决Pagerank算法对连接节点同等对待的缺点,受 物理学场论知识的启发,给出了一种修正的基于随机游走模 型的节点排序算法,用节点的修正场强来衡量对其他节点的 吸引力,这样既考虑到了节点之间的相似性,也考虑到了节点 自身的质量性质,实验结果也验证了这种方法的优越陛,对于 修正场强公式的深入研究将是未来一个有趣的研究方向. 参考文献: [1】WattsDJ,StrogatzSH.Collectivedynamicsofsmall-worldnet- works[J].Nature,1998,393(6638):440-442. [2]BarabasiAL,AlbertR.Emergenceofscalinginrandomnet— works[J].Science,1999,286(5439):509—512. [3】WestDB.Introductiontographtheory[M].UpperSaddleRiver: PrenticeHal1.2001. 【4]WashioT.MotodaH.Stateoftheartofgraph-baseddatamining[J]. SIGKDD,2003,5(1):59—68. [5]FreemanLC.Centralityinsocialnetworks:Conceptualclarifica— tion[J].SocialNetworks,1979(1):215—239. [6】AltmannM.Reinterpretingnetworkmeasuresformodelsofdis— easetransmission[J].SocialNetworks,1993:1-17. 【7]PoulinR,BoilyMC,MasseBR.Dynamicalsystemstodefine centralityinsocialnetworks[J].SocialNetworks,2000:187—220. [8】PageL,BrinS,MotwaniR,cta1.ePageRankcitationranking: BringingordertotheWEB[Z].1998. [9]SmallH.Co—citationinthescientific1iterature:Anewmeasureof therelationshipbetweentwodocuments[J].JoumaloftheAmeri— callSocietyforInformationScience,1973,24:265—269. [10]KesslerM.Bibliographiccouplingbetweenscientificpapers[J]. AmericanDocumentation,1963,14:10—25. [11]JehG,WidomJ.SimRank:ameasureofs仃uctIlfal—contextsimi— larity[C]//Proceedingsofthe8thACMSIGKDD,NewYork.NY. USA:ACMPress,2002:538—543. 【12】LinZhenjiang,ngI,LyuMR.PageSim:anovellink-based similaritymeasurefortheWorldwideWeb[C]//Proceedingsof the2006IEEE,WIC,ACMIntemationalConferenceonWebIn— telligence,2006:1-7. [13]GuimeraR,SalesPM,LanA.Classesofcomplexnetworksde— finedbyrole?to-roleconnectivityprofiles[J].NaturePhysics,2007, 3:63—69. (上接86页) [4】ByunK,LeeS,KimH.Awatermarkingmethodusingquantization andstatisticalcharacteristicsofwavelettransform[C]//Proceed- ingsofthe6thInternationalConference,2005. [5】5金聪.数字图像处理[M】.北京:清华大学出版社,2007:272—278. [6】朱桂斌,曹长修.基于仿射变换的数字图像置乱加密算法[J].计算 机辅助设计与图形学,2003,15(6). 【7]肖亮,韦志辉.一种利用人眼视觉视觉掩盖的小波域数字水印[J]_ 通信,2002,3(23):100.106. [8】黄伟.基于人眼视觉系统的图像数字水印研究【D】.南京:南京信 息 工程大学,2008. [9】姚敏.数字图像处理【M].北京:机械工业出版社,2006:138—139. [1OJ冯茂林,冯波,沈春林.基于分块DCT变换和Arnold置乱的自适 应图像水印算法[J].计算机应用,2008,28(1):171.173. [11]ReddyAA,Chatte0iBN.Anffv~waveletbasedlogo-watermarking scheme[J].PatternRecognitionLetters,2005,26(5):1019.1027.