网络节点重要度的快速评估方法

对网络节点进行重要性评估, 快速发掘重要性节点已经成为数据挖掘、复杂网络中的一个基本问题, 现有的节点重要度评估方法对于大型网络而言, 计算速度较慢. 基于电阻网络提出一种快速实用的节点重要度评估方法, 该方法利用节点对网络电能消耗的影响来评估节点的重要度, 如果由于一个节点的存在而导致网络平均电能消耗减少, 则该节点就越重要, 反之则该节点重要度就低. 该方法的时间复杂度为O(n³), 在分布式扩展的情况下可达到O(n), 实验分析证明了该方法的有效性, 而且运算速度快, 能处理大规模网络.     

节点重要度贡献的复杂网络节点重要度评估方法

引入m阶邻居节点的概念,提出了一种基于m阶邻居节点重要度贡献的复杂网络节点重要度方法,并引入α和γ两个参数,用于调节节点重要度评估对节点自身特性及m阶邻居节点的依赖程度。综合考虑了节点自身及1到m阶邻居节点的重要度贡献。为检验算法的有效性,采用ARPA网络拓扑并针对算法在不同m取值条件下的节点重要度情况进行了评估。评估结果显示,与度值法、介数法、节点删除法等评估方法相比,具有更高的评估精度,能显著地区分复杂网络中节点之间的重要性差异,能准确地确定网络中关键节点,保证节点重要度评估的准确性;此外,实验结果还揭示了一个重要动力学现象,即当邻居节点所考察的深度m值大于网络的平均路径长度L时,该方法可得到可靠且精度较高的评估结果。     

复杂网络中节点重要度评估的节点收缩方法

首先定义了网络的凝聚度,在此基础上提出了一种评估复杂网络节点重要度的节点收缩方法,认为最重要的节点就是将该节点收缩后网络的凝聚度最大,其算法的时间复杂性为O(n3).该方法综合考虑了节点的连接度以及经过该节点最短路径的数目,克服了节点删除法的弊端.最后的实验分析表明该方法直观、有效且运算速度快,对于大型复杂网络可以获得理想的计算能力.     

能力与权力:大规模复杂网络重要节点识别的二重异质指标及算法

为快速识别大规模复杂网络中的重要节点,本研究将人类社会普遍存在的两类不平等映射为节点在网络中的能力与权力的二重异质性,设计了评价复杂网络节点重要度的DH指标,构造了用于DH指标快速分布式计算的并行随机距离渐进(parallel random distance approach,简称PRDA)算法.通过网络最大连通率、网络均衡熵、算法有效性和算法效率的评价实验验证DH指标及PRDA算法的有效性,得出结论如下:DH指标在识别重要节点时能适应不同拓扑特征的复杂网络,识别性能优于或同于时间复杂度更高的介数;PRDA估计算法在最短路径获得概率p=1-10~(-1.5)的水平上得到的节点效率估计值■与真实值η_i的Pearson相关系数在0.975以上,且在大规模网络上进行节点效率估计结果更可靠;在Apache Spark并行内存计算环境中应用时间复杂度为O(n~2/l)的PRDA算法求解DH指标耗时远小于介数求解耗时,这表明算法的时间特性也适于大规模网络.     

改进的加权复杂网络节点重要度评估的收缩方法

分析了加权复杂网络的结构特点,综合考虑了边权对节点重要度评估的影响,给出了加权节点重要度的新定义,并提出了改进的适用于加权网络的节点收缩方法.该方法认为最重要的节点就是收缩后加权网络凝聚度最大的节点,其算法的时间复杂度为O(n³).该方法有助于更准确地发现复杂网络中的关键节点.最后的实验分析验证了方法的有效性和可行性.     

网络可靠性评估的演化过程重要度抽样模拟方法

针对具有高可靠度网络的连通失效概率计算问题,提出了一种重要度抽样Monte Carlo模拟方法.首先提出了考虑节点和边单元失效网络连通状态判别的演化过程算法,算法根据网络节点和边单元的可靠度,将每次模拟抽样产生的随机数转化为单元的修复时间;按照单元修复时间次序构建网络连通拓扑结构,并视为向网络连通状态转变的演化过程.然后基于重要度抽样Mont,e Carlo模拟求解高可靠度网络的2\K\All端连通失效概率,其中重要度抽样函数的计算采用基于演化过程和交叉熵模型的多准则迭代方法.高可靠度网络算例的计算结果表明,预抽样求解重要度抽样函数时,多准则迭代方法所需的预抽样次数约为其他迭代方法的1/40.因此,本文方法具有较高的计算效率.     

基于Kullback-Leibler距离的网络节点一致性排序

在复杂网络中,重要节点比其它节点能更大程度地影响网络的结构与功能.如何评价节点之间的相对重要性,找出重要节点,是一个重要的研究课题.已有的节点重要性评价和排序方法存在一定的局限性.为此,本文综合节点基本属性,依赖网络拓扑特性,提出基于Kullback-Leibler距离的节点一致性排序方法.最后,通过实例分析,验证了本文方法较已有方法在不同类型网络上的有效性和适用性更强.     

大规模人群网络流瓶颈识别方法研究

在体育赛事、集会等场合,大规模人群沿路网流动过程中易发生拥塞并诱发恐慌、踩踏等严重事故.因此,理解网络结构对人群流动特征的影响,对大规模人群在网络上的流动进行有效的组织和管理十分必要.首先结合大型活动行人路径选择行为的一般特征,采用交通分配模型将大规模人群分配到具体的网络拓扑结构上,采用非线性行人路阻函数模拟人群拥挤效应;随后,计算路网流量增加条件下人群在各路段走行时间变化率,并提出以路段走行时间变化率排序作为各路段结构重要度排序的方法,据此计算各路段的鲁棒性,确定瓶颈路段.最后,以德国2010年"爱的大游行"踩踏事故为例,分析验证了大规模人群网络流瓶颈识别方法,研究讨论了对路网实施管控的流量阈值以及不同管控条件下网络流的定量演化规律,可为路网的科学管理和规划提供基础数据和理论依据.     

基于k-shell的城市路网关键路段识别方法

考虑到城市路网中不同路段所处的位置不同,其重要程度亦不同,将体现路段在路网中位置的k-shell值引入城市路网关键路段的识别中,提出了基于度+k-shell值的识别方法;该方法应用复杂网络理论对城市路网进行网络拓扑映射并分析网络特性,利用所提出的方法对网络中节点进行重要性排序,并分析依该排序的路段次序失效后对城市路网连通可靠性的影响;以西安市三环内路网为例,将文中所提出的方法与已有基于度值和介数值的测度方法进行了对比,表明基于度+k-shell值的方法较已有的两种方法能提高网络的连通可靠性。研究结果可为城市道路交通管理部门进行城市道路施工方案的优化、交通应急预案的制定等提供决策及理论支持。     

考虑节点失效网络可靠性计算的重要度抽样随机模拟

针对同时考虑节点和边单元失效的一般赋权网络,提出了一种考虑节点失效网络连通可靠性计算的Monte Carlo随机模拟算法.Monte Carlo随机模拟方法包含单元状态抽样、网络系统连通状态分析和连通功能函数指标统计三个阶段.在系统连通状态分析阶段,提出将一般赋权网络转换为边权网络的等效化方法,此方法无需额外增加等效节点或边;在单元状态抽样阶段,采用重要度抽样函数进行随机抽样,增加对失效概率贡献大的抽样点出现概率,利用自适应方法求解最优重要度抽样函数.算例分析中,根据模拟均值的相对误差和变异系数两个指标,说明了本文方法的正确性和有效性.     

交通网络效率的度量和元件重要性的计算方法

针对固定需求和弹性需求的交通网络,综合考虑均衡状态下的出行行为、出行成本、出行需求以及路段流量等因素,分别 提出了网络效率的度量方法,并在此基础上计算网络元件的重要性.算例结果表明:所提出的效率度量方法和元件重要性计算公式是合理的,并对Braess悖论网络进行了分析,发现网络元件的重要性随需求变化而变化.所提出的方法和研究结论对设计和管理交通网络具有指导意义.     

装备保障体系关键节点分析

装备保障体系在现代战争中发挥着重要的后勤保障作用。一旦保障体系中的关键保障节点遭到袭击, 将会严重影响到系统保障能力的发挥。因此, 研究装备保障体系中的关键节点识别技术, 找出薄弱环节, 对于未来战争有着重要意义。本文以复杂网络为理论基础, 提出了一种衡量保障节点重要性的指标。该节点重要性指标一方面衡量保障节点在一定空间范围内的连接能力, 另一方面按照新提出的面向任务需求的路由方式, 衡量保障节点的全局运输能力。通过与另外6种节点的重要性指标对比, 结果从多方面证明了所提的节点重要性指标在识别关键节点时的有效性及适用性。     

A New K-Shell Decomposition Method for Identifying Influential Spreaders of Epidemics on Community Networks

An efficient method for the identification of influential spreaders that could be used to control epidemics within populations would be of considerable importance. Generally, populations are characterized by its community structures and by the heterogeneous distributions of out-leaving links among nodes bridging over communities. A new method for community networks capable of identifying influential spreaders that accelerate the spread of disease is here proposed. In this method, influential spreaders serve as target nodes. This is based on the idea that, in k-shell decomposition method,out-leaving links and inner links are processed separately. The method was used on empirical networks constructed from online social networks, and results indicated that this method is more accurate. Its effectiveness stems from the patterns of connectivity among neighbors, and it successfully identified the important nodes. In addition, the performance of the method remained robust even when there were errors in the structure of the network.     

一种基于流量工程的网络端到端性能分析算法

网络性能分析与优化是面向流量工程网络设计与管理的关键任务之一。以流量工程为基础,应用网络图的方法描述网络拓扑,通过对链路性能参数描述矩阵的标准化变换及网络邻接关联矩阵传递闭包的求解,同时结合网络事件的随机性,给出一种求解网络链路数据传输能力、分析网络端到端连通性能的算法,为网络设计及其性能分析提供了一种便捷可行的方法。     

两种策略下的最短路径并行算法研究与实现

随着智能交通运输系统的研究与应用,对在大规模交通网络上求解最短路径的实时性提出了更高的要求。为了找出适用于实际交通网络的高效最短路径并行算法,首先选取了3种最短路径标号串行算法,以此为基础分别实现了网络复制及网络分割两种策略下求解最短路径的并行算法。最后,从基于G IS的交通规划软件T ransCAD中提取了实际交通路网数据,同时还随机产生了不同规模的稀疏格网,在这些网络中对并行算法的性能进行了测试和分析。结果表明,在8台机器上求解含5 181个节点的实际交通网络中32个源点的最短路径时,基于网络分割的双队列标号修正并行算法的加速比可达到6.32,在其他网络中也表现出较好的加速比及可扩展性。     

Capacitated stochastic coloured Petri net-based approach for computing two-terminal reliability of multi-state network

Classical network reliability problems assume both networks and components have only binary states,fully working or fully failed states.But many actual networks are multi-state,such as communication networks and transportation networks.The nodes and arcs in the networks may be in intermediate states which are not fully working either fully failed.A simulation approach for computing the two-terminal reliability of a multi-state network is described.Two-terminal reliability is defined as the probability that d units of demand can be supplied from the source to sink nodes under the time threshold T.The capacities of arcs may be in a stochastic state following any discrete or continuous distribution.The transmission time of each arc is also not a fixed number but stochastic according to its current capacity and demand.To solve this problem,a capacitated stochastic coloured Petri net is proposed for modelling the system behaviour.Places and transitions respectively stand for the nodes and arcs of a network.Capacitated transition and self-modified token colour with route information are defined to describe the multi-state network.By the simulation,the two-terminal reliability and node importance can be estimated and the optimal route whose reliability is highest can also be given.Finally,two examples of different kinds of multistate networks are given.     

成本驱动的加权网络演变模型

建立以成本为主要偏好连接决定因素的加权网络演化模型,来深入理解交通运输网络背后的驱动力量.模型考虑交通运输业中的规模经济效应和拥挤效应,统一在成本函数之中.模型假设新点偏好连接成本小的点,连接后各边权重会发生变化,成本小的边流量增加可能性较大.根据航空业实际的成本函数进行数值模拟,模拟结果展示了服从截尾幂律分布的点度分布,非线性的点强度和点度关系,和先负后正的度相关性,能够较好地解释航空网络实证研究结果.