基于领域相似度的复杂网络节点重要度评估算法

节点重要性度量对于研究复杂网络鲁棒性与脆弱性具有重要意义.大规模实际复杂网络的结构往往随着时间不断变化,在获取网络全局信息用于评估节点重要性方面具有局限性.通过量化节点局部网络拓扑的重合程度来定义节点间的相似性,提出了一种考虑节点度以及邻居节点拓扑重合度的节点重要性评估算法,算法只需要获取节点两跳内的邻居节点信息,通过计算邻居节点对之间的相似度,便可表征其在复杂网络中的结构重要性.基于六个经典的实际网络和一个人工的小世界网络,分别以静态与动态的方式对网络进行攻击,通过对极大连通系数与网络效率两种评估指标的实验结果对比,证明了所提算法优于基于局域信息的度指标、半局部度指标、基于节点度及其邻居度的WL指标以及基于节点位置的K-shell指标.     

基于度与集聚系数的网络节点重要性度量方法研究

网络中节点重要性度量对于研究网络的鲁棒性具有十分重要的意义. 研究者们普遍运用度或集聚系数来度量节点的重要程度, 然而度指标只考虑节点自身邻居个数而忽略了其邻居之间的信息, 集聚系数只考虑节点邻居之间的紧密程度而忽略了其邻居的规模. 本文综合考虑节点的邻居个数, 以及其邻居之间的连接紧密程度, 提出了一种基于邻居信息与集聚系数的节点重要性评价方法. 对美国航空网络和美国西部电力网进行的选择性攻击实验表明, 采用该方法的效果较k-shell指标可以分别提高24%和112%. 本文的节点重要性度量方法只需要考虑网络局部信息, 因此非常适合于对大规模网络的节点重要性进行有效分析. 关键词： 网络科学 鲁棒性 节点重要性 集聚系数     

一种有效的基于三角结构的复杂网络节点影响力度量模型

度量复杂网络中的节点影响力对理解网络的结构和功能起着至关重要的作用.度、介数、紧密度等经典指标能够一定程度上度量节点影响力,k-shell和H-index等指标也可以应用于评价节点影响力.然而这些模型都存在着各自的局限性.本文基于节点与邻居节点之间的三角结构提出了一种有效的节点影响力度量指标模型(local triangle centrality,LTC),该模型不仅考虑节点间的三角结构,同时考虑了周边邻居节点的规模.我们在多个真实复杂网络上进行了大量实验,通过SIR模型进行节点影响力仿真实验,证明LTC指标相比于其他指标能够更加准确地度量节点的传播影响力.节点删除后网络鲁棒性的实验结果也表明LTC指标具有更好效果.     

基于多阶邻居壳数的向量中心性度量方法

K-壳分解法在度量复杂网络中节点的重要性方面具有重要的理论意义和应用价值.但K-壳方法中,存在大量壳值相等的节点,从而无法精确地比较这些具有相同壳值节点的相对重要性.因此,本文基于网络中节点自身壳值与其多阶邻居的壳值,设计利用向量的形式来表示节点在复杂网络中的相对重要性程度,提出了多阶邻居壳数向量中心性方法,并设计了该中心性向量比较方法.通过在七个真实网络中进行消息传播与静态攻击实验,发现基于多阶邻居壳数向量的中心性方法具有计算复杂度低,能够有效发现具有高传播能力的节点,在传播实验中具有优越的性能.并在静态攻击实验过程中倾向于优先破坏网络中的传播核心结构.多阶邻居壳数向量中心性方法在保留K-壳中心性信息的前提下,极大提高了节点重要性的区别程度,平衡了对节点在复杂网络中联通结构的重要性的度量和对传播结构重要性的度量,因此具有重要理论意义与应用价值.     

基于改进的协同过滤相似性度量算法研究

随着工程测量和工业控制的发展,在多样的工程测量环境和工业控制环境中选择合适的测量和控制理论、方法和技术也将成为难题,推荐技术的引入可以提升工程测量的的自动化程度和工业控制的实时性。但是推荐系统中经典的相似性度量方法在数据稀疏的情况下处理能力较弱,影响了推荐的准确性。针对这一问题,将杰卡徳相似系数加以修正,并利用杰卡德相似系数能够衡量两个集合的相似度的特点,将修正后的杰卡德相似系数作为权重系数,对经典的相似性度量方法加以修正,得到新的相似性度量方法。选取5个测评指标,分别在基于用户和基于项目的协同过滤推荐算法中,对经典的相似性度量方法和改进的相似性度量方法进行测试。对比实验表明,改进的相似性度量方法表现优于传统的相似性度量方法,提升比例约为20%。     

利用邻域“结构洞”寻找社会网络中最具影响力节点

识别复杂网络中的关键节点对网络结构优化和鲁棒性增强具有十分重要的意义. 经典的关键节点测量方法在一定程度上能够辨识网络中影响力节点, 但存在一定局限性: 局部中心性测量方法仅考虑节点邻居的数目, 忽略了邻居间的拓扑关系, 不能在计算中反映邻居节点间的相互作用; 全局测量方法则由于算法本身的复杂性而不能应用于大规模社会网络的分析, 另外, 经典的关键节点测量方法也没有考虑社会网络特有的社区特征. 为高效、准确地辨识具有社区结构的社会网络中最具影响力节点, 提出了一种基于节点及其邻域结构洞的局部中心性测量方法, 该方法综合考虑了节点的邻居数量及其与邻居间的拓扑结构, 在节点约束系数的计算中同时体现了节点的度属性和“桥接”属性. 利用SIR(易感-感染-免疫)模型在真实社会网络数据上对节点传播能力进行评价后发现, 所提方法可以准确地评价节点的传播能力且具有强的鲁棒性.     

两层星形网络的特征值谱及同步能力

多层网络是当今网络科学研究的一个前沿方向.本文深入研究了两层星形网络的特征值谱及其同步能力的问题.通过严格导出的两层星形网络特征值的解析表达式,分析了网络的同步能力与节点数、层间耦合强度和层内耦合强度的关系.当同步域无界时,网络的同步能力只与叶子节点之间的层间耦合强度和网络的层内耦合强度有关;当叶子节点之间的层间耦合强度比较弱时,同步能力仅依赖于叶子节点之间的层间耦合强度;而当层内耦合强度比较弱时,同步能力依赖于层内耦合强度;当同步域有界时,节点数、层间耦合强度和层内耦合强度对网络的同步能力都有影响.当叶子节点之间的层间耦合强度比较弱时,增大叶子节点之间的层间耦合强度会增强网络的同步能力,而节点数、中心节点之间的层间耦合强度和层内耦合强度的增大反而会减弱网络的同步能力;而当层内耦合强度比较弱时,增大层内耦合强度会增强网络的同步能力,而节点数、层间耦合强度的增大会减弱网络的同步能力.进一步,在层间和层内耦合强度都相同的基础上,讨论了如何改变耦合强度更有利于同步.最后,对两层BA无标度网络进行数值仿真,得到了与两层星形网络非常类似的结论.     

基于多重影响力矩阵的有向加权网络节点重要性评估方法

本文基于有向加权网络模型,构建了三个影响力矩阵,并利用层次分析法对其赋权求和,形成多重影响力矩阵,从而提出了一种基于该矩阵的节点重要性评价方法.该方法通过新定义的交叉强度指标,来表征节点的局部重要性;利用金网节点对待评估节点的重要性影响总值,来表征节点在全网中的相对重要性.在分析影响节点对待评估节点的影响比例时,既考虑到节点间的距离因素,又引入了最短路径条数因素;既考虑了该影响节点对网络中其他节点的影响关系,又考虑了网络中其他节点对该待评估节点的影响关系,使得评价方法更加全面.将算法运用于ARPA网络,结果表明,该方法能有效地区分各节点之间的差异,最后,对实验结果进疔连锁故障的仿真对比实验,进一步验证了方法的有效性.     

多层单向耦合星形网络的特征值谱及同步能力分析

随着复杂网络同步的进一步发展,对复杂网络的研究重点由单层网络转向更加接近实际网络的多层有向网络.本文分别严格推导出三层、多层的单向耦合星形网络的特征值谱,并分析了耦合强度、节点数、层数对网络同步能力的影响,重点分析了层数和层间中心节点之间的耦合强度对多层单向耦合星形网络同步能力的影响,得出了层数对多层网络同步能力的影响至关重要.当同步域无界时,网络的同步能力与耦合强度、层数有关,同步能力随其增大而增强;当同步域有界时,对于叶子节点向中心节点耦合的多层星形网络,当层内耦合强度较弱时,层内耦合强度的增大会使同步能力增强,而层间叶子节点之间的耦合强度、层数的增大反而会使同步能力减弱;当层间中心节点之间的耦合强度较弱时,层间中心节点之间的耦合强度、层数的增大会使同步能力增强,层内耦合强度、层间叶子节点之间的耦合强度的增大反而会使同步能力减弱.对于中心节点向叶子节点耦合的多层星形网络,层间叶子节点之间的耦合强度、层数的增大会使同步能力增强,层内耦合强度、节点数、层间中心节点之间的耦合强度的增大反而会使同步能力减弱.     

复杂网络中最小K-核节点的传播能力分析

K-核分解方法对于识别复杂网络传播动力学中最重要节点具有重要的价值, 然而该方法无法对复杂网络中大量最小K-核节点的传播能力进行准确度量. 本文主要考察最小K-核节点的传播行为, 利用其邻居的K-核信息, 提出一种度量这类节点传播能力的方法. 实证网络数据集的传播行为仿真结果表明, 该方法与度、介数等指标相比更能准确度量最小K-核节点的传播能力. 关键词： 复杂网络 传播能力 K-核分解 最小K-核节点     

PageRank centrality for temporal networks

In this paper, we propose a new centrality measure for ranking the nodes and time layers of temporal networks simultaneously, referred to as the f-PageRank centrality. The f-PageRank values of nodes and time layers in temporal networks are obtained by solving the eigenvector of a multi-homogeneous map. The existence and uniqueness of the proposed centrality measure are also guaranteed by existing results, under some reasonable conditions. The numerical experiments on a synthetic temporal network and two real-world temporal networks (i.e., Email-Eu-core and CollegeMsg temporal networks) show that the proposed centrality outperforms some existing centrality measures.     

Identifying influential nodes based on graph signal processing in complex networks

Identifying influential nodes in complex networks is of both theoretical and practical importance. Existing methods identify influential nodes based on their positions in the network and assume that the nodes are homogeneous. However,node heterogeneity(i.e., different attributes such as interest, energy, age, and so on) ubiquitously exists and needs to be taken into consideration. In this paper, we conduct an investigation into node attributes and propose a graph signal processing based centrality(GSPC) method to identify influential nodes considering both the node attributes and the network topology. We first evaluate our GSPC method using two real-world datasets. The results show that our GSPC method effectively identifies influential nodes, which correspond well with the underlying ground truth. This is compatible to the previous eigenvector centrality and principal component centrality methods under circumstances where the nodes are homogeneous. In addition, spreading analysis shows that the GSPC method has a positive effect on the spreading dynamics.     

Detection of influential nodes with multi-scale information

The identification of influential nodes in complex networks is one of the most exciting topics in network science. The latest work successfully compares each node using local connectivity and weak tie theory from a new perspective. We study the structural properties of networks in depth and extend this successful node evaluation from single-scale to multi-scale. In particular, one novel position parameter based on node transmission efficiency is proposed, which mainly depends on the shortest distances from target nodes to high-degree nodes. In this regard, the novel multi-scale information importance (MSII) method is proposed to better identify the crucial nodes by combining the network's local connectivity and global position information. In simulation comparisons, five state-of-the-art algorithms, i.e. the neighbor nodes degree algorithm (NND), betweenness centrality, closeness centrality, Katz centrality and the k-shell decomposition method, are selected to compare with our MSII. The results demonstrate that our method obtains superior performance in terms of robustness and spreading propagation for both real-world and artificial networks.     

LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks

Identifying influential nodes in complex networks is one of the most significant and challenging issues, which may contribute to optimizing the network structure, controlling the process of epidemic spreading and accelerating information diffusion. The node importance ranking measures based on global information are not suitable for large-scale networks due to their high computational complexity. Moreover, they do not take into account the impact of network topology evolution over time, resulting in limitations in some applications. Based on local information of networks, a local clustering H-index (LCH) centrality measure is proposed, which considers neighborhood topology, the quantity and quality of neighbor nodes simultaneously. The proposed measure only needs the information of first-order and second-order neighbor nodes of networks, thus it has nearly linear time complexity and can be applicable to large-scale networks. In order to test the proposed measure, we adopt the susceptible-infected-recovered (SIR) and susceptible-infected (SI) models to simulate the spreading process. A series of experimental results on eight real-world networks illustrate that the proposed LCH can identify and rank influential nodes more accurately than several classical and state-of-the-art measures.     

A novel method to identify influential nodes based on hybrid topology structure

With the increasing popularity of rail transit and the increasing number of light rail trips, the vulnerability of rail transit has become increasingly prominent. Once the rail transit is maliciously broken or the light rail station is repaired, it may lead to large-scale congestion or even the paralysis of the whole rail transit network. Hence, it is particularly important to identify the influential nodes in the rail transit network. Existing identifying methods considered a single scenario on either betweenness centrality (BC) or closeness centrality. In this paper, we propose a hybrid topology structure (HTS) method to identify the critical nodes based on complex network theory. Our proposed method comprehensively considers the topology of the node itself, the topology of neighbor nodes, and the global influence of the node itself. Finally, the susceptible–infected–recovered (SIR) model, the monotonicity (M), the distinct metric (DM), the Jaccard similarity coefficient (JSC), and the Kendall correlation coefficient (KC) are utilized to evaluate the proposed method over the six real-world networks. Experimental results confirm that the proposed method achieves higher performance than existing methods in identifying networks.     

Error and attack tolerance of synchronization in Hindmarsh–Rose neural networks with community structure

Synchronization is one of the most important features observed in large-scale complex networks of interacting dynamical systems. As is well known, there is a close relation between the network topology and the network synchronizability. Using the coupled Hindmarsh–Rose neurons with community structure as a model network, in this paper we explore how failures of the nodes due to random errors or intentional attacks affect the synchronizability of community networks. The intentional attacks are realized by removing a fraction of the nodes with high values in some centrality measure such as the centralities of degree, eigenvector, betweenness and closeness. According to the master stability function method, we employ the algebraic connectivity of the considered community network as an indicator to examine the network synchronizability. Numerical evidences show that the node failure strategy based on the betweenness centrality has the most influence on the synchronizability of community networks. With this node failure strategy for a given network with a fixed number of communities, we find that the larger the degree of communities, the worse the network synchronizability; however, for a given network with a fixed degree of communities, we observe that the more the number of communities, the better the network synchronizability.     

Identification of unstable individuals in dynamic networks

To identify the unstable individuals of networks is of great importance for information mining and security management. Exploring a broad range of steady-state dynamical processes including biochemical dynamics, epidemic processes,birth–death processes and regulatory dynamics, we propose a new index from the microscopic perspective to measure the stability of network nodes based on the local correlation matrix. The proposed index describes the stability of each node based on the activity change of the node after its neighbor is disturbed. Simulation and comparison results show our index can identify the most unstable nodes in the network with various dynamical behaviors, which would actually create a richer way and a novel insight of exploring the problem of network controlling and optimization.     

综合考虑局部和全局特性的电网关键节点识别

为有效识别网络中的关键节点,提出一种综合考虑网络局部和全局特性的节点重要性识别综合指标,依据此指标对加权标准测试系统IEEE39和IEEE118中的节点进行重要性排序,并将排序结果与基于介数法和点权法对节点重要性进行排序结果进行对比,基于结构的网络效能分析和基于动力学的失同步扩散时间、同步能力比较均表明,提出的基于综合指标的节点重要性排序更合理,优于基于介数和点权的节点重要性识别方法.