论文部分内容阅读
近年来,复杂网络研究引起了物理学、数学、化学、医学、生物学、计算机科学,社会学等不同领域研究者的广泛关注。真实网络存在异质性,网络中不同节点或者不同边在结构和功能上的作用具有很大的差异,重要性大的节点或边是指可以更大地影响网络结构和功能的节点或边。从网络鲁棒性与脆弱性的角度进行评价,一个节点或者一条边是否重要是由移除该节点或该条边后对网络连通度造成的影响程度决定的。准确挖掘网络中的关键节点和关键边,既可用作防御策略,对网络关键节点和关键边加以保护从而提高网络的抗毁性,也可用作进攻策略,在网络打击过程中集中火力打击敌方关键节点和关键边,从而实现以较低的打击成本达到较大的收益。考察复杂网络的结构特征,论文从网络鲁棒性的角度,研究了复杂网络中节点和边的重要性度量问题,并进一步研究了多节点发起的(多源)信息传播中的影响最大化问题。
提出了一种基于节点桥接特征的复杂网络节点重要性度量算法。实际网络数据规模庞大,网络结构复杂且往往随着时间动态变化,基于网络全局属性的评价指标由于算法复杂度过高,不适用于分析大型复杂网络。分析节点局部结构特征,如果一个节点出现在其邻域节点间的最短路径上的频次很高,意味其邻域节点间的结构性缺口特征越明显,此时目标节点的桥接作用强,其结构重要度也高,由此论文提出了一种基于节点桥接特征的复杂网络节点重要度排序算法。在六个公开的实际网络数据集中和一个人工构建的小世界网络中,以静态与动态的方式移除网络节点,考察不同算法在极大连通系数和网络效率两种指标下的算法效果,证明所提算法评价节点重要度的效果整体优于度指标、K-shell指标、LLS指标和WL指标。特别是在网络攻击的初始阶段,所提出的算法的优势更加明显。
设计了一种基于信息熵的复杂网络节点重要性度量算法。论文采用的信息熵是一种结构熵,在复杂网络中,结构熵指的是从网络结构的拓扑特性出发评估和度量网络结构的复杂程度,大多数研究都是信息熵来定义复杂网络的结构熵。熵构建过程中最重要的一个环节是构建熵所需要的概率集,大多数情况下使用度信息来构建。论文采用自我网络(Ego network)的介数和信息熵来定义节点的网络结构熵,计算自我网络的节点介数仅需获取节点的一条网络信息,算法复杂度低,可以用于大规模网络,论文综合考察网络邻域节点和自身的权重,提出了自我网络介数的映射熵MEBE。在多个实际网络中的打击实验表明,MEBE算法与度指标以及度指标导出的结构熵算法相比,可以取得更高的节点重要性度量精度。
提出了一种基于路径和完全图关键边评估算法。在复杂网络中,有时候并不能阻断节点对外的所有联系,但是有必要切断最为重要的连边,此时需要对网络关键边进行度量。以网路中的路径为出发点,结合了边的度数和介数,并且加入完全图的考察,提出了一种新的高精度边的重要性度量算法。在14个经典的实际网络数据集、以及ER网络模型和LFR网络模型两种人工合成的网络上进行仿真打击实验,采用极大连通系数和网络效率两种指标对算法排序精度进行评价,实验结果与边的Jaccard系数、边端点度乘积、边端点介数乘积等算法相比,论文所提的算法可以更精确地对边的重要性进行度量。
提出一种基于核数和H指数的复杂网络影响最大化算法,算法利用了核数层次特征和H指数传播影响力特征。该算法首先求出网络中各个节点的核数和H指数,并综合这两个属性选出当前影响最大的节点作为种子节点,此后通过核数约束条件和H指数约束条件求出当前节点的影响区域,并通过覆盖算法寻找下一个节点。通过此算法既可以保证找到的种子节点具有极高的影响力,又可以减小种子节点的影响力的重叠区域,从而实现影响力最大化。在5个真实网络数据集、以及BA网络模型和LFR网络模型两种人工网络数据中的实验结果表明,与度指标、核数、H指数、折扣度等算法相比,所提算法能在取值范围更宽的传播率下得到更高的初始节点集精度。
提出了一种基于节点桥接特征的复杂网络节点重要性度量算法。实际网络数据规模庞大,网络结构复杂且往往随着时间动态变化,基于网络全局属性的评价指标由于算法复杂度过高,不适用于分析大型复杂网络。分析节点局部结构特征,如果一个节点出现在其邻域节点间的最短路径上的频次很高,意味其邻域节点间的结构性缺口特征越明显,此时目标节点的桥接作用强,其结构重要度也高,由此论文提出了一种基于节点桥接特征的复杂网络节点重要度排序算法。在六个公开的实际网络数据集中和一个人工构建的小世界网络中,以静态与动态的方式移除网络节点,考察不同算法在极大连通系数和网络效率两种指标下的算法效果,证明所提算法评价节点重要度的效果整体优于度指标、K-shell指标、LLS指标和WL指标。特别是在网络攻击的初始阶段,所提出的算法的优势更加明显。
设计了一种基于信息熵的复杂网络节点重要性度量算法。论文采用的信息熵是一种结构熵,在复杂网络中,结构熵指的是从网络结构的拓扑特性出发评估和度量网络结构的复杂程度,大多数研究都是信息熵来定义复杂网络的结构熵。熵构建过程中最重要的一个环节是构建熵所需要的概率集,大多数情况下使用度信息来构建。论文采用自我网络(Ego network)的介数和信息熵来定义节点的网络结构熵,计算自我网络的节点介数仅需获取节点的一条网络信息,算法复杂度低,可以用于大规模网络,论文综合考察网络邻域节点和自身的权重,提出了自我网络介数的映射熵MEBE。在多个实际网络中的打击实验表明,MEBE算法与度指标以及度指标导出的结构熵算法相比,可以取得更高的节点重要性度量精度。
提出了一种基于路径和完全图关键边评估算法。在复杂网络中,有时候并不能阻断节点对外的所有联系,但是有必要切断最为重要的连边,此时需要对网络关键边进行度量。以网路中的路径为出发点,结合了边的度数和介数,并且加入完全图的考察,提出了一种新的高精度边的重要性度量算法。在14个经典的实际网络数据集、以及ER网络模型和LFR网络模型两种人工合成的网络上进行仿真打击实验,采用极大连通系数和网络效率两种指标对算法排序精度进行评价,实验结果与边的Jaccard系数、边端点度乘积、边端点介数乘积等算法相比,论文所提的算法可以更精确地对边的重要性进行度量。
提出一种基于核数和H指数的复杂网络影响最大化算法,算法利用了核数层次特征和H指数传播影响力特征。该算法首先求出网络中各个节点的核数和H指数,并综合这两个属性选出当前影响最大的节点作为种子节点,此后通过核数约束条件和H指数约束条件求出当前节点的影响区域,并通过覆盖算法寻找下一个节点。通过此算法既可以保证找到的种子节点具有极高的影响力,又可以减小种子节点的影响力的重叠区域,从而实现影响力最大化。在5个真实网络数据集、以及BA网络模型和LFR网络模型两种人工网络数据中的实验结果表明,与度指标、核数、H指数、折扣度等算法相比,所提算法能在取值范围更宽的传播率下得到更高的初始节点集精度。