复杂网络中的一种介度熵抗毁性度量方法

在复杂网络中，核心节点的损坏可能会影响到整个网络的稳定性。基于节点重要性研究了网络抗毁性度量和抗毁性能。综合考虑节点度值和介数对节点重要性的影响，提出了局部介-度中心性指标。兼顾节点的聚集系数，提出节点抗毁性度量方法。为了估量网络的抗毁性能，提出了介-度熵度量及其算法。仿真攻击实验结果表明，基于介-度中心性的攻击策略移除约20%的节点后，可将网络近似地分割为孤立节点集合，它优于传统的攻击策略，表明介-度中心性指标可以更准确地刻画节点重要性。对不同模拟网络的抗毁性评估计算结果则表明，介-度熵度量对网络抗毁性能的排序符合实际情况，在衡量网络抗毁性方面是完全合理的。     

基于介度相关性的无标度网络抗毁性研究

复杂网络主要面临随机攻击和选择性攻击,在不同的攻击方式下复杂网络的抗毁性有很大差异。综合考虑复杂网络的抗毁性参数,以节点的度和介数中心性为度量参数,通过5种不同攻击方式对无标度网络的抗毁性进行测试,得到度和介数的实时测量值,动态分析攻击下无标度网络的介度相关性。实验结果表明,无标度网络在ID、RD攻击下介度满足幂律关系,而在IB、RB和随机攻击下不严格满足幂律关系。     

一种通信网络抗毁性评价的改进模型

分析了现代战场通信网抗毁性评价的需求,针对现有通信网抗毁性测度评价模型无法准确评价网络抗毁性测度和节点重要性,以及不同节点数的网络间抗毁性的问题,利用基于最短路径数和跳面节点法节点重要性多指标评价方法对该模型进行改进。在此基础上,提出一种基于节点的全网平均等效抗毁性测度的网络抗毁性评价模型,并验证了模型的有效性。     

基于复杂网络的应急物流网络抗毁性研究*

基于复杂网络理论,引入平均最短路径距离和极大连通子图,研究应急物流网络的抗毁性测度模型,在最大度和介数等不同的攻击策略下分析了单点应急物流网络的抗毁性能。理论分析和实验结果表明,随机攻击的网络易毁性小于选择性攻击;在攻击较多顶点时,度攻击的抗毁性能较弱。     

具有抗毁性的无线传感器网络有向拓扑模型

如何通过合理构建拓扑模型有效提高网络抵御攻击的能力,一直是该领域研究的热点之一.针对无线传感网络无标度拓扑在遭受不同攻击方式时抗毁性差的问题,本文结合节点出入度和介数中心性两种因素,同时考虑数据传输的有向性,提出衡量网络抗毁性的度量模型概念,将该模型引入择优连接概率中,构建具有抗毁性的无线传感器网络有向拓扑模型.理论证明网络节点出入度均服从幂律分布,符合无标度特性,仿真实验结果表明,在相同实验环境下,该文所构拓扑模型在最大连通分支比例和网络效率两方面均优于其他3种比较模型,具有更强的抗毁性.     

考虑节点重要度的Ad Hoc网络抗毁性测度研究

Ad Hoc网络的实际应用受制于其可靠性,如何对Ad Hoc网络进行抗毁性设计和抗毁性测度评估是Ad Hoc网络可靠性研究的热点.针对这个关键问题,从Ad Hoc网络的拓扑结构入手,考虑节点的重要度,结合网络结构熵的概念,定义了网络抗毁熵、节点抗毁度和全网抗毁度,实例分析结果表明本文所定义测度是移动Ad Hoc网络抗毁性评估的有效测度.     

基于社团结构的复杂网络抗毁性测度

综合复杂网络连通度和社团结构的抗毁性测度,提出了一种新的基于社团结构的复杂网络抗毁性测度,既考虑网络的整体效能,又联系了网络本身的社团结构性。另一方面,为了更加有效地攻击网络的社团,提出一种基于社团的选择性攻击方式,移除较少的节点就使网络中的社团崩溃。通过仿真分析表明,基于社团的复杂网络抗毁性测度更加全面客观地衡量了网络的抗毁性,基于社团的选择性攻击更加有效地破坏了网络的社团结构性。     

基于不重叠路径熵的网络抗毁性评估方法

通过引入熵的概念,提出了基于不重叠路径数的标准稳定熵指标,用于刻画节点间抗毁性随不重叠路径数变化的规律.在此基础上给出了用于全网抗毁性评估的模型.同时指出了评价模型中涉及的节点间不重叠路径数的计算方法.最后通过算例分析以及与最短路径法相比较,论证了基于不重叠路径熵的模型在网络抗毁性评估方面具有更高的准确性与合理性.     

小世界网络抗毁性及介-度相关性研究

日常生活中,复杂网络主要面临随机攻击和选择性攻击,网络模型的结构特性使复杂网络在不同攻击方式下的抗毁性有很大的差异.综合考虑复杂网络的抗毁性参数和网络模型的结构特性差异,文章以节点的最大度值、平均度值、最大介数和平均介数为度量参数,通过5种不同攻击方式对WS小世界网络的抗毁性进行了测试,得到了介度关系曲线,随着节点的移除,动态分析了WS小世界网络的抗毁性和攻击下小世界网络的介 度相关性.实验结果表明,WS小世界网络在RD攻击下表现出一定的脆弱性,在其他攻击方式下有很强的鲁棒性,而其介度关系在某些区域呈线性关系,但大部分区域呈现无规律性,其动态相关性需要进一步研究.小世界网络较强的抗毁性对组建网络有重要的影响,鉴于小世界网络的结构特性,组建网络时应尽量不要把网络的功能集中在少数Hub节点上.针对WS小世界网络较强的鲁棒性,结合小世界网络的结构特性,将做进一步研究,以便提出更高效的攻击策略.     

不同攻击模式下城市公交网络抗毁性分析

为了保证城市公交网络的安全运营、提高整个交通网络运行效率,以成都市公交网络为例,分析了该网络的拓扑结构特性,研究了该网络在随机攻击和蓄意攻击下的抗毁性。仿真结果表明,网络在随机攻击和基于节点度的攻击下连续移除节点的数目几乎不对网络的抗毁性产生影响,而在基于节点介数和效率的攻击下连续移除的节点个数越少,网络的抗毁性越差;基于节点介数的攻击对网络抗毁性产生的影响要比随机、基于节点度和效率更为显著。     

Finding groups with maximum betweenness centrality

In this paper we consider the problem of identifying the most influential (or central) group of nodes (of some predefined size) in a network. Such a group has the largest value of betweenness centrality or one of its variants, for example, the length-scaled or the bounded-distance betweenness centralities. We demonstrate that this problem can be modelled as a mixed integer program (MIP) that can be solved for reasonably sized network instances using off-the-shelf MIP solvers. We also discuss interesting relations between the group betweenness and the bounded-distance betweenness centrality concepts. In particular, we exploit these relations in an algorithmic scheme to identify approximate solutions for the original problem of identifying the most central group of nodes. Furthermore, we generalize our approach for identification of not only the most central groups of nodes, but also central groups of graph elements that consists of either nodes or edges exclusively, or their combination according to some pre-specified criteria. If necessary, additional cohesiveness properties can also be enforced, for example, the targeted group should form a clique or a κ-club. Finally, we conduct extensive computational experiments with different types of real-life and synthetic network instances to show the effectiveness and flexibility of the proposed framework. Even more importantly, our experiments reveal some interesting insights into the properties of influential groups of graph elements modelled using the maximum betweenness centrality concept or one of its variations.     

邮件网络中基于介数的免疫策略研究

针对如何抑制病毒在邮件网络中的传播问题,在交互式邮件传播模型中分析介数免疫策略与传统基于度信息的免疫策略对病毒传播的控制能力。在真实的安然邮件网络和人工网络中对比各种免疫策略的效率与代价,结果发现节点介数免疫策略只须保护少量节点就可以降低病毒传播规模,有效地保护网络安全。     

基于中介中心度的微博影响力个体发现

微博中重要影响力个体的发现有着极为重要的作用。中介中心度方法是发现网络中重要节点的有效方法, 然而传统的中介中心度方法只适用于小规模的网络, 对于海量的微博网络信息却无能为力。提出一种基于随机游走的中介中心度算法, 该算法不仅能有效地应对海量的微博网络数据, 而且其发现结果也明显优于相关的研究。     

一种利用BC方法的关键词自动提取算法研究

通过分析几种常见关键词自动抽取方法的特点和不足，以KeyGraph算法思想为基础，构建词语网络并利用网络节点中心度（Betweenness Centrality）理论，提出了一种新的自动抽取关键词算法．通过分析和比较，新算法提取的关键词更能体现文档内容，并且相对低频而意义重要的关键词也能被提取出．最后，通过与TF和TFIDF算法的比较和分析，获得了令人满意的结果．     

基于删边扩容策略的城市交通网络优化

建立一个面向控制的城市交通网络模型,以结构矩阵的形式进行数学表示,引入序参量的概念来表征城市交通的拥堵状况,并提出了基于介数的具体删边扩容策略. 将此策略应用到已建立的交通网络模型中进行仿真验证,证明了该策略在不影响行驶路径长度的前提下可以显著改善城市交通状况,并得出了删边比例与介数最大值成反比例的对应关系的结论.     

基于Spark的L1-BC算法在关键蛋白质检测中的应用

Spark作为当今大数据领域的分布式处理框架,在各个领域的应用越来越广泛。在关键蛋白质预测中,基于蛋白质相互作用网络拓扑结构的介数中心（BC）指标有着很好的预测效果,提出一种新的L1-BC指标,不仅能区分一些BC指标值相同的蛋白质,还能通过取子图计算体现出蛋白质的局部特性,实验结果表明该指标能够提高关键蛋白质的预测精度。基于Spark平台实现了L1-BC指标的并行计算算法,通过累加器和广播变量使得内存得到极大的优化,在数据集YDIP上的实验结果表明,基于Spark的L1-BC算法的加速比达到了94.31%。     

无锁同步的细粒度并行介度中心算法

通过结合体系结构和算法进行研究发现,基于锁的同步机制是细粒度并行介度中心(betweenness centrality,简称BC)算法在现有多核平台上高效执行的主要瓶颈.提出了一种消除锁同步的数据驱动(data-centric)并行算法,在AMD 32核SMP和Intel8核SMP两个平台上获得了2倍左右的加速比.     

基于复杂网络分析的软件高危缺陷评估方法

为了评估软件缺陷的风险,提出了一种基于复杂网络分析的软件缺陷评估方法。该方法首先用一个网络模型表达程序实体之间的关系,将源代码中的方法抽象为节点,方法间的调用关系抽象为有向边,以此构造程序源代码网络;然后分别用介数算法和PageRank算法计算造成软件缺陷的方法节点在源代码全局网络中的地位,由此评估缺陷的风险高低。实验结果表明,该方法在评估内部高危缺陷时有较好的效果,有助于提高软件开发维护人员对一些隐蔽高危缺陷的关注度,进而为后续修复缺陷与软件演化提供有益的线索。     

复杂网络加边扩容策略研究

网络扩容策略是近年来复杂网络的研究热点,目前针对网络删边扩容研究已经颇为成熟,但加边扩容的研究还较为匮乏.根据网络容量与网络节点介数的最大值成反比的结论,提出了一种复杂网络加边扩容的策略,并与最低度添加边和最长最短路径添加边策略进行分析比较.实验表明:在添加边数目相同的条件下,提出的添加边策略不仅能有效减少网络平均最短路径,还可以最大化提高网络的容量.