[科普中国]-关键节

关键节定义

关键节在杂网络中的结构洞节点对于信息传播具有重要作用, 现有关键节点排序方法多数没有兼顾结构洞节点和其他类型的关键节点进行排序. 本文根据结构洞理论与关键节点排序相关研究选取了网络约束系数、介数中心性、等级度、效率、网络规模、PageRank值以及聚类系数7个度量指标, 将基于ListNet的排序学习方法引入到复杂网络的关键节点排序问题中, 融合7个度量指标, 构建了一个能够综合评价面向结构洞节点的关键节点排序方法. 采用模拟网络和实际复杂网络进行了大量实验, 人工标准试验结果表明本文排序方法能够综合考虑结构洞节点和核心节点, 关键节点排序与人工排序结果具有较高的一致性. SIR传播模型评估实验结果表明由本文选择TOP-K节点发起的传播能够在较短的传播时间内达到最大的传播范围. 复杂网络的研究一直备受关注, 为了解释不同网络所具有的不同特征, 研究焦点从网络的社团结构到网络中的关键节点发现。

关键节点对复杂网络上的信息传播、防止传染病的传播和扩散等现实情境起到重大作用. 网络中关键节点排序问题不仅与网络拓扑结构特征有关还应考虑到其功能特征因素. Burt 的结构洞理论[5]认为, 在社会结构中占据结构洞位置的企业会获得更多的竞争优势, 从而使企业获得累加收益, 包括信息利益和控制利益. 在信息社会中, 处于结构洞位置的成员能够获取更关键的信息, 从而影响甚至控制社会关系与信息的传播. 如图1所示, 该图为互联网上某个热点话题的传播图, 图中红色节点为处于结构洞的节点, 社会媒体上一些热点话题被拥有粉丝较多的蓝色节点发起, 而处于边缘地带的结构洞节点却带动了将近50%的话题传播量, 如果没有这些处于结构洞的节点发挥作用, 话题将不会有广泛的传播范围, 这说明话题在传播过程中, 核心节点固然很重要, 但处于结构洞的节点也起到重大作用. 所以, 关键节点排序问题关注的焦点不能仅局限于网络中的核心节点, 也不可忽略处于结构洞位置的节点. 现有关键节点排序研究很少考虑结构洞节点,如何在复杂网络的关键节点排序问题中综合考虑结构洞节点和其他类型的关键节点是一个值得深入研究的问题.近年来, 复杂网络中的关键节点的排序问题已经成为研究热点. 定量的衡量网络中节点的重要程度通常会用到一些中心性度量指标, 如节点的度、接近中心性、流介数中心性, Katz 中心性等, 但是这些指标对网络的拓扑结构依赖性很强. 而Kitsak 等从新的视角提出利用K-核分解来研究网络中的关键节点, 该方法认为关键节点的重要性与其所处网络的位置有关, 将外层的节点层层剥去, 处于内层的节点即为网络中的关键节点. 另外, 在搜索引擎领域, 排序问题的研究已经广为人知, 如著名的Google网页排名算法Pagerank, Lü 等提出的LeaderRank算法这些关键节点排序方法各有利弊, 于是学者们寻找综合性的方法对网络中的关键节点进行评价. 于会等提出了一种多属性决策的排序方法, 对网络中单个节点的度中心性、介数中心性等多个指标作为决策评价方案的属性进行综合计算, 从而对网络中关键节点进行排序; Hou 等考虑度、介数、K-核三个不同指标对节点重要性的影响, 采用欧拉距离公式计算三种不同指标的综合作用得到节点的排序结果; Comin等综合考虑介数与度的关系, 定义了一个关键节点排序的指标; 任卓明等提出了一种基于度与聚类系数的网络节点重要性度量方法对大规模网络的节点重要性进行有效分析; 周漩等针对节删除法、节点收缩法和介数法的不足综合考虑了节点效率、节点度值和相邻接点重要度贡献, 提出了一种利用重要度评价矩阵来确定复杂网络关键节点的方法通过实验证明, 这些综合利用度量指标的方法取得的结果均优于单个指标获得的关键节点排序结果, 但是这些排序方法也没有融入具有结构洞特征的因素, 因而无法考虑处于结构洞位置的关键节点.对于复杂网络中面向结构洞的关键节点排序问题的研究目前不多, 一方面是由于处于结构洞位置的节点拥有独特特征, 这些特征将结构洞节点与复杂网络中的核心节点区分开, 因此即使处于结构洞的关键节点在网络中发挥重要作用却依然容易被忽略。

另一方面, 在复杂网络中关于结构洞的研究还不深入, 如何在复杂网络中科学的测量结构洞节点还值得探索. Burt提出的几个定量描述结构洞的指标, 如网络约束系数(Constraint, CT)、网络有效规模(EffectiveSize, ES)、效率(Efficient,EF)、等级度(Hierarchy, HI)等; Freeman提出用介数中心性(Betweenness Centrality, BT)测量方法描述结构洞 这些指标能够定量的刻画结构洞的一些局部特征. 根据相关结构洞指标, 本文提出一种能够融合结构洞特征与网络节点其他重要性特征的排序方法, 从而更加全面的对网络中的关键节点进行综合评价.排序学习方法是当前文本检索领域的研究热点, 它将机器学习方法引入到信息检索的文档相关性排序问题中, 充分考虑各种排序方法对最终排序结果的影响, 通过训练学习排序参数, 将各种排序方法视为特征, 对文档的相关性做综合的评估.本文将该方法引入到复杂网络中面向结构洞节点的排序问题上, 对不同的度量指标进行排序学习,最后获得参数.排序学习方法能够有效结合多个特征的关键在于该方法能够学习多维特征的参数估计问题.而排序学习方法根据训练样本的不同可以分为三类: 基于单个样本的Pointwise算法、基于样本对的Pairwise算法和基于样本队列的Listwise算法.Pointwise算法将每个训练数据集作为学习样本,将分类问题转化为单个文档的分类和回归问题;Pairwise算法将训练数据集中有不同相关性标注的一对数据作为样本, 根据这些样本对将排序问题转化为二值分类问题, 如应用比较广泛的RankingSVM[26]算法; Listwise算法将训练数据的相关性序列作为样本, 该样本序列与标注序列的距离作为损失函数进行学习, 这三类方法中Listwise算法的实际效果最好, 因此这种方法是排序学习领域当前的研究热点, 而其中应用效果较好的算法是ListNet 算法[27]. 所以本文将ListNet 排序学习方法引入复杂网络多指标关键节点排序问题中.综上所述, 本文将基于ListNet排序学习方法对网络中单个节点的CT, EF, ES, HT, BC, Pager-ank 值(PageRank, PR)、聚类系数(Clustering Co-efficient, CC)这7个度量指标进行融合, 综合评价复杂网根据具有人工排序的实验结果分析, 综合7个度量指标评价复杂网络中的关键节点比单一指标评价效果更好, 验证了相关研究阐述的集成性排序方法优于单个指标排序的结论对于大型复杂网络, 本文方法排序得到的TOP-K节点能够在较短的时间内达到最大的传播范围, 在网络拓扑结构具有多样性的情况下效果更佳, 说明本文方法选择出的节点具有较高的传播能力, 对于现实复杂网络中的实用性比较强.由于介数中心性计算复杂度高, 下一步工作中, 我们将优化本文方法, 探索利用简单指标实现有效排序, 将本文方法运用在更大型的复杂网络关键节点排序上.络中面向结构洞的节点的重要性。1

关键节算法关键节优化针对传感器网络多跳通信和多对一的流量特征，提出负载均衡的约束条件，将关键节点集选取问题转化为多目标优化问题，提出一种基于非支配遗传算法的关键节点集轮换算法。通过节点密度控制机制，从投放的节点池中选取关键节点集，以满足监测区域覆盖连通。在每轮网络工作的开始，激活不同的关键节点集，保证在每个时刻，有且仅有一个节点集完成对网络的充分覆盖。仿真结果表明该算法能够快速收敛于最优解，极大化网络关键节点集数目，有效延长网络的生存时间。无线传感器网络由大量集成了传感器、处理器、无线通信等模块的低功耗节点以 Ad hoc 方式构成，节点协作完成监测区域环境信息的采集、处理和转发，可以为环境监测、工业控制和灾难现场紧急救援等诸多应用提供支持。受制于传感器节点的能量有限性及其应用区域的不可达性，无线传感器网络大多通过飞机布撒等方式投放大量节点以消除覆盖盲区。但是这种高密度的节点部署方式往往会导致共享无线信道的节点之间相互竞争，进而发生通信干扰，不仅影响数据传输的可靠性，而且能量开销较大。为此，覆盖控制问题成为传感器网络研究中的关键问题。立足于传统计算机网络定义，网络覆盖通常归属于系统“服务质量”范畴。当网络覆盖低于预先定义的阈值时，表征整个网络已经不能提供正常的功能，即网络失效。密度控制是无线传感器网络覆盖问题的一种有效解决方案。

关键节排序基于 NSGA-II 的多目标优化关键节点集轮换精 锐 非 支 配 遗 传 算 法 NSGA-II(Non-dominatedSorting Genetic Algorithm)从非劣性排序、以拥挤距代替适值共享及基于精锐策略保留优异解等三个方面对原始 NSGA算法进行改进，具有快速求解 Pareto 最优解的能力。基于 NSGA-II 进行无线传感器网络关键节点集选取首先需要将问题空间转化到编码空间。为了避免重组操作中丢失优秀解，采用了一种循环重组的方法。同时，为了避免高适值个体快速繁殖而导致早熟，本文在非支配排序的过程中引入了删除算子，用来删除种群中的相同个体。

关键节求解通过将多目标优化领域相关理论引入节点集轮换求解中，提一种基于 NSGA-II 的覆盖节点集选取机制。充分考虑全网通信的负载均衡需求，从而尽可能利用网络剩余节点，在节省网络能量的同时，增强了网络的健壮性。仿真实验表明，提出的多目标优化覆盖节点集轮换算法与现有的最大小限制条件的启发式算法相比，具有更优良的性能，为以后的研究奠定了良好的基础。2

关键节应用应用实例为解决乳腺癌疾病模块挖掘方法中基因表达谱样本数量少、数据不完整、存在噪声和偏差的问题，提出了一种基于关键节点子团和局部适应度的候选疾病模块挖掘算法———KNGLF 算法。 该算法首先将候选基因与致病基因间的重叠相似性得分和功能相似性得分进行融合，通过比较融合得分与阈值，筛选出关键节点，并构建关键节点子团; 然后，基于局部适应度及不同节点对应的不同判定标准，扩展挖掘候选疾病模块; 最后，根据富集分析结果确定候选疾病基因模块。 实验结果表明，与现有其他乳腺癌模块挖掘算法相比，KNGLF 中关键节点选择算法所得平均排名较小，曲线下面积较大。 KNGLF 算法挖掘出 15 个具有较显著生物意义的乳腺癌候选疾病模块。

关键节应用背景此外，KNGLF 算法还可扩展至其他疾病候选模块。癌症是一种细胞失控增长的复杂多发疾病，在全世界范围内已成为一个重要的公共健康问题。 在各类型癌症中，乳腺癌是全球女性最常见的恶性肿瘤，世界上绝大多数国家在过去 20 年中发病率都持续增长。 以统计生化试验的方法来寻求疾病分子靶点进行治疗，虽然取得了一定的成果，但大都以特定的基因目标为试验对象，因而所得结果有限，且需消耗大量时间和人力物力。通过生物网络挖掘疾病功能模块，不仅能为分子靶点研究提供有效的信息，还能展示疾病基因及其产物以及它们彼此之间的协同关系，全面阐明其在复杂疾病过程中的作用机理。 目前，学者们已提出了多种基于网络的乳腺癌疾病模块挖掘方法。提出了一种基于路径的乳腺癌核心模块挖掘方法，利用该方法虽然辨识出了一些与该疾病有关的生物标记和功能模块，但由于主要依靠基因表达谱数据，故易受表达数据缺失、冗余和偏差以及样本数量有限的影响，且模块构建较为简单，没有进行更深入的筛选。

关键节前景利用已有工具从构建出的局部共表达网络中挖掘模块，然后结合差异表达基因和显著样本的分布特性来筛选出癌症风险模块，通过与已知癌症样本之间的风险关系来判断模块的疾病风险程度; 该方法仍局限于表达谱所涉及的基因，且使用统一的阈值来确定基因间连接关系，故而会导致一些弱相关性基因丢失。鉴于此，本文提出了一种新的基于关键节点子团和局部适应度算法来挖掘乳腺癌候选疾病模块。该算法不使用基因表达谱数据，采用融合打分策略筛选出关键节点并构建关键节点子团，借助关键节点子团和局部适应度的思想进行模块挖掘，并根据富集分析来决定所挖掘模块是否为候选致病基因模块。挖掘结果及部分富集分析在致病基因集中，从 BCGB，G2SBC 和 OMIM数据库中分别收集了 62，44 和 48 个致病基因，剔除重复数据后，获得 138 个乳腺癌致病基因。 利用表型间相似性构建相应候选基因集，通过打分筛选，最终得到 1 935 个关键节点，并构建出各关键节点子团。 采用 KNGLF 算法挖掘候选疾病模块，应用在线工具 Go-TermFinder 进行富集分析和确认，显著性阈值 P 默认为 0。 01，最终获得 15 个具有一定生物学意义乳腺癌候选疾病模块。以排名第 1 的关键节点子团所挖掘出的台 DAVID，分别在生物过程、细胞成分和分子功能以及 KEGG 通路中进行富集条目( P