第１７卷第６期 ２０１６年１２月 信息工程大学学报 Ｊｏｕｒｎａｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ Ｖｏ１．１７ ＮＯ．６ Ｄｅｃ．２０１６ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７１—０６７３．２０１６．０６．Ｏ１８ 基于叠加随机游走的复杂网络节点重要度评估方法 宋 琛 ，尹 波 ，张贤坤 （１．天津科技大学，天津３００２２２；２．６６４７０，河北秦皇岛０６６１０２） 摘要：针对现有节点重要度评估方法排序结果不精确的缺点，提出一种基于叠加随机游走的评 估方法。首先引入随机游走算法并进行叠加改进，计算得到节点间的相似度矩阵；其次提出相 似和的概念，用以表征节点的重要度，相似和越高，表明其与越多的节点有更高的相似度，相对 而言重要度越高；最后对相似和进行排序，得到网络中节点的重要度排序。实验证明，该方法 能以较高的精度评估网络节点的重要度，获取网络中的关键节点。 关键词：节点重要度；评估；随机游走；相似和 中图分类号：ＴＰ３９３．０２ 文献标识码：Ａ 文章编号：１６７１—０６７３（２０１６）０６．０７３０—０５ Ｎｏｄｅ Ｅｖａｌｕａｔｉｏｎ Ｍｅｔｈｏｄ Ｂａｓｅｄ ｏｎ Ｓｕｐｅｒｐｏｓｅｄ Ｒａｎｄｏｍ Ｗａｌｋ Ｓ０ＮＧ Ｃｈｅｎ．ＹＩＮ Ｂｏ．ＺＨＡＮＧ Ｘｉａｎｋｕｎ （１．Ｔｉａｎｊｉｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｔｉａｎｊｉｎ ３００２２２，Ｃｈｉｎａ；２．Ｕｎｉｔ ６６４７０，Ｑｉｎｈｕａｎｇｄａｏ ０６６１０２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｔｈａｔ ｔｈｅ ｅｘｉｓｔｉｎｇ ｎｏｄｅ ｉｍｐｏｒｔａｎｃｅ ｅｖａｌｕａｔｉｏｎ ｍｅｔｈｏｄｓ ｃｏｕｌｄ ｎｏｔ ｏｆｆｅｒ ａｃｃｕｒａｔｅ ｓｏｒｔｉｎｇ，ａ ｎｏｄｅ ｅｖａｌｕａｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｓｕｐｅｒｐｏｓｅｄ ｒａｎｄｏｍ ｗａｌｋ ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｔｅｘｔ．Ｆｉｒｓｔ，ｔｈｅ ｒａｎｄｏｍ ｗａｌｋ ａｌｇｏｒｉｔｈｍ ｉｓ ｉｎｔｒｏｄｕｃｅｄ ａｎｄ ｔｈｅｎ ｉｍｐｒｏｖｅｄ ｔｏ ｓｕｐｅｒｐｏｓｅｄ ｒａｎｄｏｍ ｗａｌｋ． Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｕｓｅｄ ｔｏ ｃａｌｃｕｌａｔｅ ｔｈｅ ｓｉｍｉｌａｒｉｔｙ ｍａｔｒｉｘ ｂｅｔｗｅｅｎ ｎｏｄｅｓ．Ｓｅｃｏｎｄ，ｔｈｅ ｃｏｎｃｅｐｔ ｏｆ ｔｈｅ ｓｕｍ ｏｆ ｓｉｍｉｌａｒｉｔｙ ｉｓ ｐｕｔ ｆｏｒｗａｒｄ ａｎｄ ｕｓｅｄ ｔｏ ｃｈａｒａｃｔｅｒｉｚｅ ｔｈｅ ｎｏｄｅ ｉｍｐｏｒｔａｎｃｅ．Ｔｈｅ ｈｉｇｈ ｓｕｍ ｏｆ ｓｉｍｉ— ｌａｒｉｔｙ ｓｕｇｇｅｓｔｓ ｔｈａｔ ｔｈｅ ｎｏｄｅ ｈａｓ ａ ｈｉｇｈｅｒ ｓｉｍｉｌａｒｉｔｙ ｗｉｔｈ ｍｏｒｅ ｎｏｄｅｓ，ａｎｄ ｔｈｉｓ ｎｏｄｅ ｉｓ ｍｏｒｅ ｉｍｐｏｒｔａｎｔ ｉｎ ｔｈｉｓ ｒｅｇａｒｄ．Ｆｉｎａｌｌｙ，ｔｈｅ ｓｏｒｔｉｎｇ ｏｆ ｎｏｄｅ ｉｍｐｏｒｔａｎｃｅ ｉｎ ｔｈｅ ｎｅｔｗｏｒｋ ｉｓ ｏｂｔａｉｎｅｄ ｂｙ ｓｏｒｔｉｎｇ ｔｈｅ ｓｕｍ ｏｆ ｓｉｍｉｌａｒｉｔｙ．Ｅｘｐｅｒｉｍｅｎｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｉｓ ｍｅｔｈｏｄ ｃａｒｌ ｅｖａｌｕａｔｅ ｎｏｄｅ ｉｍｐｏｒｔａｎｃｅ ｗｉｔｈ ｈｉｇｈ ａｃｃｕｒａｃｙ ａｎｄ ｔｈｕｓ ｏｂｔａｉｎ ｔｈｅ ｋｅｙ ｎｏｄｅｓ ｉｎ ｔｈｅ ｎｅｔｗｏｒｋ ｅａｓｉｌｙ． Ｋｅｙ ｗｏｒｄｓ：ｎｏｄｅ ｉｍｐｏｒｔａｎｃｅ；ｅｖａｌｕａｔｉｏｎ；ｒａｎｄｏｍ ｗａｌｋ；ｓｕｍ ｏｆ ｓｉｍｉｌａｒｉｔｙ 虚拟与现实世界中，复杂网络跨越计算机学、 社会学、生物学、军事学等多个领域广泛存在，如微 ｐｏ￣ａｎｃｅ ｅｖａｌｕａｔｉｏｎ）作为一个重要领域也获得了广 泛关注 。节点重要度排序的研究对于社会生 博社交网络、科学家协作网络、神经元网络、通信网 络等。基于图论，网络可以看做节点与节点间联系 的集合。拓扑结构的非均一性决定了网络中各节 点重要度的相异性，一些重要节点往往对整个网络 活的各方面有非常重要的应用价值：在协 作网络中，可以找到的头目，迅速控制并 瓦解整个组织；在战争遇敌我对峙时，寻找军事重 镇和交通要道进行重点攻击，快速获取战争主动 权；在控制人员思想的过程中，应当最先掌握活跃 分子，便于稳定全局；在谣言传播过程中，寻找散布 的拓扑稳定性和功能实现起着更重要的作用。随 着小世界特性¨ 与无标度特性 的发现，对复杂 网络的研究迅速兴起。节点重要度评估（ｎｏｄｅ ｉｍ． 消息的源头，迅速遏制谣言传播；在路由、铁路、科 收稿日期：２０１５－０６—１２；修回日期：２０１５－０９－０７ 基金项目：国家自然科学基金资助项目（Ｕ１４０４６０４） 作者简介：宋琛（１９８８一），女，助理讲师，硕士，主要研究方向为社会网络分析。 第６期 宋 琛等：基于叠加随机游走的复杂网络节点重要度评估方法 ７３１ 学合作等网络中，找到核心节点、核心人物进行重 点保护，保证整个网络的稳定性。 １ 研究现状 目前节点重要度评估主要有以下几种方法：① 基于节点中心性。通常使用的衡量方法有基于度 数 、介数 和流介数 等。节点的度是指邻接 节点的数量，介数是网络中所有节点对之间的最短 路径通过该节点的次数。度指标简单直观，是用来 描述节点重要度最直接的指标，但它仅仅考虑了局 部信息，更多地体现了某一节点的“号召力”，排序 往往出现偏差。介数指标主要体现节点的信息承 受和传递能力，但是时间复杂度较高，对于复杂网 络并不适用；②基于节点删除 和节点收缩 的 方法。在某些网络中，一些重要节点地位非常重 要，一旦去除，网络就无法连通，文献［８］将网络以 生成树的形式表示，根据删除特定节点后的生成树 数量评估节点的重要程度，若某个节点删除后剩余 生成树的数量达到最小值，则该节点为最重要的节 点。但该方法只能用在联通网络中，若一个节点删 除后网络不再连通，该方法将无法继续判断。节点 收缩法就是将节点与它的某个邻居节点收缩成一 个新节点，通过计算凝聚函数求解节点重要度，但 是每次收缩后都需要计算凝聚度，时间复杂度较 高。③特征向量方法 Ｊ０ Ｊ。特征向量不仅考虑了度 信息还包括邻接节点的重要度，利用节点的邻接节 点来描述节点的重要性，如果某个节点的重要度很 高，该节点只能与大量一般节点或者少数重要节点 邻接。但该方法收敛过程很慢，有时还会出现周期 性死循环。特征向量方法还包括累计提名 、 ＰａｇｅＲａｎｋ［ｔ２１ＬｅａｄｅｒＲａｎｋ［１３＿、、ＳＡＬＳＡ㈨等方法。 另外节点重要度排序上，文献［１５］还提出了一种 基于节点位置的ｋ－ｓｈｅｌ１分解法，逐层去掉度数为１ 的节点及其相关联系。ｋ－ｓｈｅｌ１分解法复杂度低，在 大型网络中得到了较多应用，但它的应用范围有局 限，划分结果过于粗糙。 为提高计算结果的准确性，本文提出了一种基 于叠加随机游走的节点重要度评估（ｎｏｄｅ ｉｍｐｏｒ． ｔａｎｃｅ ｅｖａｌｕａｔｉｏｎ ｂａｓｅｄ Ｏｉｌ ｔｈｅ ｓｉｍｉｌａｒｉｔｙ ｕｓｉｎｇ ｓｕｐｅｒ— ｐｏｓｅｄ ｒａｎｄｏｍ ｗａｌｋ）方法。根据随机游走距离公式 计算节点间的相似度矩阵，提出相似和的概念，对 节点与网络中其它各个节点的相似度累加得到该 节点的相似和，相似和越高，表明节点与越多的节 点有更高相似性，节点在网络中越重要。该算法考 虑了节点的度、邻接节点的重要性、节点间信息的 传递以及网络的整体结构，克服了传统方法的局限 性，使用范围广，评价结果更为精确。 ２基于叠加随机游走的重要度排序 随机游走算法¨ （ｒａｎｄｏｍ ｗａｌｋ ａｌｇｏｒｉｔｈｍ）已经 广泛应用到数据挖掘、社区发现等互联网领域。为 了直观的表达节点在网络中的作用，将随机游走应 用于复杂网络节点重要度评估，提出基于叠加随机 游走的相似和（ｓｕｍ ｏｆ ｓｉｍｉｌａｒｉｔｙ ｂａｓｅｄ ｏｎ ｓｕｐｅｒ— ｐｏｓｅｄ ｒａｎｄｏｍ ｗａｌｋ）概念，表征节点的重要程度。 ２．１ 随机游走算法 随机游走是指基于过去的表现无法预测将来 的发展方向。随机游走不存在一个固定的模式，每 一步游走所选择的方向都是随机的，不能通过参数 或者经验值来预测游走的方向。对于一个无向无 权的复杂网络，将其抽象为具有ｎ个节点ｍ条边 的无向图Ｇ＝（ ，Ｅ），Ｖ表示节点的集合，Ｖ＝（ 。， Ｖ ， ，…，Ｖ ），Ｅ表示节点间联系的集合，Ｅ＝（ｅ。， ｅ。，ｅ：，…，ｅ ），ｋ 表示节点ｉ的度，即所有与节点ｉ 直接相连的节点总数。该图的邻接矩阵用Ａ［ａ ］ 表示： ｒ１，节点ｉ和 之间有联系 ｌ０，节点 和＿『之间无联系 设定一个图上的随机游走模型：初始状态时， 将一个游走ｗａｌｋｅｒ放置在无向图Ｇ任意节点ｉ上， 规定ｗａｌｋｅｒ每一步游走以相同的概率Ｐ＝１／ｋ （ 为节点ｉ的度）到达它的任一邻居节点，以Ｐ＝０跳 跃到其它非邻居节点。也就是说该模型中节点游 走时只能通过邻接节点链依次游走，不会产生跳 跃。游走时每一步的选择都与之前的路径无关， ｗａｌｋｅｒ行走的路径是一条马尔科夫链。该模型不 仅可以很好地应用于静态网络中，对于动态网络同 样有效。图１所示为随机游走模型示意图，Ｐ为右 侧状态在下一步出现的概率。 图１中，网络的初始状态如左侧所示，将ｗａｌｋ． ｅｒ放置在节点１，节点１共有２个邻居节点，节点２ 个和节点３。即节点１的度为２，ｗａｌｋｅｒ在行走一 步时将以Ｐ＝１／２的概率游走到节点２或３，以Ｐ＝ ０的概率跳跃到节点４。 ２．２ 叠加随机游走算法的相似和求解 关于随机游走相似度的衡量存在多种不同的 ７３２ 信息工程大学学报 标准，文献［１７］提出了平均首次穿越时间ＭＦＴＰ 的概念，用ｗａｌｋｅｒ从节点 出发第１次通过节点Ｙ ｗａｌｋｅｒ 数量同样为ｆ，这种方式即为叠加随机游走（ｓｕｐｅｒ． ｐｏｓｅｄ ｒａｎｄｏｍ ｗａｌｋ）。试验中由于步数ｔ的不同，释 放的ｗａｌｋｅｒ数量也会不同，求得的相似度也会存 在差异，根据文献［２０］中的实验结果，本文中选取 ｔ＝４来计算相似度。图２为４个ｗａｌｋｅｒｓ的叠加随 机游走释放过程示意图。 ｗａｌｋｅｒ ｙ ◆ ● 一 ● 一 ， 暑 善ｗａｌｋｅｒ 图１ 随机游走模型示意图 所使用时间平均值来衡量节点 和Ｙ之间的相似 度。文献［１８］介绍了平均通勤时间ＡＣＴ，以节点 通过Ｙ的平均时间作为衡量标准。但这两种衡量 方式时间复杂度都很高，不适用大型网络。本文基 于文献［１９］对相似度计算进行了改进。用ｐ 表示 ｗａｌｋｅｒ从节点 出发，游走一步到达Ｙ的概率： ＝ （１） 其中， 是节点 的度，ｏ 是邻接矩阵中对应值。 用仃 （ｆ）表示ｗａｌｋｅｒ从节点 出发游走ｔ步之内 到达Ｙ的概率。７ｒ （￡）可以通过一步转移矩阵递 推得到，７ｒ （ｔ）是７ｒ（ｔ）矩阵第 列的列矩阵。７ｒ （ｔ）是仃 （ｔ）矩阵第Ｙ行的值。７ｒ （０）是一个ｎ １ 维的矢量，第 个值为１。Ｐ 是矩阵Ｐ的转置。 ７ｒ （ｔ）＝Ｐ ７ｒ （ｔ一１） （２） 用ｓ 表示在行走ｔ步时，节点 和Ｙ之间的随 机游走相似度： ｓ （￡）＝ ￣ｌｌ＇＇ｘｙ（ｔ）＋ ‘７Ｔｙｘ（ ）（３） 其中，ＩＥＩ是网络中节点间的连接总数。 随机游走由于过程的绝对随机性可能会使结 果产生较大偏差。比如节点 和Ｙ是有直接联系 的两个节点，节点 的度大于１，ｗａｌｋｅｒ从节点 出 发，每次游走均随机选择方向。ｔ步之后，ｗａｌｋｅｒ可 能到达一个距离节点 和Ｙ同样很远的位置，从而 测定节点 和Ｙ之间的相似度很低。为解决这一 问题，以Ａｔ：１接连不断的释放ｗａｌｋｅｒ，直至第一 个被释放的ｗａｌｋｅｒ步数为ｔ，此时网络中ｗａｌｋｅｒ的 释放 Ｏ 幽２叠加随机游走４个ｗａｌｋｅｒｓ释放过程 图２中ｗａｌｋｅｒｓ每一步游走１个单位距离。在 ｔ＝０时，ｗａｌｋｅｒｌ位于释放点；ｔ＝１时，ｗａｌｋｅｒｌ随机 沿 轴正方向行走１个单位距离，ｗａｌｋｅｒ２位于释 放点准备出发；ｔ＝２时，ｗａｌｋｅｒ１沿Ｙ轴负方向第２ 次游走，ｗａｌｋｅｒ２沿Ｙ轴负方向开始第１次游走， ｗａｌｋｅｒ３位于释放点准备出发…， ４时，ｗａｌｋｅｒｌ 游走４步，ｗａｌｋｅｒ２游走３步，ｗａｌｋｅｒ３游走２步， ｗａｌｋｅｒ４游走１步。 为获取误差更小的结果，释放多个ｗａｌｋｅｒ之 后，对ｓ 相似度进行叠加： Ｓ Ｓ Ｒ （ ）＝一￣＂Ｓ ｎ Ｗ（ｉ） （４） 对于一个固定的网络来说，其总边数ｌ Ｅ Ｉ是固 定的，因此在计算过程中，２ Ｉ Ｅ Ｉ可以被忽略。省略 的ＯＳＲＷ相似度（ｏｍｉｔｔｅｄ ｓｉｍｉｌａｒｉｔｙ ｂａｓｅｄ ｏｎ ｓｕｐｅｒ— ｐｏｓｅｄ ｒａｎｄｏｍ ｗａｌｋ）： ｓ ｏ ｓ胂（ ）＝∑．．ｓ （ ） （５） 在计算过程中，使用新的相似度公式来计算节 点之间的相关程度，生成相似度矩阵。相似度矩阵 中的每个值，代表了对应的行节点和列节点之间的 相似度。为了求得各节点的重要度，提出相似和的 概念，将各行相似度累加，生成对应节点的ＳＳＲＷ 相似和： ｓ （ｔ）＝∑ｓ （ ） （６） 第６期 宋琛等：基于叠加随机游走的复杂网络节点重要度评估方法 ７３３ 相似和不仅仅依赖于节点的某一项指标进行 判断，而是充分考虑了网络的整体结构进行综合性 评价，涉及到节点的度、邻接节点的贡献率、网络信 息传递同时考虑了节点的位置信息，可以有效地评 估节点的重要度。本文通过图３局部对称的网络 图，具体说明相似和的求解过程。 图３局部对称简单网络图 首先根据邻接矩阵计算网络的一步转移矩阵， 如图４所示。 ０ １／３ １／３ ｌ／３ ０ ０ ０ ０ １／２ ０ ０ １／２ ０ ０ ０ ０ ｌ／２ ０ ０ ｌ／２ ０ ０ ０ ０ ｌ／４ ｌ／４ １，４ ０ ｌ／４ ０ ０ ０ ０ ０ ０ ｌ／４ ０ １／４ １／４ １／４ ０ ０ ０ ０ ｌ／２ ０ １，２ ０ ０ ０ ０ ０ １／３ １／３ ０ １／３ ０ ０ ０ ０ ｌ／３ ０ １／３ ０ 图４一步转移矩阵Ｐ 根据递推关系式计算得到仃（ｔ），进行进一步 计算得到叠加随机游走的０５尺 相似度，相似度矩 阵如图５所示。 ０ ５．５６９４ ５．５６９４ ８．７９１７ ２．１６６７ ０．５９７２ ０，３３３３ ０．５９７２ ５．５６９４ ０ ２．７６３９ ６．２３６１ １．４７２２ ０．４８６１ ０．２２２２ ０．４８６ｌ ５．５６９４ ２．７６３９ ０ ６．２３６ １．３３７ ０ ４８６１ ０．２２２２ ０．４８６１ ８．７９ｌ７ ６．２３６１ ６．２３６ ０ ５．２９２ １．６１１ １．５００ １．６ｌ１１ ２．１６６７ １．４７２２ １．３３７ ５．２９２ ０ ５．４８６１ ３．８３３３ ５．４８６１ ０．５９７２ ０．４８６１ ０．４８６１ １．６ｌｌ ５．４８６１ ０ ５．１ｌ１１ ３．１ｌ１１ ０．３３３３ ０，２２２２ ０ ２２２２ １．５００ ３ ８３３３ ５．１ｌＪ１ ０ ５．１１１】 ０．５９７２ ０．４８６１ ０．４８６１ １．６１ｌ ５．４８６１ ３．１１１１ ５．１１１１ ０ 图５相似度矩阵 按行或按列累加求得各节点的相似和，如表１ 所示。在图３中节点２和３，节点６和８存在局部 对称的关系，在网络中有同等重要度，求得的相似 和这两对节点也分别相同。 表１ 网络中８个节点的相似和 ２．３算法伪代码 根据上述分析，基于Ｅｃｌｉｐｓｅ平台使用ＪＡＶＡ 语言对算法进行实现，为方便后续计算过程中节点 的随机选取，算法开始时首先打乱节点顺利，按无 序状态存储无向图，在程序运行过程中无须不断获 取随机数，顺序读取节点即可。该算法的伪代码表 不如Ｆ。 算法：基于叠加随机游走的复杂网络节点重 要度评估方法。 输入：无向图Ｇ（Ⅳ，Ｅ）； 输出：节点重要度排序； 初始化网络图并打乱节点ｓｈｕｆｆｌｅ（Ｇ）； 以邻接矩阵形式表示无向图Ｍｇｒａｐｈ； 求解一步转移矩阵Ｐ； ｆｏｒ（ｉｎｔ Ｐ＝０；ｐ＜４；ｐ＋＋） 求解ＲＷ相似度； 累加ＲＷ相似度求解ＯＳＲＷ相似度； ｆｏｒ（ｉｎｔ ｉ：０； ＜ｇｒａｐｈ．ｎｏｄｅｓ．１ｅｎｇｔｈ一１；ｉ＋＋） 计算相似和； ｆｏｒ（ｉｎｔ ｉ＝０；ｉ＜ｇｒａｐｈ．ｎｏｄｅｓ．１ｅｎｇｔｈ一１；￡＋＋） 对相似和进行排序； 按重要度输出节点 ３ 实验分析 Ｚａｃｈａｒｙ’ｓ ｋａｒａｔｅ ｃｌｕｂ数据集 是应用在复杂 网络分析中的最常用的检测网络，从１９７０到１９７２ 年，Ｗａｙｎｅ Ｚａｃｈａｒｙ用３年时间观察了美国一所大 学空手道俱乐部成员间的社会关系，构造了该社会 关系网，该网络共有３４个点，７８个联系。每个节 点代表一名俱乐部成员。观察这些成员在俱乐部 内外的交往，构造他们之间的联系。每条联系表示 对应的两名成员之间有频繁的交往。图４为空手 道俱乐部网络结构图。 图６ Ｚａｃｈａｒｙ’ｓ ｋａｒａｔｅ ｃｌｕｂ网络示意图 在调查过程中，该校校长和教练就是否提高培 训费用发生争执，俱乐部为两个派别，节点３４ 和节点１分别代表校长和教练，两个核心周围的成 员由于相互间关系的亲疏远近分成了两个派别。 ７３４ 信息工程大学学报 ｌ ２ ３ ４ ５ ６ ７ ８ ９ 印们加∞∞∞∞加０ 使用基于随机游走的相似和对该网络进行排序。 ３１与３４、３３、２、９有联系，二者度数均为５且处于 较为核心位置，因此这两个节点的重要度相对于其 驺３ ２ ４ 由于网络中节点较多，图７仅画出重要度排名前 １０的节点相似和。 Ｈ ９ 它节点应该较高。节点２４虽处较为边缘位置但其 与节点３４和３３都有联系，且度数是边缘节点中最 ３ ９ ２ Ｈ高的，因此其重要度应当高于其它边缘节点。综上 所述，节点１、３４、３３、２、３、４、９、３２、３１和２４应该是 加６ 最重要的１Ｏ个节点。本文提出的基于随机游走相 ●３ ＂ ９加２ ４ 荟 靶 排Ｊ予 图７重要度排名前１０节点相似和 从图７中可以看出，基于叠加随机游走的复杂 网络节点重要度评估方法求得的重要度结果非常 精确，节点３２、３１以及节点２４在网络中的重要度 非常相似，而该算法做出了很好的区分。为了验证 基于叠加随机游走的算法对节点重要度排序结果 的优劣，排序结果中重要度排序前１０个节点与基 于度 、基于介数 、基于接近度 和基于剥落算 法 的排序方法进行比较，结果如表２所示。 表２节点重要度排序比较 黼 ，薹靠 剥薹 序， 在数据集中，节点３４和１代表是社区的核心， 毫无疑问这两个节点应当是最重要的两个节点，节 点３３对外联系非常多，且处在连接节点３４和节点 １的中间位置，因此３３的地位也非常重要。在度 排序、介数排序和本文提出的相似和排序中，节点 １、３４和３３都是最重要的３个节点。与实际情况 相符。节点２、３、４、９处于两个网络中的中间位置， 不仅连接了网络的核心节点，且度值高，与两个模 块中的大量节点有直接联系，因此这４个节点所处 地位应当仅次于节点１、３４和３３。可以看到除介 数排序无节点４外，无论使用哪种方法进行评估， 这７个节点始终毫无争议的在重要度前１０的节点 之中。节点３２与最重要１、３４和３３有联系，节点 似和的节点重要度排序方法，排序结果非常正确、 且精确度高。 ３ ２ Ｍ ４ ９ ４ 结语 ● ”２ ３ ４ ９ 儿 本文针对复杂网络节点重要度评估，提出了一 种基于随机游走的新的评估方法，评估中引入了叠 加的随机游走，通过定义相似和来表征节点的重要 度。相似和全面考虑了节点的度、邻接节点的属性 以及节点在网络中的位置。实验证明，基于随机游 走相似和的评估算法可以准确地对复杂网络中的 各节点进行重要度评估。但该算法只能针对无向 无权网络进行评估，在下一步的工作中可以对有向 加权网络的节点重要度评估进行更多研究。 参考文献 ［１］Ｗａｔｔｓ Ｄｕｎｃａｎ Ｊ，Ｓｔｒｏｇａｔｚ Ｓｔｅｖｅｎ Ｈ．Ｃｏｌｌｅｃｔｉｖｅ ｄｙｎａｍｉｃｓ ｏｆ ｓｍａｌｌ—ｗｏｒｌｄ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｎａｔｕｒｅ，１９９８，３９３（６６８４）： ４４０－４４２． ［２］Ｂａｒａｂａｓｉ Ａｌｂｅｒｔ Ｌａｓｚｌｏ，Ａｌｂｅｒｔ Ｒｅｋａ．Ｅｍｅｒｇｅｎｃｅ ｏｆ ｓｃａｌ— ｉｎｇ ｉｎ ｒａｎｄｏｍ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｓｃｉｅｎｃｅ，１９９９，２８６（５４３９）： ５０９—５１２． ［３］Ａｌｂｅｒｔ Ｒｅｋａ，Ｊｅｏｎｇ Ｈａｗｏｏｎｇ，Ｂａｒａｂ６ｓｉ Ａｌｂｅｒｔ Ｌａｓｚｌｏ． Ｅｒｒｏｒ ａｎｄ ａｔｔａｃｋ ｔｏｌｅｒａｎｃｅ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｎａ— ｔｕｒｅ，２０００，４０６（６７９４）：３７６—３８２． ［４］Ｇａｌｌｏｓ Ｌａｚａｒｏｓ Ｋ，Ｃｏｈｅｎ Ｒｅｕｖｅｎ，Ａｒｇｙｒａｋｉｓ Ｐａｎｏｓ，ｅｔ ａ１．Ｓｔａｂｉｌｉｔｙ ａｎｄ ｔｏｐｏｌｏｇｙ ｏｆ ｓｃａｌｅ—ｆｒｅｅ ｎｅｔｗｏｒｋｓ ｕｎｄｅｒ ａｔ— ｔａｃｋ ａｎｄ ｄｅｆｅｎｓｅ ｓｔｒａｔｅｇｉｅｓ［Ｊ］．Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｌｅｔｔｅｒｓ， ２００５，９４（１０）：１４． ［５］任晓龙，吕琳嫒．网络重要节点排序方法综述［Ｊ］． 科学通报，２０１４，５９（１３）：１１７５—１１９７． 『６］Ｆｒｅｅｍａｎ Ｌｉｎｔｏｎ Ｃ．Ａ Ｓｅｔ ｏｆ Ｍｅａｓｕｒｅｓ ｏｆ Ｃｅｎｔｒａｌｉｔｙ Ｂａｓｅｄ ｏｎ Ｂｅｔｗｅｅｎｎｅｓｓ［Ｊ］．Ｓｏｃｉｏｍｅｔｒｙ，１９７７，４０（１）：３５－４１． ［７］Ｙａｎ Ｇａｎｇ，Ｚｈｏｕ Ｔａｏ，Ｈｕ Ｂｏ，ｅｔ ａ１．Ｅｆｆｉｃｉｅｎｔ ｒｏｕｔｉｎｇ ｏｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｅ，２００６，７３（４）： ０４６１Ｏ８． ［８］陈勇，胡爱群，胡啸．通信网中节点重要性的评价方 法［Ｊ］．通信学报，２００４，２５：１２９－１３４． （下转第７５９页） ８ 第６期 冯培义等：面向热点新闻事件的地图快速制作框架与实现 北京：中国科学技术大学，２００９． ７５９ 的时事地图［Ｊ］．新闻记者，２００２，７：２２—２３． ［３］Ｃａｓｐｅｒ Ｙｏｓｔ．Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ｊｏｕｒｎａｌｉｓｍ［Ｍ］．北京：中国传 媒大学出版社，２０１３． ［１１］屈展，李婵．ＪＳＯＮ在Ａｊａｘ数据交换中的应用研究 ［Ｊ］．西安石油大学学报：自然科学版，２０１１（０１）： ９５．９８． ［４］边雪清，韩有文，王海芹．专题地图制图系统设计与实 现［Ｊ］．测绘科学，２００９，３４（增刊）：１６５—１６８． ［１２］刘红芝．中文分词技术的研究［Ｊ］．电脑开发与应用， ２０１０（０３）：１－３． ［５］徐琳．基于模板技术的应急专题地图设计与制作 ［Ｄ］．郑州：信息工程大学，２０１２． ［６］Ｍａｐｅａｓ．ｃｏｍ：在地图上“阅读新闻”［ＥＢ／ＯＬ］．［２０１０・ １２—２３］．网易科技报道ｈｔｔｐ：／／ｔｅｃｈ．１６３．ｃｏｍ／１０／１２２３／ １０／６ＯＪ４ＢＦ４Ｋ０００９３８ＥＮ． ［１３］胡锡衡．正向最大匹配法在中文分词技术中的应用 ［Ｊ］．鞍山师范学院学报，２００８（Ｏ２）：４２＿４５． ［１４］黄翼彪．开源中文分词器的比较研究［Ｄ］．郑州：郑 州大学，２０１３． ［１５］张晴，李玉影．概念整合理论框架下的《静夜思》意义 建构——基于ＩＣＴＣＬＡＳ的分析方法［Ｊ］．唐山师范学 院学报，２０１５（０１）：２９—３１． ［７］张春菊，张雪英，朱少楠．基于网络爬虫的地名数据库维 护方法［Ｊ］．地球信息科学学报，２０１１，１３（４）：４９２－４９９． ［８］李志义．网络爬虫的优化策略探略［Ｊ］．现代情报， ２０１１（１０）：３１－３５． ［１６］程钢．国内主流在线地图ＡＰ１分析及优化对策研究 ［Ｊ］．测绘工程，２０１３，２２（６）：４－８． ［１７］冯振兴．Ａｊａｘ技术在Ｗｅｂ系统中的应用研究［Ｄ］．北 京：北京林业大学，２００８． ＜＞●＜＞●＜＞●＜＞●＜＞●＜＞●０●ｏ●＜＞●＜＞●＜＞●０●＜＞●＜＞●＜＞●＜＞●＜＞●＜＞●＜＞●（＞●＜＞●＜＞●＜＞● ［９］陈千．主题网络爬虫关键技术的研究与应用［Ｄ］．北 京：北京理工大学，２０１５． ［１Ｏ］曾伟辉．支持Ａｊａｘ的网络爬虫系统设计与实现［Ｄ］． ０●０●０●０●０●０●０●０●０●ｏ●ｏ●０●０●０●０●０●ｏ●０●０●＜＞●＜＞０ （上接第７３４页） ［９］谭跃进，吴俊，邓宏钟．复杂网络中节点重要度评估 的节点收缩方法［Ｊ］．系统工程理论与实践，２００６，２６ （１１）：７９—８３． ｗａｌｋ ａｌｇｏｒｉｔｈｍ ｔｏ ｃａｌｃｕｌａｔｅ ｔｈｅ ｄｅｎｓｉｔｙ ｏｆ ｓｔａｔｅｓ［Ｊ］． Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｌｅｔｔｅｒｓ，２００１，８６（１０）：２０５０—２０５３． ［１７］ＨａｉｊｕｎＺｈｏｕ．Ｄｉｓｔａｎｃｅ，ｄｉｓｓｉｍｉｌａｒｉｔｙ ｉｎｄｅｘ ａｎｄ ｎｅｔｗｏｒｋ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ［Ｊ］．Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｅ，２００３，６７ （６）：０６１９０１． ［１０］Ｂｏｎａｃｉｃｈ Ｐｈｉｌｌｉｐ．Ｆａｃｔｏｒｉｎｇ ａｎｄ ｗｅｉｇｈｔｉｎｇ ａｐｐｒｏａｃｈｅｓ ｔｏ ｓｔａｔｕｓ ｓｃｏｒｅｓ ａｎｄ ｃｌｉｑｕｅ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｍａｔｈｅｍａｔｉｃａｌ Ｓｏｃｉｏｌｏｇｙ，２０１０，２（１）：１１３－１２０． ［Ｉ ８］Ｌｕｈ Ｙｅｎ，Ｆｒａｎｃｏｉｓ Ｆｏｕｓｓ，Ｃｈｒｉｓｔｉｎｅ Ｄｅｃａｅｓｔｅｃｋｅｒ，ｅｔ ａ１．Ｇｒａｐｈ ｎｏｄｅｓ ｃｌｕｓｔｅｒｉｎｇ ｗｉｔｈ ｔｈｅ ｓｉｇｍｏｉｄ ｃｏｍｍｕｔｅ— ［１１］Ｐｏｕｌｉｎ Ｒ，Ｂｏｉｌｙ Ｍ Ｃ，Ｍａｓｓｅ Ｂ Ｒ．Ｄｙｎａｍｉｃａｌ ｓｙｓｔｅｍｓ ｔｏ ｄｅｆｉｎｅ ｃｅｎｔｒａｌｉｔｙ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｓｏｃｉａｌ Ｎｅｔ— ｗｏｒｋｓ，２０００，２２（３）：１８７—２２０． ｔｉｍｅ ｋｅｒｎｅｌ：ａ ｃｏｍｐａｒａｔｉｖｅ ｓｔｕｄｙ［Ｊ］．Ｄａｔａ ｋｎｏｗｌｅｄｇｅ ｂｉｎｇｉｎｅｅｆｉｎｇ，２００９，６８（３）：３３８－３６１． ｐｉｎｇＬｉｕ，ＬｉｎｙｕａｎＬＯ．Ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｌｏｃａｌ ［１９］ Ｗｅｉ［１２］Ｓｅｒｇｅｙ Ｂ，Ｐａｇｅ Ｌ．Ｔｈｅ ａｎａｔｏｍｙ ｏｆ ａ ｌａｒｇｅ－ｓｃａｌｅ ｈｙｐｅｒ・ ｔｅｘｔｕａｌ ｗｅｂ ｓｅａｒｃｈ ｅｎｇｉｎｅ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ＆Ｉｓ・ ｄｎ Ｓｙｓｔｅｍｓ，１９９８，３０（９８）：１０７－１１７． ｒａｎｄｏｍ ｗａｌｋ［Ｊ］．Ｅｕｒｏｐｈｙｓ．Ｌｅｔｔ．２０１０，８９（５）５８００７． Ｐｏｎｓ，Ｍａｔｔｈｉｅｕ Ｌａｔａｐｙ．Ｃｏｍｐｕｔｉｎｇ ｃｏｍｍｕｎｉｔｉｅｓ ［２Ｏ］ Ｐａｓｃａｌｉｎ ｌａｒｇｅ ｎｅｔｗｏｒｋｓ ｕｓｉｎｇ ｒａｎｄｏｍ ｗａｌｋｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ—ＩＳＣＩＳ ２００５． ２００６：１０（２）： １９１．２１８． ｉｏｎ ｆｌｏｗ ｍｏｄｅｌ ｆｏｒ ｃｏｎｆｌｉｃｔ ［２１］ Ｚａｃｈａｒｙ Ｗ Ｗ．Ａｎ ｉｎｆｏｒｍａｔ［１３］Ｌｎ Ｌ，Ｚｈａｎｇ Ｙ Ｃ，Ｙｅｕｎｇ Ｃ Ｈ，ｅｔ ａ１．Ｌｅａｄｅｒｓ ｉｎ Ｓｏｃｉａｌ Ｎｅｔｗｏｒｋｓ，ｔｈｅ Ｄｅｌｉｃｉｏｕｓ Ｃａｓｅ［Ｊ］．Ｐｌｏｓ Ｏｎｅ，２０１１， ６：ｅ２１２０２． ［１４］Ｌｅｍｐｅｌ Ｒ，Ｍｏｒａｎ Ｓ．Ｔｈｅ ｓｔｏｃｈａｓｔｉｃ ａｐｐｒｏａｃｈ ｆｏｒ ｌｉｎｋ— ｓｔｒｕｃｔｕｒｅ ａｎａｌｙｓｉｓ（ＳＡＬＳＡ）ａｎｄ ｔｈｅ ＴＫＣ ｅｆｆｅｃｔ［Ｊ］． Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ，２０００，３３：３８７４０１． ａｎｄ ｆｉｓｓｉｏｎ ｉｎ ｓｍａｌｌ ｇｒｏｕｐｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ａｎｔｈｒｏｐｏｌｏｇｉ— ｃａｌ Ｒｅｓｅａｒｃｈ，１９７７，３３（４）：４５２４７３． ｒａｌｉｔｙ ｉｎ ｓｏｃｉａｌ ［２２］ Ｆｒｅｅｍａｎ Ｌｉｎｔｏｎ Ｃ．Ｆｒｅｅｍａｎ Ｌ Ｃ．Ｃｅｎｔ［１５］Ｋｉｔｓａｋ Ｍ，Ｇａｌｌｏｓ Ｌ Ｋ，Ｈａｖｌｉｎ Ｓ，ｅｔ ａ１．Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｏｆ ｉｎｆｌｕｅｎｔｉａｌ ｓｐｒｅａｄｅｒｓ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｎａｔｕｒｅ Ｐｈｙｓｉｃｓ，２０１０，６（１１）：８８８－８９３． ｎｅｔｗｏｒｋｓ ｃｏｎｃｅｐｔｕａｌ ｃｌａｒｉｆｉｃａｔｉｏｎ［Ｊ］．Ｓｏｃｉａｌ Ｎｅｔｗｏｒｋｓ， １９７８，１（３）：２１５．２３９． ［２３］司晓静，复杂网络中节点重要性排序的研究［Ｄ］．西 安：西安电子科技大学，２０１２． ［１６］Ｗａｎｇ Ｆ，Ｌａｎｄａｕ Ｄ Ｐ．Ｅｆｉｃｉｆｅｎｔ，ｍｕｌｔｉｐｌｅ－ｒａｎｇｅ ｒａｎｄｏｍ
