６通信设计与应用 ２０１７年４月上
关于衡量网络节点重要性算法的分析和评价
张俊怡 ，张晋畅ｚ，张斌 ，姚栓
（１．东北大学，１１００００；２．中国矿业大学，２２１１１６；３．江苏师范大学科文学院，２２１１１６；４．西安科技大学，７１００５４）
【摘要】无论是在自然界中还是现代社会中，网络无处不在，有复杂系统的地方往往便有网络。如自然界中的食物链关系网、社会中的人际关
系网、流行疾病传播网络以及互联网等，如何衡量网络中节点的重要性一直都是复杂网络研究中的一个重要研究问题。目前有很多学者提出了 相关的衡量算法，包括有李鹏翔等提出通过度量节点删除对网络的破坏性来衡量节点重要性；ＫｉｔＳａｋ等人提出了适用于大型网络的利用Ｋ一核 分解获得节点重要性的排序指标；任卓明等提出基于度与集聚系数的节点重要性度量方法。本文就以上三种算法进行分析，并且结合其适用情
形、计算性能等进行了综合评价，最后基于这些衡量算法，本文给出了新的基于Ｋ一核分解层层局部深度遍历的节点重要性评价方法。
【关键词】复杂网络；节点重要性；衡量算法；Ｋ一核分解；度与集聚系数
【中圄分类号】ＴＮ９１５．０ 【文献标识码】Ａ 【文章编号】１００６—４２２２（２０１７）０７—０００６—０３
１引舌
准确的对网络中节点的重要性进行衡量．无论是对提高
网络的鲁棒性。或者是找出关键节点从而有效的摧毁整个网
络都具有重要的意义。比如在学校的网络连接中。找出重要的
路由器节点．如果这些节点的失效，很有可能会瘫痪整个学校
的网络．我们就应该对这些重要的路由器节点进行冗余备份
处理：再比如网上的谣言传播网络．谣言的传播往往会对社会
造成重大的社会影响，所以找出谣言网络中的重要节点（比如
一些微博大Ｖ）加以遏制或者是摧毁，对于破坏谣言传播网络
抑制谣言的传播很有作用。长期以来，很多学者在如何衡量网
络节点重要性方面都提出了相关的算法。 ２算法分析与评价
２．１相关属性指标的定义
现在假设网络为Ｇ（Ｖ，Ｅ），Ｖ是节点集合，Ｅ是边的集合，
Ａ＝【ａｌ１］为邻接矩阵，ａｉｊ＝１说明两个节点相邻，否者ａｉｊ＝０，Ｎ为网
络中节点的数量．在对节点重要性衡量之前．先提出几个下文
提及的相关属性指标
（１）节点的度：节点ｉ的邻居数量
ｋ（ｉ）＝乏ａ。． Ｊ Ｇ （２）多级邻居信息：节点ｉ邻居的邻居的最近邻居数和次
近邻居数之和总和：
ｌ（ｉ）＝∑∑Ｎ（ｕ）
ｊＣｌ＇（ｉ）ｕ ） Ｆ（ｉ）是指节点ｉ的邻居节点集合，ｒ（ｊ）是指节点Ｊ的邻居
节点集合，Ｎ（ｕ）是节点ｕ的最近邻居数和次近邻居数之和。
（３）紧密度：表明节点在网络中对其他节点施加影响力的
能力，紧密度越大，袁明节点越位于网络的中心。
ｃ（ｉ）
ｊ＝ｌｄ ｄｊｉ表示节点ｉ到节点ｊ的最短路径，它依赖于整个网络的
拓扑结构，所以计算的时间复杂度比较高．为Ｏ（ｎ３）。
２．２ Ｋ一核分解算法
２．２．１算法思想 由于直接用节点的度等来衡量节点的重要性局限性太
大，没有考虑到节点在整个网络中位置这一情况。例如，如图１，
节点１、节点２和节点４的度都是一样的，但节点１作为根节
点，重要性可能会远比另外两个点大。
Ｋ一核分解法即体现了节点重要性依赖于其在网络中的位
置这一思想，它是一个层层递进递归删除节点的过程。
定义：Ｋ一核，一个节点集合Ｃ是整个网络节点集合Ｖ的 图１树状图
子集，Ｃ中任一节点ｖ的度不少于Ｋ。由其所推导出的最大子
图即成为Ｋ一核，也可理解为递归的移除掉节点度数小于Ｋ的
节点和与其相连的边后形成的子图。
节点核数：一个节点属于Ｋ一核而不属于（Ｋ＋１）一核，则节
点核数为Ｋ
如图２中的Ｋ一核的分解实例，Ｋｓ为Ｋ一核的简称，其最外
层为Ｋｓ＝ｌ，即所有的节点的度都不小于１，然后删除所有Ｋ 中度为１的节点及其相连的边，删除后还有则继续删．可以看
到Ｋｓ＝２中所有节点的度均不小于２。依次类推
图２ Ｋ－核分解实例
２．２．２算法分析与评价
该算法通过Ｋｓ指标来衡量节点重要性．即Ｋｓ越大节点
重要性越大，也就是节点的核数；ＫｉｔＳａｋ等人通过调查发现。 在单个传播源的情形下，用Ｋｓ指标衡量比用度数指标衡量更
为有效，但是该算法仍然是有局限性的，比如在多个传播源的
情形下，效果不一定会更好；还有就是Ｋｓ赋予了大量的节点
具有相同的核数值，所以无法具体分别出同一Ｋｓ内中的节点 的相对重要性，但是该算法适用于节点数多的大型网络。计算
的时间复杂度较低 ２－３通过度量节点删除对网络的破坏性来衡量节点
重要性
２．３．１基本思想
节点重要性可以通过度量节点删除对网络的破坏性来衡 ２（）１７年４月上
量，破坏性是通过节点删除后所有不连通的节点对之间的最 短路径的倒数之和来反映的．之所以用倒数，是暗示删除节点
对距离越近的或者说是直接连接的点破坏性越大．距离远的 间接的连接的点的破坏性较小 破坏性指标在具体计算的时
候需要分为直接破坏性和间接破坏性
节点间的连接以及距离可以用邻接矩阵来表示，最短路
径的寻找则可以用迪杰斯特拉算法．下面我们通过一个具体
例子来分析．如图３所示，假设节点直接距离均为１，现在我
们删除节点ｌ
｛ ５． ）
ｔ 图３删除前 ｏ ④ （兰） 一≯一＠
图４删除后直接破坏力 图５删除后间接破坏力
如图４，删除后的直接破坏计算为Ｄ＝１／ｄ（１，２）＋ｌｉｄ（１，３）
ｄ（１，２）表示节点１到节点２的距离，其他同理，也就是节
如图５，删除后的间接破坏计算为Ｍ＝１／ｍ（２，３）＋Ｉ／ｄ（２，５）
阵表述
系，能够较为全面的体现其在整个网络中的节点重要性，并且
计算公式简单，不足就是计算的时间复杂度太高，复杂度高的
原因：①因为对于每个节点都要考虑网络中所有其他节点的
距离关系：②在找最短路径的时候迪杰斯特拉算法的时问复
２．４肚ｔ＝度－．ｊ集聚系数的 点黍要性度 方法
准确识别重要节点．但是则仍然没有考虑到节点与其邻居之
间的一个紧密程度．而集聚系数这能反映该因素，于是结合节
点的度与集聚系数来衡量节点重要性便可解决这一问题，并
节点的度上文已经定义了为ｋ．，下面来看聚集系数的定叉
聚集系数：ｃ ｋｉｆ ｋｉ ＇－ｉ￣ ．表示节点ｉ与任意两个邻居节
任卓明等提出了新的节点重要性评价指标Ｐ．表示为：
、 ｆｉ ∑．ｇ ｌ ＾
ｆ表示节点ｉ自身的度与其邻居的度之和，ｒ．表示节点ｉ的
邻居节．点的集合，ｋ 表示节点Ｗ的度，Ｎ为网络总节点集合、
Ｐ 式子采用了同趋化函数．使得其能反映出不同指标结
合在一起后的综合作用力， 将聚集系数和度的信息结合在
了一起，ｇ．是用对ｒａｉｎ—Ｈ１ａｘ标准对 进行归一化处理．．
该算法通过指标ｆ１．来反映节点重要性，其值越大，表明节 通信设计与应用７
点与其邻居的紧密程度、节点的度和邻居的度之和的综合作
用力越大．也就是节点重要性越大该算法只需要节点的邻居
信息以及聚集信息等局部信息．同样适用于大规模网络中 ３新的衡量算法
３．１基本思慰
本文提出来的新的衡量算法是基于Ｋ一核分解法的改进
算法，是一种在Ｋ一核分解模型中一层一层通过局部深度遍
历．记下节点的访问次数，然后向内层传值的一个过程
在一次深度遍历网络节点的过程中，重要的节点往往会
被访问更多次．但是如果直接用节点访问次数作为指标．显然 和只考虑节点的度是一样的．忽略了节点在整个网络中的位
置．并且当网络过大时，深度遍历显然时间复杂度过大，而Ｋ一
核分解法却是一个好办法．不但能考虑到节点的位置，而且能
将网络划分为一个个小网络．于是将这两个思想相结合，提出
在Ｋ一核分解模型中从最外层开始一层一层通过局那深度遍 历，然后位内层传值，直到访问完所有节点这一算法
如图６，图６是图２中ｋ一核分解的上半部分，三种颜色代
表三层．最外层Ｋｓ是１，最内层Ｋｓ是３，以此为例来讲解改进
的算法、
图６
３．２算法实现过程
第一步．通过Ｋ一核分解将网络分为了三层，如图所示，最
外层分为了两个子图，分别进行局部深度遍历，两个子图分别
是节点集合ａ：Ｉ８，９，１Ｏ，１ １，１２，ｌ３］和ｂ＝【７］，分别从这两个子图 选取度最小的节点开始深度遍历，现在假设从ａ中选取节点
１０开始遍历．碰到下一层的节点不访问，直到遍历完所有节
点，遍历的路径是ｆ１０，９，１ ｌ，９，８，１２，８，１３，８】，从ｂ中选取节点
７开始遍历，遍历的路径是｛７１，定义一个Ｃ． 表示第ｉ个节点出
现的次数，则Ｋｓ＝ｌ层中节点的Ｃ。，值如表ｌ所示
表ｌ
节点ｉ ７ ８ ９ ｌＯ ｌｌ １２ １ ３
Ｃ． １ ３ ２ １ １ ｌ ｌ
从表ｌ中可以看出节点８的重要性是最大的，其次是节
点９、 第二步．将第一次各子图中遍历出的最大Ｃ 值赋给与该
子图直接相连的内层节点，如内层节点获得多个赋值，则将多 个赋值求和作为自身的Ｃ 值的基数，即，ａ节点集合中的节点
８与节点５相连，则节点５的Ｃ 从３（在ａ节点集合中具有最
大的Ｃ．．值的节点是节点８，为３）开始访问次数，同理，节点６
的基数是１．然后删除Ｋｓ＝１层中所有节点，对Ｋｓ＝２层中各子
图重复第一步 第三步．对网络中所有节点按重要性进行排序，需要注意
的是，（： 值只能在同层比较，同层值越大节点越重要，内层节
点重要性永远要比外层大，即，哪怕内层Ｃ 值小，它也比外层
９＿ｏ ８通信设计与应用 ２０１７年４月上
无线网络ＭＯＯ Ｃ ｓ大数据聚类方法优化研究
伍 斌（广东海格怡创科技有限公司，５１０６２７）
【摘 要】ＭＯＯＣ （ ａｓｓｉｖｅ。ｐ。 ０ｎ ｌｉｎｅ 。ｕｒｓｅｓ）即大型开放式网络课程。是一种基于远程课程教学与无线网络和通信技术结合发展的新的在线
网络课程，能给学生提供更大的学习空间。聚类分析是较为常见的学习分析和数据发现的方法，其基本原理是根据对象的属性特征让不同特征
的对象形成各种类别。这种方法在ＭＯＯＣｓ中有重要的作用和广泛的应用。无线网络数据量大而且比较冗杂，以往的将ＭＯＯＣｓ大数据分类分
析属性进行聚类的方法有很大的不精确因素。对无线网络ＭＯＯＣｓ大数据快速准确聚类促进大数据的处理能力。对聚类方法的优化处理，能有
效的促进相互交流学习和聚类综合性能的提高。
【关键词】无线网络；ＭＯＯＣｓ大数据；聚类；方法优化；分析 【中图分类号】ＴＰ３１１．１ 【文献标识码】Ａ 【文章编号】１００６—４２２２（２０１７）０７—０００８—０２
引言
随着科技和网络技术的不断发展。各种电子商务活动已
经融入我们的日常生活。ＭＯＯＣｓ即大型开放式网络课程的迅
速的发展，在线学习系统不断完善，数据量也在激增，人们对
这些大数据的关注度也来越高 通过后大数据分析处理提高
管理和学习效率．是研究者们关注的热点。聚类分析的核心就
是分类。各个类别的数据有较大差异．而类别之类具有相似的
属性特征 本文就无线网络ＭＯＯＣｓ大数据聚类方法极其优化
进行分析讨论
ｌ在线学习研究中聚类的一般流程
１．１变量选择
聚类研究的基本思路是对一组变量的取值计算变量对应
对象的相似程度。所以，参数的选择对聚类研究有极大得影
响．基于各种不同的研究问题．需要从可获得的研究数据中找 到或者计算出规定能够表示学习特征的变量作为聚类研究最
初的参数。聚类分析变量的确定简单选择某一参数，也可以对
相关数据的多个参数聚合。
１．２聚类的过程
聚类的过程其实是一个分组的过程．产生不同的类别。研
究对象的相似性比较可采用较多方式．相对的聚类算法也分 为四类，分男ｌｊ是层次化聚类算法，划分式聚类算法，基于密度
和网格的聚类算法和其他聚类算法。由于对象的之间的相似
性有一定不确定性，所以聚类结果存在误差。不同算法得到的
结果也会不同．所以经常要进行比对。
１．３类别分析
进行数据聚类后会出现多组数据。对这些类别要进行一
，ｔ：Ｚ≯ 移 定的注释分析，是以原始数据和参数为依据的。聚类后需要时
这些组别分别进行概括性的描述。常用的衡量活跃水平和学
习绩效的方法是取值高低。在实际中发现，就单纯的数据取值
高低很难进行聚类结果的有效解释，需要同时结合教学过程
进行深入的研究分析。通常还需进行不断地调整改变才能得
到最终的有意义的解释 １．４有效性检验
有效检验包括聚类变量残花自身有效性的检验和其他变
量具有统一标准两个方面［１ｌ。 ２传统的ＭＯＯＣｓ大数据聚类方法
聚类分析对数据的挖掘处理和分析具有重大的作用。聚
类分析既可以对大数据库中存在的数据进行深入详细信息的
发现和研究。还可以是对其他数据挖掘处理的预处理步骤。传
统的大数据聚类处理的目标是实现快速高效的目的。通过对
大量的告诉变化的数据聚类．实现在线变动大数据的准确处 理．但是．当大数据渗入到更高的维数的复杂情况时，聚类的
精确度很快降低．同时对大数据的空间复杂性很难求出真正
正确的聚类映射
传统的Ｍ００Ｃｓ大数据聚类分析方法能成立数据的宏观
定义．对大数据聚类处理后能呈现一个直观的分布，一目了
然．以此为依据就可以发现类别数据间的一些联系．但是这种
办法的应用增大了计算量，从而造成聚类可靠性和精度下降，
所以有必要对ＭＯＯＣｓ大数据聚类方法进行优化目。
３针对传统ＭＯＯＣｓ大数据聚类方法弊端的
优化方法及分析
３．１非线性时间序列分析的ＭＯＯＣｓ大数据聚类
Ｃ ．值大的节点更为重要。
４总结与期望
全文一共详细的分析和评价了现有的具有代表性的三种 节点重要性衡量算法，并且基于Ｋ一核分解法提出了改进的算
法，但是由于作者不具有实验的环境和数据，所以并未对提出 的改进算法进行实验证明 希望有感兴趣的学者能够对此进
行实验．并且和其他算法进行一个相关的对比。
参考文献
［１］李鹏翔，任玉晴，席酉民．网络节点（集）重要性的一种度量指标．系
统工程，２００４．２２（４）：１３～２０． 【２１任卓明，邵风，刘建国，郭强，汪秉宏．基于度和集聚系数的网络节 点重要性度量方法研究．物理学报．２０１３．１２． ［３】任卓明．复杂网络中的节点重要性度量ｆＤ］．上海理工大学，２０１３，１２． 宋起超．一种新的改进的加权Ｋ一核分解方法．软件工程，２０１６．１９
（１）：２１－２２． ［５］曹玖新，董丹，徐顺，郑啸，刘波，罗军舟．一种基于ｋ一核的社会网 络影响最大化算法．计算机学报，２０１５，３８（２）：２３８～２４８． ［６］任卓明，刘建国，邵凤，胡兆龙，郭强．复杂网络中最小Ｋ一核节点的 传播能力分析．物理学报．２０１３．１０．
收稿日期：２０１７—２—６
作者简介：张俊怡，男，大三本科生，研究方向为数据挖掘、大
数据、人工智能。
张晋畅．男，大二本科生。 张斌，男，大二本科生。
姚栓，男，大一本科生。